====== 선분 교차 ======

  * 선분의 교차 여부는 세 점의 방향성을 이용해서, 실수 연산 없이 구하는 것이 가능하다.

===== 세 점의 위치 관계 =====
  * 세 점 p1, p2, p3의 위치 관계는 벡터의 외적을 이용해서 구할수 있다.
  * (p2-p1)벡터와 (p3-p1)벡터의 외적을 구한 값이, 양수이면 시계방향(CW), 음수이면 반시계방향(CCW), 0이면 일직선상(collinear)으로 놓여져있는 것이다.

===== 두 선분의 위치 관계 =====
  * p1,p2를 양 끝점으로 갖는 선분 l1과 p3,p4를 양 끝점으로 갖는 선분 l2가 있을때의 두 선분의 위치관계를 생각하자.
  * 먼저 용어부터 정리하자.
    * 두 선분이 공통으로 포함하는 점이 존재한다면, intersect 한다고 한다. 이것은 crossing, touching, overlapping을 모두 포함한다.
  * 우선 간단하게, 4점이 모두 non-collinear 할 경우를 생각하자. 이때에 가능한 위치관계는 교차하던가(crossing) 떨어져있던가(disjoint) 두가지 밖에 없다. 
    * CCW 연산을 4번 사용해서 위치 관계를 구할수 있다.
      * l1선분을 기준으로 p3과 p4의 방향성이 반대이고 l2선분을 기준으로 p1과 p2의 방향성이 반대이면 교차하고, 그 외에는 교차하지 않는다.
    *     * 코드: [[:ps:teflib:geometry#is_crossing|teflib.geometry.is_crossing]]
  * 이제, collinear한 점들이 있을 경우를 생각하자.
    * 똑같이 4번의 CCW 연산의 결과를 이용해서 위치 관계를 구할수 있다.
    * 그러나 한 끝점이 다른 선분에 터칭하는 경우, 두 끝점이 같은 경우, 선분의 일부가 겹치는 경우 등등을 처리해야 한다. 막 어려운건 아닌데, 코드가 길어지고 실수하기 쉽다.
      * 다행하게도.. 모든 점이 non-collinear하다는 조건을 주는 문제가 많이 있어서.. 이것들을 실제로 전부 처리할 경우가 많지는 않다.
    * 관련문제: [[ps:problems:boj:17387]]
    * 코드: [[:ps:teflib:geometry#is_intersecting|teflib.geometry.is_intersecting]]
  * 구현
    * 가독성면에서는 cross 프로덕트, 또는 is_ccw 함수를 따로 빼는것이 좋지만, python에서는 함수 호출을 4번이나 하는것이 속도면에서 너무 손해가 크다.. 그냥 인라이닝하자.
    * 모든 점이 non-collinear하다는 조건이 없으면 intersecting 여부를 체크하기 위해 [[:ps:teflib:geometry#is_intersecting|teflib.geometry.is_intersecting]]를 사용한다
    * 모든 점이 non-collinear하다면 crossing하는지만 체크하면 된다. [[:ps:teflib:geometry#is_crossing|teflib.geometry.is_crossing]]을 써서 좀더 컴팩트하게 쓸수 있게 하자.
    * 가능한 위치 관계를 전부 enum으로 만들어서 리턴해주는 함수도 고민했지만, 거기까지는 그다지 필요없어서 제외했다. 이 외의 케이스를 체크해야 한다면.. (overlapping 여부를 찾는다든가..) 그때그때 구현해서 쓰자.


===== 두 선분의 교점 =====
  * 어쩔수 없이 실수 연산이 필요하다. 처리할 케이스도 엄청 많아서 지저분하다.
  * 우선 CCW를 이용해서 교차 여부를 체크하고, 교차하는 경우에만 계산하는것이 그나마 좀 간단하다.
  * 계산은 공식대로 하면 된다만.. 아래 코드가 [[https://cp-algorithms.com/geometry/segments-intersection.html]]보다 더 간단하다.
  * 코드는 이런식..
    * <dkpr py>
DISJOINT = 0
OVERWRAPPING = 1


def intersect_point(x1, y1, x2, y2, x3, y3, x4, y4):
    if not geometry.is_intersecting(x1, y1, x2, y2, x3, y3, x4, y4):
        return DISJOINT

    denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if denom:
        t1, t2 = x1 * y2 - y1 * x2, x3 * y4 - y3 * x4
        x = ((x3 - x4) * t1 - (x1 - x2) * t2) / denom
        y = ((y3 - y4) * t1 - (y1 - y2) * t2) / denom
        return (x, y)
    else:
        p1, p2, p3, p4 = sorted([(x1, y1), (x2, y2), (x3, y3), (x4, y4)])
        return p2 if p2 == p3 else OVERWRAPPING
</dkpr>
  * 관련 문제: [[ps:problems:boj:20149]]