[C++] 선분 교차 판정

선분 교차 판정이란 말 그대로 두 선분이 교차하는지 아닌지 판정하는 것이다. 선분 교차 판정을 효율적으로 하기 위해서는 CCW(또는 signed area)에 대한 지식이 필요하다.

CCW(또는 signed area)란? 세 점 A, B, C에 대하여 선분 BC가 AB에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지 판정하는 것으로, 2차원에서 determinant의 개념을 응용하는 기술이다. 두 2차원 벡터 u, v의 determinant는 2가지 정보를 담고 있다. 그 절댓값은 두 벡터 u, v가 생성하는 평행사변형의 넓이를 알려주고, 그 부호는 v가 u에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지를 알려준다(+: 반시계, -: 시계). PS계에서는 CCW라는 이름이 널리 알려져 있지만, 나는 김홍종 교수님(근본임)께 signed area라고 배웠다.

그러면 이걸 가지고 선분 교차를 어떻게 판정할 수 있을까? 선분 P1-P2와 Q1-Q2에 대하여 다음과 같이 경우의 수를 나눠 본다.

1. P1, P2 중 하나와 Q1, Q2 중 하나가 일치한다면, 당연히(…) 선분은 교차한다. (선분의 양끝이 만나는 것도 교차하는 것이다)
2. 네 점 중 일직선 위에 있는 세 점이 하나도 없다면, 선분이 교차할 필요충분조건은 다음 넷 중 하나이다.
   • P1, Q1, P2, Q2가 이 순서대로 시계 방향
   • P1, Q1, P2, Q2가 이 순서대로 반시계 방향
   • P1, Q2, P2, Q1이 이 순서대로 시계 방향
   • P1, Q2, P2, Q1이 이 순서대로 반시계 방향
3. 그런데 시계/반시계를 판정하는 법은 우리가 이미 알고 있다. CCW 공식을 갖고 이리저리 돌려 보면, 주어진 조건은 결국 다음 조건과 동치임을 알 수 있다.
   • CCW(P1, Q1, P2) * CCW(P2, Q2, P1) > 0 && CCW(Q1, P2, Q2) * CCW(Q2, P1, Q1) > 0
4. 네 점 중 세 점만 일직선 위에 있다면, 4개의 CCW 중 2개는 0이고 2개는 0이 아니며 이 둘의 부호가 같다. 따라서 2번과 합치면 다음 조건을 얻을 수 있다.
   • CCW(P1, Q1, P2) * CCW(P2, Q2, P1) >= 0 && CCW(Q1, P2, Q2) * CCW(Q2, P1, Q1) >= 0
5. 네 점 모두 일직선 위에 있다면, 4개의 CCW 값이 모두 0이다. 이 때는 CCW 같은 마법의 공식이 없다. 순전히 일직선 위에 있다는 정보만 이용해서 선분이 교차하는지 아닌지 판정해야 한다. 선분은 교차할 수도 아닐 수도 있다. 예를 들어 점이 P1, Q1, P2, Q2 순서로 놓여 있다면 교차하고, P1, P2, Q1, Q2 순서대로 놓여 있다면 교차하지 않는다.

class Point {
public:
    long long x, y;
    Point(long long _x, long long _y) : x(_x), y(_y) {}
    Point operator-(const Point& rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    bool operator<(const Point& rhs) const {
        // return y / x < rhs.y / rhs.x
        return y * rhs.x < x * rhs.y;
    }
    bool operator==(const Point& rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

long long signed_area(const Point& a, const Point& b, const Point& c) {
    // return det
    Point v1 = b - a, v2 = c - b;
    return v1.x * v2.y - v2.x * v1.y;
}

bool segment_sect(const Point& p1, const Point& p2, const Point& q1, const Point& q2) {
    /*
        #p1
      #q1    #q2
        
         #p2
     */
    if (p1 == q1 || p1 == q2 || p2 == q1 || p2 == q2) {
        return true;
    }
    
    long long s1 = signed_area(p1, q1, p2);
    long long s2 = signed_area(q1, p2, q2);
    long long s3 = signed_area(p2, q2, p1);
    long long s4 = signed_area(q2, p1, q1);
    
    // unify
    s1 = s1 > 0 ? 1 : s1 < 0 ? -1 : 0;
    s2 = s2 > 0 ? 1 : s2 < 0 ? -1 : 0;
    s3 = s3 > 0 ? 1 : s3 < 0 ? -1 : 0;
    s4 = s4 > 0 ? 1 : s4 < 0 ? -1 : 0;
    
    if (s1 * s3 == 0 && s2 * s4 == 0) {
        // Exception case
        auto __cmp__ = [](const Point& lhs, const Point& rhs) -> bool {
            return lhs.y < rhs.y ? true : lhs.y > rhs.y ? false : lhs.x < rhs.x ? true : false;
        };
        return !((__cmp__(p1, q1) ^ __cmp__(q1, p2)) && (__cmp__(p1, q2) ^ __cmp__(q2, p2)) && (__cmp__(q1, p1) ^ __cmp__(p1, q2)) && (__cmp__(q1, p2) ^ __cmp__(p2, q2)));
    } else if (s1 * s3 >= 0 && s2 * s4 >= 0) {
        return true;
    } else {
        return false;
    }
}