알고리즘: CCW(Counter Clock Wise)

CCW 알고리즘: 

3개의 점 A, B, C가  있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘.

 

위 알고리즘을 사용하면 선분 AB에 대해 점 C가 선분의 왼쪽에 있는지 오른쪽에 있는지 판단할 수 있다.

다른말로 표현하면 시계방향을 그리는지 반시계 방향을 그리는지 알 수 있다.

 

세 점 A(x1, y1), B(x2, y2), C(x3, y3)이 주어졌을 때

두 벡터 (x2-x1, y2-y1), (x3-x1, y3-y1)의 외적의 부호가 방향을 결정한다.

 

일반화한 외적의 식은 다음과 같다: (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) 

시계, 반시계, 직선 총 3가지 경우가 존재할 수 있음.

시계: -1, 직선: 0, 반시계: 1

int ccw(int x1, int y1, int x2, int x2, int y2, int x3, int y3) {
 return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
}

외적 계산법

연습문제를 풀어보자~

https://www.acmicpc.net/problem/11758

---

CCW를 응용한 두 선분의 교차 판단:

점 4개(a1, a2, b1, b2)가 주어졌을 때 하나의 선분을 기준으로 다른 선분의 두 끝 점이 선분의 좌우에 위치하면 겹친다.

(두 선분에 대해 전부 확인해야함.)

즉, (ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 && ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0)를 만족할 경우 두 선분은 겹쳐있다.

예외: 외적이 0이 나올경우, 겹치는 점을 확인해야한다.

 

연습문제를 풀어보자~

https://www.acmicpc.net/problem/17386 예외 미적용

https://www.acmicpc.net/problem/17387 예외 적용