Geometry (1) - CCW & 교차 판별

이번 글부터 지금까지 공부한 기하 알고리즘들에 대해서 정리를 하고 넘어가려고 한다. 솔직히 나는 기하를 잘 못한다. 많은 사람들이 기하를 어려워 하지만, 나의 꼼꼼한 코딩을 잘 못한다는 약점이 기하의 어려운 점을 더 부각시킨다. 또한, 기본적으로 기하 알고리즘을 많이 알고 있지도 않다. 그래서 아는 기하 알고리즘들을 한 번 정리하고 넘어가려고 한다. 

기하 알고리즘?

기하 문제를 푸는 데 쓰이는 알고리즘 들이다. n차원으로 나아가기도 하지만, 보통 좌표평면 상에서 이루어지며, 점, 선 ,도형들 간의 관계, 상태를 표현하는 알고리즘들이 많다. 기본적으로 수학에서의 기하의 지식이 있으면 전체적으로 도움이 될 수 있다. 

기하 구현

모든 기하 문제는 일단 기본적으로 점을 잡고 시작한다. 보통 pair형을 사용하여 점을 표현한다. 하지만 나는 기본적으로 구조체를 좋아해서 점을 무조건 구조체로 잡는 편이다. 이처럼 코드가 좀 특이 하기도 하고, 다른 알고리즘은 몰라도 기하 부분은 내 코드가 좋은 코드라는 확신히 별로 없어 굳이 많이 참고할 이유는 없다고 생각한다. 

CCW

CCW는 counter clock wise의 줄임말으로 정보에서의 CCW 알고리즘은 세 점의 방향성을 나타내는 알고리즘이다.
세 점이 놓일 수 있는 방향성은 아래와 같이 세가지 경우가 있다.

이 세가지 의 상황은 1->2, 2->3 으로 이루어진 두 벡터의 내적 계산으로 깔끔하게 판별을 할 수 있다. 식으로는 이렇게 표현된다.

이 값의 절댓값은 넓이의 두배이기도 하지만, 지금은 그것이 중요한게 아니라 이 값의 부호가 중요하다. 이 값의 부호가 양수이면 반시계방향, 0 이면 일직선, 음수면 시계 방향이다. 

지금은 3개의 점에 대해서만 말했지만, 두 개의 벡터에 대해서도 가능하다. 

CCW 코드

ll ccw(poi a,poi m,poi b)
{
    ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
    return (t<0)-(t>0);
}
 
ll cccw(poi a,poi b,poi c,poi d){
    d.x-=(c.x-b.x);
    d.y-=(c.y-b.y);
    return ccw(a,b,d);
}

3번째 줄은 위의 식을 좀 더 깔끔하게 다듬은 식이고, 4번째 줄은 3가지 경우를 나누는 잔기술이다.
반시계면 1, 일직선이면 0, 시계면 -1을 반환하게 된다. 

기하의 기초이기 때문에 무조건 알고 들어가야 한다.

선분 교차 판별

두 개의 선분이 교차하는지를 아는 것도 기하 문제에서 쓰이고는 한다. 그럼 두 개의 선분이 교차하지 않을 때와 교차할 때의 특징을 살펴보자.  

교차하지 않는 왼쪽의 두 그림은 어떤 선분을 기준으로 나머지 두 개의 점이 모두 한 쪽에 있다는 것을 알 수 있다. 하지만 교차하는 경우에는 어떤 선분을 기준으로 잡아도 나머지 두 개의 점이 양쪽에 있다.
이는 CCW로 바로 확인이 가능하며, 따라서 선분 교차 판별은 CCW로 쉽게 해낼 수가 있다. 

이때 ccw(a,b,c)*ccw(a,b,d)와 ccw(c,d,a)*ccw(c,d,b)가 둘 다 0 이하 인가? 로 판별한다. 하지만 이 경우 예외가 한 가지 존재하게 된다. 

둘 다 0 이지만, 겹치지 않고 일직선상에 있는 경우이다. 따라서 예외 처리를 통해서 이 경우만 제외해주면 된다. 

코드

struct poi{
    ll x,y;
      bool operator <(const poi &t) const {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
 
ll ccw(poi a,poi m,poi b)
{
    ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
    return (t<0)-(t>0);
}
 
bool cross(lin a,lin b)
{
    if(ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)==0&&ccw(b.f,b.s,a.f)*ccw(b.f,b.s,a.s)==0)
        return !(max(a.f, a.s)<min(b.f,b.s)||max(b.f, b.s)<min(a.f,a.s));
    return ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)<=0&&ccw(b.f,b.s, a.f)*ccw(b.f,b.s,a.s)<=0;
}