[알고리즘] ccw와 선분교차 판정

CCW(Counter-Clockwise) 알고리즘

 

CCW는 벡터의 외적을 이용하여 한 선분에 대하여 한 점의 위치 관계를 파악하는 알고리즘을 말합니다.

직선 AB에 대하여 점 C의 위치 관계 서술한다면 AB벡터와 AC벡터의 외적 값의 부호를 통해 알 수 있습니다. 그리고 이러한 위치 관계를 통해 기하에서 다양한 것들을 할 수 있습니다.

 

※ 벡터의 외적과 방향성

오른손의 법칙을 통해 AB벡터로 손을 가르킨 후 점 C의 방향으로 손을 감을 때 엄지손가락이 위로 가면 반시계 ( 외적값이 + ) 반대로 아래로 가면 시계방향 ( 외적값이 - ) 로 나타납니다. 

 

int ccw(pii v1, pii v2, pii v3)
{
    ll val = (v2.first-v1.first) * (v3.second-v1.second) - (v2.second-v1.second) * (v3.first - v1.first);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}

 

시점이 v1인 방향 벡터를 구하기 위해서 기존 벡터에서 v1벡터를 뺀 후 계산했습니다. 그리고 문제마다 다르겠지만 해당 함수에서 long long int 로 return하고 나중에 그 값을 연산에 사용할 때가 많은데요, 이 때 주의할 점은 때때로 long long int 의 범위를 넘어갈 수도 있다는 사실입니다. 따라서 저는 부호에 따라 따로 값을 return 했습니다.

 

선분교차 판정

 

일단 교차한다는 사실은 대~충 생각해보면 한 선분에 대하여 다른 선분의 점들이 한 개는 왼쪽, 한 개는 오른쪽에 있으면 되지 않을까? 라고 생각해보죠. (일단은요)

 

일단 주의할 점은 ccw는 선분이 아니라 직선에 대해서 다른 점의 위치를 판정한다는 사실입니다. 따라서 오른쪽과 같은 모습을 볼 수 있는데요, 확실히... 초록색 선에 대해서 하늘색의 두 점은 서로 다른 위치 관계이지만, 초록색 선의 점들은 하늘색 선에 대해서 한 쪽 방향에만 존재한다는 사실을 알 수 있습니다. 

 

// 초록색 선분을 Green
// 하늘색(파란색) 선분을 Blue 라고 칭할 때 
// 시작점의 위치를 s 끝 점의 위치를 e 라고 하자

ccw(Green.s, Green.e, Blue.s) * ccw(Green.s, Green.e, Blue.e) < 0
ccw(Blue.s, Blue.e, Green.s) * ccw(Blue.s, Blue.e, Green.e) < 0

두 식을 동시에 만족한다면 위와 같은 상황을 판별할 수 있다.

 

그런데 한 선분의 점이 다른 선분 위에 존재할 경우도 있습니다. 아래의 그림처럼 말이죠,,

 

위에 식에서 위치 관계가 오른쪽 / 왼쪽으로 다른 것을 판별하기 위해 ccw값을 곱한 값이 음수임을 확인했었는데, 방향이 같다면 0이 되므로 미만이 아니라 이하로 (등호 추가) 바꾸면 일단 괜찮아질 것 같습니다. 

// 초록색 선분을 Green
// 하늘색(파란색) 선분을 Blue 라고 칭할 때 
// 시작점의 위치를 s 끝 점의 위치를 e 라고 하자

ccw(Green.s, Green.e, Blue.s) * ccw(Green.s, Green.e, Blue.e) <= 0
ccw(Blue.s, Blue.e, Green.s) * ccw(Blue.s, Blue.e, Green.e) <= 0

두 식을 동시에 만족한다면 위와 같은 상황을 판별할 수 있다.

 

 

이걸로 끝나면 좋겠지만... ccw는 절대로 선분에 관한 것이 아니라 방향, 즉 직선에 관한 위치 판정입니다... 식을 저렇게 쓴다면 

 

 

위와 같은 상황을 판단하지 못합니다. 그래서 저는 ccw를 생각할 때 선분이지만 일단 직선으로 확장하여 생각합니다. 암튼 그렇다면 이런 경우엔 한 개의 선분에 대하여 다른 선분의 점이 포함되는지 확인해주면 됩니다. 

// 초록색 선분을 Green
// 하늘색(파란색) 선분을 Blue 라고 칭할 때 
// 시작점의 위치를 s 끝 점의 위치를 e 라고 하자
// s <= e 를 만족한다 ( = e는 s보다 오른쪽에 존재, 만약 x좌표가 같다면 위에 존재)
int a = ccw(Green.s, Green.e, Blue.s), b = ccw(Green.s, Green.e, Blue.e);
int c= ccw(Blue.s, Blue.e, Green.s), d = ccw(Blue.s, Blue.e, Green.e);

만약 a * b <= 0 이고 c * d <= 0 이면
{
	만약 a * b == 0 이고 c * d == 0 이면
    {
    	만약 Green.s >= Blue.s 라면 -> Green과 Blue을 바꾼다.
        return Blue.s 가 Green.s 와 Green.e 사이에 있는가?
    }
    return 교차함
}

return 교차 안함

 

이를 고려하여 의사 코드를 만든다면 아래 처럼 나타난다. 그렇다면 아래 문제를 풀어보고 만약 안된다면 아래 코드를 참고하고 어디가 틀렸고 왜 틀렸는지 비교하여 공부봅시다!

 

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

 

코드

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define pii pair<ll,ll>
#define dou long double
#define pdd pair<dou, dou>

pii as, ae, bs, be;

ll ccw(pii v1, pii v2, pii v3) 
{
    ll val =(v2.first - v1.first) * (v3.second - v1.second) - (v2.second - v1.second) * (v3.first - v1.first);

    /// ccw 값을 곱하는 연산으로 오버플로우 발생할 수 있음

    /// 따라서 값을 넘기지 않고 부호만 넘김
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0; 
}

bool is_intersect()
{
    ll a = ccw(as, ae, bs), b = ccw(as, ae, be);
    ll c = ccw(bs, be, as), d = ccw(bs, be, ae);
    if(a * b <= 0 && c * d <= 0){
        if(as > bs) {swap(as, bs); swap(ae, be);} /// s점 뿐만 아니라 e점도 swap
        if(a*b == 0 && c*d == 0)
            return as <= bs && bs <= ae;
        return 1;
    }
    return 0;
}

int main()
{
    cin >> as.first >> as.second >> ae.first >> ae.second;
    cin >> bs.first >> bs.second >> be.first >> be.second;
    if(as > ae) swap(as, ae); /// 시작점이 끝점보다 왼쪽에 존재하게끔... 
    if(bs > be) swap(bs, be);
    if(is_intersect()) cout << "1";
    else cout << "0";
}

 

직선의 방정식을 통한 교차 판정의 문제점

 

사실 CCW말고도 직선의 방정식으로도 판정할 수 있긴 한데요... 이를 사용하지 않는 큰 이유 중 첫 번째는 예외가 너무 많다는 사실입니다... x = a 만 해도 직선의 방정식으로 나타낼 수 없습니다. 그리고 두 번째는 실수오차가 발생할 수도 있기 때문입니다.  그에 비해 ccw는 구현도 간단하고 예외도 간단히 처리할 수 있습니다.

 

 

예전에 공부할 땐 그냥 문제를 풀기 위해서 ccw식을 외웠는데요.. 지금 다시 공부하면서 ccw가 어떤 의미인지 이해하니 활용도 가능하고 바로 유도가 가능하네요. 앞으로의 알고리즘 포스팅은 이해와 유도를 기반으로 진행하겠습니다.