概要

線分\(P_0-P_1\)と線分\(Q_0-Q_1\)が交差しているかを外積と内積を用いて判定する。

外積で線分の交差を判定し、線分が一直線に並んでいる場合に内積で判定する。

実装

AOJ: "CGL_2_B: Segments/Lines - Intersection"で提出した実装

# 線分同士の交点判定
def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    return C0 * C1 <= 0 and D0 * D1 <= 0
for q in range(int(input())):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())
    print(+is_intersection((x0, y0), (x1, y1), (x2, y2), (x3, y3)))

Verified

  • AOJ: "CGL_2_B: Segments/Lines - Intersection": source (Python3, 0.02sec)