CCW와 CCW를 이용한 선분 교차 판별

PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다.

그 전에 우선 CCW에 대하여 이야기 해보겠습니다.

CCW는 Counterclockwise의 약자로 풀어 해석하면 그냥 반시계 방향입니다.

PS에서의 CCW는 세 점에 대한 방향성을 나타냅니다. 

CCW의 return 값은 보통 세가지 경우입니다.

1. 반시계 방향인 경우

2. 시계 방향인 경우

3.세 점이 평행한 경우

이렇게 세가지 경우로 분류되며 CCW는 삼각형의 면적을 구하는 공식+벡터를 이용하여 구해지게 됩니다.

해당 식에서 S가 0보다 크면 반시계 방향 

S가 0보다 작으면 시계 방향

S가 0이면 세 점이 평행합니다. 

이를 소스코드로 작성하면 아래와 같습니다.

int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    int op = a.first*b.second + b.first*c.second + c.first*a.second;
    op -= (a.second*b.first + b.second*c.first + c.second*a.first);
    if (op > 0)return 1;
    else if (op == 0)return 0;
    else return -1;
}

그렇다면 선분 교차 판별을 하기전에 CCW를 이용하여 풀 수 있는 한 문제를 소개해드리겠습니다.

https://www.acmicpc.net/problem/12781  작년 저희 학교 교내대회에 나온 문제입니다. 

문제를 간단하게 설명하면 볼록 다각형에서 주어지는 두 선분이 피자를 4등분 할 수 있는지 여부를 체크하는 문제입니다.

이 문제를 어떻게 CCW를 이용하여 풀 수 있을까요?

우선 두 선분이 피자를 4등분 하는 경우를 생각해봅시다.

다음과 같은 경우를 생각해볼 수 있을겁니다.

이를 자세히 관찰해보면 C-D 선분에서 다른 선분을 이루는 두 점인 A와 B로의 CCW를 계산해보면 이는 서로 반대 방향을 나타낼것입니다.

즉 CCW(C,D,A)와 CCW(C,D,B)의 곱이 음수인 경우 피자를 4등분 할 수 있습니다.

이 문제를 푸시고나시면 선분 교차 판별에 대한 설명이 끝났구나라고 생각하실 수도 있습니다. 하지만 방금 문제에는 볼록 다각형에 올려져 있는 네점에 대하여 CCW를 구한것이기 때문에 비교적 간단히 해결할 수 있었습니다.

하지만 그냥 2차원 평면에 있는 두 선분에 대해서라면 이와 같은 솔루션만으로는 선분 교차여부를 완벽히 구해낼 수 없습니다.

예를 들자면 이런 경우가 있을 수 있습니다.

위 그림과 같은 경우 C-D에 대한 점 A,B의 CCW를 각각 구해보면

아래 그림과 같이 서로 다른 방향을 나타내는데에도 불구하고 두 선분은 서로 교차를하지 않습니다.

그렇다면 두 선분의 선분교차를 어떻게 구해야할까요?

답은 생각보다 간단합니다. A-B선분에 대한 점 C,D의 CCW도 구해주면 됩니다.

즉 CCW(A,B,C)*CCW(A,B,D)<=0 이면서 CCW(C,D,A)*CCW(C,D,B)<=0 이면 두 선분이 교차된다고 생각할 수 있습니다.

아까 문제와는 다르게 등호가 붙게되었는데 등호가 붙는 경우(0이 되는 경우)에도 선분이 교차되어 있는 경우이기 때문에 판별을 해주어야 합니다.

자 이제 선분 교차 판별이 완벽하게 될까요 ..?

아쉽게도 아직 끝나지 않았습니다. 위의 방법에는 하나의 반례가 존재합니다.

CCW(A,B,C)*CCW(A,B,D)가 0이면서  CCW(C,D,A)*CCW(C,D,B)가 0인 경우인데요. 

그림으로 그려보자면 

이와 같은 두 선분은 CCW(A,B,C)*CCW(A,B,D)==0 && CCW(C,D,A)*CCW(C,D,B)==0 이게 됩니다.

그렇다고 이 경우를 무조건 선분교차가 아니라고 해버린다면 위의 그림에서 B와 C가 바뀐 

와 같은 경우를 판별하지 못하게됩니다. 따라서 이를 제대로 판별해주기 위하여 

CCW(A,B,C)*CCW(A,B,D)==0 && CCW(C,D,A)*CCW(C,D,B)==0 인 경우에는 b에 대한 c의 상대 위치와 d에대한 a의 상대위치를 비교해주면 됩니다.

아래는 이에 대한 소스코드 입니다. 

int isIntersect(pair<pair<int, int>, pair<int, int>> x, pair<pair<int, int>, pair<int, int>> y) {
    pair<int, int> a = x.first;
    pair<int, int> b = x.second;
    pair<int, int> c = y.first;
    pair<int, int> d = y.second;
    int ab = ccw(a, b, c)*ccw(a, b, d);
    int cd = ccw(c, d, a)*ccw(c, d, b);
    if (ab == 0 && cd == 0) {
        if (a > b)swap(a, b);
        if (c > d)swap(c, d);
        return c <= b&&a <= d;
    }
    return ab <= 0 && cd <= 0;
}

올해 2017년 ACM ICPC 대전 리저널 인터넷 예선 E번에 선분교차 여부를 판단해주어야 하는 플로우 문제가 출제되었으니 한번씩 풀어보시는 것도 좋을거 같습니다. https://www.acmicpc.net/problem/14750