[알고리즘] 세 점의 방향성 파악하기 'CCW 알고리즘'

안녕하세요.

여행벌입니다.

오늘은 세 점이 주어졌을 때, 방향성을 파악할 수 있는 CCW 알고리즘에 대해 다뤄보겠습니다.

---

다음과 같이 세 점 A, B, C 가 있을 때, 세 점의 방향성을 시계방향 / 반시계방향 / 일직선 3가지로 나눌 수 있습니다.

그렇다면 세 점이 주어졌을 때, 어떻게 시계방향인지 반시계 방향인지 일직선인지 구분할 수 있을까요?

우리가 잘 알고 있는 직선의 방정식을 이용해서 쉽게 구분할 수 있습니다.

 

[결론]

int CCW(int x1, int y1, int x2, int y2, int x3, int y3){
	int temp1 = (y2 - y1) * (x3 - x1) + y1 * (x2 - x1);
	int temp2 = (x2 - x1) * y3;

	if (temp1 < temp2) // 반시계
		return 1;
	else if (temp1 > temp2) // 시계
		return -1;
	else // 일직선
		return 0;

}

 

[증명]

A점 (x1, y1) /  B점 (x2, y2) / C점 (x3, y3) 가 주어졌다고 해보겠습니다.

아래 그림과 같이 AB점을 지나는 직선으로 평면을 두 개로 나눴을 때,

어느 쪽에 C점이 있느냐에 따라 시계방향인지 반시계 방향인지 판단할 수 있습니다.

 

[AB직선의 방정식]

-AB 직선의 기울기가 양수.

먼저 기울기가 양수인 경우, AB 직선의 방정식에 C점의 X 좌표인 x3를 대입했을 때, 얻어낸 y 값이

y3랑 같다면 직선 위

y3보다 작다면 반시계방향,

y3보다 크다면 시계방향인 것을 확인할 수 있습니다.

x2 - x1이 양수이므로 x2 - x1을 양변에 곱해도 부등호는 변하지 않습니다.

 

-AB 직선의 기울기가 음수.

위 그림은 반대로 직선의 방정식에 x3를 대입해서 얻은 y 값이 

y3랑 같다면 직선 위

y3보다 작다면 시계방향,

y3보다 크다면 반시계방향인 것을 확인할 수 있습니다.

하지만 이때, x2 - x1 은 음수이므로 양변에 x2 - x1을 곱해주면 부등호 방향이 바뀌어 위에서 얻어낸 식과 같아집니다.

---

세 점의 방향성을 알려주는 알고리즘을 'CCW 알고리즘' 이라고 합니다.

CCW 알고리즘을 기반으로 한 여러 기하 알고리즘이 많기 때문에 익혀두시는 게 좋을 것 같습니다!

 

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.