선분 교차

두 선분이 공통으로 포함하는 점이 존재한다면, intersect 한다고 한다. 이것은 crossing, touching, overlapping을 모두 포함한다.

* 코드: teflib.geometry.is_crossing

똑같이 4번의 CCW 연산의 결과를 이용해서 위치 관계를 구할수 있다.

관련문제: 17387

코드: teflib.geometry.is_intersecting

가독성면에서는 cross 프로덕트, 또는 is_ccw 함수를 따로 빼는것이 좋지만, python에서는 함수 호출을 4번이나 하는것이 속도면에서 너무 손해가 크다.. 그냥 인라이닝하자.

모든 점이 non-collinear하다는 조건이 없으면 intersecting 여부를 체크하기 위해 teflib.geometry.is_intersecting를 사용한다

모든 점이 non-collinear하다면 crossing하는지만 체크하면 된다. teflib.geometry.is_crossing을 써서 좀더 컴팩트하게 쓸수 있게 하자.

가능한 위치 관계를 전부 enum으로 만들어서 리턴해주는 함수도 고민했지만, 거기까지는 그다지 필요없어서 제외했다. 이 외의 케이스를 체크해야 한다면.. (overlapping 여부를 찾는다든가..) 그때그때 구현해서 쓰자.

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