본문 바로가기

알고리즘 관련/알고리즘&이론

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

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


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


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


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


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


1. 반시계 방향인 경우



2. 시계 방향인 경우



3.세 점이 평행한 경우




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


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


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


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


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


1
2
3
4
5
6
7
int ccw(pair<intint> a, pair<intint> b, pair<intint> 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;
}
cs


그렇다면 선분 교차 판별을 하기전에 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의 상대위치를 비교해주면 됩니다.


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isIntersect(pair<pair<intint>, pair<intint>> x, pair<pair<intint>, pair<intint>> y) {
    pair<intint> a = x.first;
    pair<intint> b = x.second;
    pair<intint> c = y.first;
    pair<intint> 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 == && cd == 0) {
        if (a > b)swap(a, b);
        if (c > d)swap(c, d);
        return c <= b&&<= d;
    }
    return ab <= && cd <= 0;
}
cs





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

'알고리즘 관련 > 알고리즘&이론' 카테고리의 다른 글

advanced disjoint set  (2) 2018.06.24
좌표압축 기법  (1) 2017.09.19
deque를 이용한 다이나믹프로그래밍  (0) 2017.09.05
L-R flow  (0) 2017.08.15
트리에서 A와 B의 경로 사이에 C존재 여부  (0) 2017.07.11