외적으로 이해하는 CCW와 선분 교차 판정

About this offer

코딩테스트에서 좌표와 선분이 등장하면 기울기를 먼저 떠올리기 쉽다. 예를 들어 두 선분이 평행한지 확인하려면 각 선분의 기울기를 계산해 비교할 수 있다. double slope1 = (double) dy1 / dx1; double slope2 = (double) dy2 / dx2; 하지만 이 방식에는 몇 가지 문제가 있다. dx == 0 인 수직선을 별도로 처리해야 한다. 실수 연산을 사용하면 오차를 고려해야 한다. 이럴 때 사용할 수 있는 것이 외적(Cross Product) 이다. 외적은 단순히 두 벡터가 평행한지를 확인하는 것에서 끝나지 않는다. 외적의 부호 를 이용하면 세 점이 어느 방향으로 놓여 있는지를 판단할 수 있고, 이것이 CCW(Counter Clockwise) 알고리즘이다. 그리고 CCW를 이용하면 두 선분이 서로 교차하는지도 판별할 수 있다. 이 글에서는 다음 흐름으로 정리해본다. 외적 → CCW → 선분 교차 판정 1. 외적 복습 2차원 벡터 $\overrightarrow{a}=(x_1,y_1)$, $\overrightarrow{b}=(x_2,y_2)$가 있을 때 외적은 다음과 같이 계산할 수 있다. $$ \overrightarrow{a}\times\overrightarrow{b} = x_1y_2-y_1x_2 $$ 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이와 같다. $$ \left|\overrightarrow{a}\times\overrightarrow{b}\right| = \left|\overrightarrow{a}\right| \left|\overrightarrow{b}\right| \sin\theta $$ 두 벡터가 평행하다면 두 벡터 사이의 각도는 $0^\circ$ 또는 $180^\circ$이다. $$ \sin 0^\circ = 0 $$ $$ \sin 180^\circ = 0 $$ 따라서 평행한 두 벡터의 외적은 0이다. $$ \overrightarrow{a}\times\overrightarrow{b}=0 $$ 코드에서는 다음처럼 확인할 수 있다. long cross = x1 * y2 - y1 * x2; if (cross == 0) { // 두 벡터는 평행 } 기울기를 나눠서 비교하지 않기 때문에 수직선이나 실수 오차를 별도로 처리할 필요가 없다. 하지만 외적이 알려주는 정보는 단순히 0인가 아닌가 에서 끝나지 않는다. 2. 외적의 부호는 방향을 나타낸다 두 벡터의 외적 결과에는 부호가 있다. 외적 결과 의미 > 0 반시계 방향 < 0 시계 방향 = 0 일직선 즉 외적은 두 벡터가 평행한지를 판별할 뿐 아니라, 한 벡터에서 다른 벡터로 이동할 때 어느 방향으로 꺾이는지도 알려준다. 이 성질을 세 점에 적용한 것이 CCW 다. 3. CCW란? CCW는 Counter Clockwise 의 약자다. 세 점 A , B , C 가 있을 때 A → B → C 순서로 이동하면 진행 방향이 다음 중 무엇인지 판별한다. 반시계 방향 시계 방향 일직선 예를 들어 다음과 같은 경우를 생각해보자. C / A ── B A → B 로 이동한 뒤 C로 향하려면 반시계 방향으로 꺾어야 한다. 반대로 다음과 같다면 시계 방향이다. A ── B \ C 4. CCW는 어떻게 계산할까? 세 점을 다음과 같이 두자. $A=(A_x,A_y)$ $B=(B_x,B_y)$ $C=(C_x,C_y)$ A를 기준점으로 두 개의 벡터를 만든다. $$ \overrightarrow{AB} = (B_x-A_x,\ B_y-A_y) $$ $$ \overrightarrow{AC} = (C_x-A_x,\ C_y-A_y) $$ 그리고 두 벡터를 외적한다. $$ \overrightarrow{AB}\times\overrightarrow{AC} $$ 좌표로 풀어쓰면 다음과 같다. $$ (B_x-A_x)(C_y-A_y) - (B_y-A_y)(C_x-A_x) $$ 결과의 부호에 따라 방향을 판단할 수 있다. CCW(A, B, C) > 0 → 반시계 방향 CCW(A, B, C) < 0 → 시계 방향 CCW(A, B, C) = 0 → 일직선 Java로 구현하면 다음과 같다. static long ccw(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } 방향만 필요하다면 외적의 실제 값 대신 -1 , 0 , 1 만 반환하도록 만들 수도 있다. static int ccw(Point a, Point b, Point c) { long cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); return Long.compare(cross, 0); } 반환값의 의미는 다음과 같다. 1 → 반시계 0 → 일직선 -1 → 시계 CCW는 별개의 복잡한 공식이라기보다 외적의 부호를 세 점의 방향 관계에 적용한 것 이라고 볼 수 있다. 5. CCW로 선분 교차 판정하기 이제 네 점 A , B , C , D 가 있고 두 선분 AB , CD 가 있다고 하자. 두 선분이 서로 가로질러 교차하려면 다음 두 조건을 모두 만족해야 한다. C와 D가 직선 AB의 서로 반대쪽에 있어야 한다. A와 B가 직선 CD의 서로 반대쪽에 있어야 한다. 6. C와 D가 AB의 서로 반대편에 있는지 확인 직선 AB를 기준으로 C와 D의 방향을 각각 확인한다. ccw(A, B, C); ccw(A, B, D); C와 D가 AB의 서로 반대편에 있다면 두 CCW 결과의 부호도 서로 다르다. 따라서 다음 조건을 만족한다. $$ CCW(A,B,C)\times CCW(A,B,D)<0 $$ 예를 들어 다음과 같은 형태다. C | A --+-- B | D 7. 한쪽만 검사하면 안 되는 이유 처음에는 다음 조건만 확인하면 될 것처럼 보인다. ccw(A, B, C) * ccw(A, B, D) < 0 하지만 이것만으로는 부족하다. C와 D를 잇는 선분이 실제 선분 AB가 아니라, AB를 무한히 연장한 직선 과 만날 수도 있기 때문이다. 따라서 반대 방향에서도 확인해야 한다. 즉 A와 B가 직선 CD의 서로 반대편에 있는지도 검사한다. $$ CCW(C,D,A)\times CCW(C,D,B)<0 $$ 결국 일반적인 교차 조건은 다음 두 조건을 모두 만족하는 것이다. $$ CCW(A,B,C)\times CCW(A,B,D)<0 $$ $$ CCW(C,D,A)\times CCW(C,D,B)<0 $$ 코드로 표현하면 다음과 같다. boolean intersect = ccw(a, b, c) * ccw(a, b, d) < 0 && ccw(c, d, a) * ccw(c, d, b) < 0; 핵심은 두 선분 각각을 기준으로 상대 선분의 두 끝점이 서로 반대편에 있는지 검사한다는 것 이다. 8. 선분의 끝점이 닿는 경우 두 선분이 정확히 한 끝점에서 만나는 경우도 교차로 취급한다고 하자. A ------ B | C 이 경우 하나 이상의 CCW 결과가 0이 된다. 따라서 < 0 이 아니라 <= 0 으로 조건을 확장해야 한다. $$ CCW(A,B,C)\times CCW(A,B,D)\leq0 $$ $$ CCW(C,D,A)\times CCW(C,D,B)\leq0 $$ 하지만 여기서 새로운 예외가 생긴다. 9. 네 점이 일직선 위에 있는 경우 다음 두 선분을 생각해보자. A ----- B C ----- D 두 선분은 서로 떨어져 있다. 하지만 네 점이 모두 같은 직선 위에 있기 때문에 모든 CCW 결과가 0이 된다. ccw(a, b, c) == 0; ccw(a, b, d) == 0; ccw(c, d, a) == 0; ccw(c, d, b) == 0; 따라서 단순히 다음 조건만 검사하면 ab <= 0 && cd <= 0 두 선분이 교차한다고 잘못 판단하게 된다. 즉 CCW는 두 선분이 같은 직선 위에 있다는 사실까지만 알려줄 뿐, 실제 구간이 겹치는지는 알려주지 않는다. 그래서 두 선분이 모두 일직선 위에 있는 경우에는 실제 구간이 겹치는지 추가로 확인해야 한다. 10. 일직선 선분의 겹침 판정 두 선분을 좌표 순서대로 정렬했다고 생각해보자. A -------- B C -------- D 두 선분이 겹치려면 다음 조건을 만족해야 한다. A <= D C <= B 반대로 A ----- B C ----- D 처럼 B < C 라면 두 선분은 떨어져 있다. 2차원 좌표에서는 점을 (x, y) 의 사전식 순서로 비교할 수 있다. static int compare(Point a, Point b) { if (a.x != b.x) { return Long.compare(a.x, b.x); } return Long.compare(a.y, b.y); } 따라서 선분 교차 판정은 크게 두 단계로 생각할 수 있다. 1. CCW를 이용해 두 선분의 방향 관계를 확인한다. 2. 네 점이 모두 일직선이라면 실제 선분 구간이 겹치는지 추가로 확인한다. 11. 전체 Java 구현 class Point { long x; long y; Point(long x, long y) { this.x = x; this.y = y; } } public class Geometry { static int ccw(Point a, Point b, Point c) { long cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); return Long.compare(cross, 0); } static boolean intersects(Point a, Point b, Point c, Point d) { int abC = ccw(a, b, c); int abD = ccw(a, b, d); int cdA = ccw(c, d, a); int cdB = ccw(c, d, b); int ab = abC * abD; int cd = cdA * cdB; // 네 점이 모두 일직선 위에 있는 경우 if (ab == 0 && cd == 0) { if (compare(a, b) > 0) { Point temp = a; a = b; b = temp; } if (compare(c, d) > 0) { Point temp = c; c = d; d = temp; } return compare(a, d) <= 0 && compare(c, b) <= 0; } return ab <= 0 && cd <= 0; } static int compare(Point a, Point b) { if (a.x != b.x) { return Long.compare(a.x, b.x); } return Long.compare(a.y, b.y); } } 12. 왜 long 을 사용하는가? CCW 계산에서는 다음과 같은 곱셈이 발생한다. (b.x - a.x) * (c.y - a.y) 각 좌표가 int 범위 안에 있다고 해서 곱셈 결과도 int 범위 안에 있는 것은 아니다. 예를 들어 값이 100,000 정도라면 100,000 × 100,000 = 10,000,000,000 이 되어 이미 int 의 최대값을 넘어간다. 따라서 좌표 범위가 크다면 CCW 계산은 long 으로 처리하는 것이 안전하다. 또 위 구현처럼 ccw() 에서 실제 외적 값을 그대로 반환하지 않고 -1 , 0 , 1 로 정규화해 반환하면 이후 ccw(a, b, c) * ccw(a, b, d) 계산에서도 오버플로를 걱정할 필요가 없다. 13. 정리 처음에는 외적을 단순히 평행 여부를 판별하는 공식으로 생각할 수 있다. 외적 == 0 → 두 벡터가 평행 하지만 외적의 부호 까지 보면 더 많은 정보를 얻을 수 있다. 외적 > 0 → 반시계 방향 외적 < 0 → 시계 방향 외적 == 0 → 일직선 이 성질을 세 점에 적용한 것이 CCW 다. 그리고 CCW를 두 선분 각각의 관점에서 적용하면 선분 교차 여부를 판별할 수 있다. 외적 ↓ 방향 판별 ↓ CCW ↓ 선분 교차 판정 CCW와 선분 교차 판정을 각각 독립된 공식으로 외우기보다, 결국 모든 것이 다음 외적 계산에서 출발한다는 점을 이해하는 것이 중요하다. $$ (x_1,y_1)\times(x_2,y_2) = x_1y_2-y_1x_2 $$ 외적의 0 여부와 부호가 무엇을 의미하는지 이해하면 CCW와 선분 교차 판정까지 자연스럽게 연결된다. 특히 코딩테스트에서는 기울기를 직접 계산하는 것보다 외적을 사용하면 다음과 같은 장점이 있다. 나눗셈이 필요 없다. 수직선을 별도로 처리하지 않아도 된다. 실수 오차를 피할 수 있다. 좌표 문제에서 방향이나 교차 여부를 판단해야 한다면 기울기보다 외적과 CCW를 먼저 떠올려볼 수 있다.