96. Line Intersection

기하 문제 중에는 두 선분이 서로 교차하는지를 알아내야 하는 것들이 꽤 있다. 선분의 교차 여부를 프로그램으로 구현하려고 하면 그리 만만하지 않은데, 앞에서 설명한 CCW 함수를 이용하면 비교적 간단하게 선분 교차 여부를 확인할 수 있다. $2$차원 좌표평면에 네 점 $\text{A}(x_1, y_1), \text{B}(x_2, y_2), \text{C}(x_3, y_3), \text{D}(x_4, y_4)$가 존재하고 선분 $\overline{\text{AB}}$와 선분 $\overline{\text{CD}}$의 교차 여부를 판별해야 하는 경우를 생각해 보자.

 

점들의 위치가 다음과 같을 때,

선분 $\overline{\text{AB}}$와 선분 $\overline{\text{CD}}$는 교차한다.

만약 점 $\text{B}$와 점 $\text{C}$의 위치를 서로 바꾼다면 선분 $\overline{\text{AB}}$와 선분 $\overline{\text{CD}}$는 교차하지 않는다.

두 그림의 차이를 CCW 함수의 관점에서 찾아보면, 선분 $\overline{\text{AB}}$를 기준으로 점 $\text{C}$와 점 $\text{D}$의 방향이 같은 경우 선분이 교차하지 않는다. 마찬가지로 선분 $\overline{\text{CD}}$를 기준으로 점 $\text{A}$와 점 $\text{B}$의 방향이 같은 경우도 선분이 교차하지 않는다. CCW 함수에 의한 세 점 $\text{A}, \text{B}, \text{C}$의 방향 관계를 $\text{CCW(A, B, C)}$라고 하면, $\text{CCW(A, B, C)} \cdot \text{CCW(A, B, D)} > 0$ 또는 $\text{CCW(C, D, A)} \cdot \text{CCW(C, D, B)} > 0$인 경우 두 선분이 교차하지 않는다고 할 수 있다. 그렇지 않은 경우, $\text{CCW(A, B, C)} \cdot \text{CCW(A, B, D)} \le 0$이고 $\text{CCW(C, D, A)} \cdot \text{CCW(C, D, B)} \le 0$이며 다음과 같은 경우들이 존재할 수 있다.

 

만약 $\text{CCW(A, B, C)} \ne 0$ 또는 $\text{CCW(A, B, D)} \ne 0$ 또는 $\text{CCW(C, D, A)} \ne 0$ 또는 $\text{CCW(C, D, B)} \ne 0$이라면 두 선분이 끝점이 아닌 곳에서 만나거나 아래의 경우처럼 한 점이 다른 선분 위에 있는 경우이므로 두 선분이 교차한다.

그렇지 않다면 모든 CCW 함수의 결과값이 $0$이므로 네 점이 한 직선 위에 있는 경우가 된다.

선분을 뒤집거나 순서를 아예 반대로 하는 경우를 같은 것으로 생각하면 네 점의 순서로 다음과 같은 세 가지 경우가 나올 수 있는데, 이중 첫 번째와 두 번째 경우는 선분이 교차하고 세 번째 경우는 선분이 교차하지 않는다. 이것은 점들의 $x$좌표 또는 $y$좌표를 정렬했을 때 첫 번째와 두 번째 값이 같은 선분에 속하고 세 번째와 네 번째 값이 같은 선분에 속하는 경우와 같다. 이 경우까지 처리하면 평면 상의 두 선분에 대한 선분 교차 판정이 완료된다. 구현은 다음과 같다.

typedef long long LL;
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3)
{
    LL t =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    if(t > 0)return 1;
    else if(t < 0)return -1;
    else return 0;
}
int line_intersect(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3, LL x4, LL y4)
{
    LL c1 = ccw(x1, y1, x2, y2, x3, y3), c2 = ccw(x1, y1, x2, y2, x4, y4), c3 = ccw(x3, y3, x4, y4, x1, y1), c4 = ccw(x3, y3, x4, y4, x2, y2);
    if(c1 * c2 > 0 || c3 * c4 > 0)return 0;
    else if(c1 || c2 || c3 || c4)return 1;
    else if(min(x1, x2) > max(x3, x4) || min(y1, y2) > max(y3, y4) || min(x3, x4) > max(x1, x2) || min(y3, y4) > max(y1, y2))return 0;
    else return 1;
}

 

[연습문제]

 

BOJ 17386. 선분 교차 1 (Gold III)

선분 교차 여부를 판정하는데 CCW 함수의 결과값이 $0$인 경우가 존재하지 않아서 케이스 처리가 비교적 간단하다.

 

BOJ 17387. 선분 교차 2 (Gold II)

이 문제는 CCW 함수의 결과값이 $0$인 경우가 존재할 수 있으므로 그 경우도 모두 처리하면 된다.

 

BOJ 20149. 선분 교차 3 (Platinum IV)

이번에는 두 선분이 한 점에서 만나는 경우 교차점의 좌표까지 구해야 한다. 직선의 방정식으로 교점을 구할 수도 있고, 이분 탐색으로 교차점의 좌표를 구해도 된다. 한 선분의 한쪽 끝점을 계속 움직이면서 다른 선분과 교차하는지 확인하는 것이다.

 

→ solved.ac tag: line_intersection