두 선분의 교차 판정(2), CW/CCW, python

두 선분의 교차 판정(1), python

두 선분의 교차 판정(1), python

 

이전글에서는 매개변수 방정식을 이용해서 두 선분이 교차하는지를 판별했다.

벡터의 외적을 이용해서 선분 교차를 판별하는 방법도 있다. 

 

 

 

 

벡터의 외적을 통한 CCW(반시계 방향), CW(시계방향) 판별 방법

 

A, B, C 세 점이 있을때 벡터 \(\vec{AB}\)와 벡터 \(\vec{AC}\)의 외적 \(\vec{AB}\times \vec{AC}\)의 부호를 통해 A, B, C가 시계방향인지, 반시계방향인지를 알 수 있다.

 

 

 

벡터의 외적을 통해 회전 축의 방향을 알 수 있다.

2차원에서 벡터의 외적은  \(\vec{A} = (a,b) \) \(\vec{B} = (c,d) \) 일때  \(\vec{A}\times \vec{B} = ad-bc \)로 정의된다.

 

 

 

 

 

 

 

 

\(\vec{AB}\times \vec{AC}>0\)의 경우 점 A, B, C는 반시계 방향으로 놓이게 된다. 이 경우를 CCW(counter clockwise)라고 한다.

 

 

\(\vec{AB}\times \vec{AC}<0\)의 경우는 A, B, C는 시계방향으로 놓이게 된다. CW(clockwise)라고 한다.

 

 

\(\vec{AB}\times \vec{AC}=0\)이라면 A, B, C가 한 직선 위에 있게 된다.

 

 

벡터의 외적을 통한 CW/CCW 판별은 선분 교차 뿐만 아니라 볼록 껍질(convex hull)문제, 다각형 내부와 외부 판별등 2차원 기하학에서 자주 쓰인다..

 

 

 

CCW, CW를 통한 선분 교차여부 판별

 

이제 벡터의 외적을 통해 세 점이 시계방향인지, 반시계방향인지를 구하여 선분 교차여부를 판별할 수 있다.

 

 

 

 

두 선분이 교차할때, \(\vec{CD}\) 기준으로 A는 오른쪽, B는 왼쪽에 위치해야 한다.

\(\vec{AB}\) 기준으로 C는 왼쪽, D는 오른쪽에 위치해야 한다.

 

 

 

 

 

 

 

 

점 C, D, A는 시계방향으로 놓여져야 하고 C, D, B는 반시계방향으로 놓여져야 한다.

\((\vec{CD}\times \vec{CA})( \vec{CD}\times \vec{CB})\leq 0\) 이 된다.

 

 

 

 

 

 

점 A, B, C는 반시계방향으로 놓여져야 하고 A, B, D는 시계방향으로 놓여져야 한다.

\((\vec{AB}\times \vec{AC})(\vec{AB}\times \vec{AD})\leq 0\) 이 된다.

 

 

 

 

 

 

 

\(\vec{AB}\times \vec{AC}=\vec{AB}\times \vec{AD}=\vec{CD}\times \vec{CA}=\vec{CD}\times \vec{CB}=0 \) 인 경우에 

\( \vec{AB} 와 \vec{CD} \) 가 평행하면서 교차하게 된다.

 

이 경우 매개변수 방정식과 같은 방식으로 x축, y축에 투영하여 오른쪽 선분의 왼쪽점과 왼쪽 선분의 오른쪽 점의 위치를 비교해주면 된다. 

.

 

 

 

 

python 구현

 

Ax,Ay,Bx,By = map(int, input().split())
Cx,Cy,Dx,Dy = map(int, input().split())

A=(Ax,Ay);B=(Bx,By);C=(Cx,Cy);D=(Dx,Dy)

# 외적 결과값이 양수면 CCW, 음수면 CW
def ccw(p1, p2, p3):
    a,b = p2[0]-p1[0], p2[1]-p1[1]
    c,d = p3[0]-p1[0], p3[1]-p1[1]
    return a*d-b*c

 

A,B,C / A,B,D / C,D,A / C,D,B 가 CW인지 CCW인지를 구하기 위해 외적을 계산하는 함수를 구현한다.

 

 

 

# C,D,A와 A,B,D는 CW, C,D,B와 A,B,C는 CCW
CDA = ccw(C,D,A); CDB = ccw(C,D,B)
ABD = ccw(A,B,D); ABC = ccw(A,B,C)

if CDA==CDB==ABD==ABC==0:
    # x축에 우선 투영, x값이 같다면 y축에 투영
    if max(min(A,B),min(C,D)) <= min(max(A,B),max(C,D)):
        print(1)
    else:
        print(0)
elif CDA*CDB<=0 and ABD*ABC<=0:
    print(1)
else:
    print(0)

 

외적이 모두 0이면 두 선분이 한 직선 위에 있는 경우이므로 x축, y축 투영을 해서 점의 위치를 비교해준다.

외적의 곱을 계산하여 0보다 작거나 같으면 교차한다.