선분 교차 판별 알고리즘

CCW

CCW ( Counter ClockWise, 반시계 방향 )의 약자로, CCW의 return은 세가지 방향성을 나타냄.

1. 반시계 방향 ( return 1 )

2. 시계 방향 ( return -1 )
   

3. 세 점이 평행 ( return 0 )
   

아래와 같은 수식으로 값을 구하게 됨.

$2 \times S = \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 &1\end{vmatrix} = (x_2-x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1)$

CCW를 이용한 선분 교차 판정

def ccw(a,b,c):
    op = a[0]*b[1] + b[0]*c[1] + c[0]*a[1]
    op -= (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])
    if op > 0:
        return 1
    elif op == 0:
        return 0
    else:
        return -1

def isIntersect(x,y):
    a = x[0]
    b = x[1]
    c = y[0]
    d = y[1]
    ab = ccw(a,b,c)*ccw(a,b,d)
    cd = ccw(c,d,a)*ccw(c,d,b)
    if ab ==0 and cd == 0:
        if a > b:
            a,b = b,a
        if c > d:
            c,d = d,c
        return c <= b and a <= d
    return ab <= 0 and cd <= 0