[Python] 20149 선분 교차 3 - 외적이 아닌 직선의 방정식으로

 선분 교차여부를 따질 때 흔히 외적을 사용해 회전 방향으로 체크하곤 한다.

그런데 이 방법은 교점을 1개만 갖고 있는 경우를 구분하기가 상당히 까다롭다.

그래서 아예 직선의 방정식을 구해 교점을 구한 뒤 선분 위에 있는지 체크하였다.

1. 전처리

점의 위치가 무작위로 주어지기 때문에 사전식으로 정렬하여 경우의 수를 축소하였다.

ax,ay,bx,by=I()
cx,cy,dx,dy=I()

A=(ax,ay)
B=(bx,by)
C=(cx,cy)
D=(dx,dy)
if A>B:A,B=B,A
if C>D:C,D=D,C

2. 직선의 위치관계 판단

직선으로 경우의 수를 나눌 경우 매우 좋은 점이 바로 위치관계가 단순하다는 것이다.

• 평행 : 기울기가 같다. 
  $\Delta x_{\overline{AB}}=bx-ax ,\Delta y_{\overline{CD}}=dx-cx, ...$으로 각 선분의 양 꼭지점의 x변화량, y변화량을 의미한다.
  $$ \frac{\Delta y_{\overline{AB}}}{\Delta x_{\overline{AB}}} = \frac{\Delta y_{\overline{CD}}}{\Delta x_{\overline{CD}}}$$
  위 식을 정수 연산으로 바꾸기 위해 기울기 비교 식을 다음 처럼 식을 변형했다.

# 평행 여부 확인하기
p=dx1*dy2-dy1*dx2

• 일치 : 기울기가 같고 절편이 같다. 절편도 마찬가지로 직선의 방정식에 대입하여 구한 뒤 정수 연산으로 바꾸어줬다.
  앞에서 전처리를 했기 때문에 한 점에서만 선분이 정확히 만나는 경우는 A=D, B=C 단 2가지이다. 이 경우 교점을 각각 A,B로 잡아 줬다.
  직선이 일치하지만 선분은 서로 떨어져 있을 수 있는데
  이 때 판단은 C<=B and A<=D 일 경우 겹친 것이고 그렇지 않을 경우 떨어진 것으로 판단 할 수 있다. 

# 절편이 같다면
if dx1*dx2*cy-dx1*dy2*cx==dx1*dx2*ay-dx2*dy1*ax :
	t=2
    # 끝점 일치
	if A==D : x,y=A
	elif B==C : x,y=B
    # 그렇지 않은 경우는 겹치거나 동떨어진 경우 뿐이다.
	else : t=3 if C<=B and A<=D else 0

• 한 점에서 만남: 기울기가 다르다. 이 경우 직선의 교점을 수식으로 구해주었다.
  이 경우 주의사항이 한 선분이 x축이나 y축에 수직할 경우 int값으로 바꿔줘야 나중에 선분 안에 있는지 체크할 때, 정상적인 대소 비교가 된다.

# 교점 구하기
p=dx1*dy2-dy1*dx2
x=(ab*dx2-dx1*cd)/p
y=(ab*dy2-dy1*cd)/p

3. 선분 내 교점 존재여부 판단

앞에서 교점이 구해졌다면 이 교점이 선분 내 교점인지 체크해야한다. 전처리 했지만 y좌표는 대소가 맞지 않으므로 아래와 같이 다시 처리 후 체크한다. 이때 조심할 점은 교점을 모두 구한 뒤 y 좌표값의 순서를 바꿔야한다는 점이다.

if ay > by : ay, by = by, ay
if cy > dy : cy, dy = dy, cy
def on_segment(x,y) : return ax<=x<=bx and ay<=y<=by and cx<=x<=dx and cy<=y<=dy

4. 마무리

• 앞에서 교점이 있었던 경우는 t=1로 체크해 선분 내 교점이 있는지 체크하여 만나는지 확인을 한 뒤 1과 교점을 출력
  on_segment(x,y)의 값이 0이면 넘어가도록 함
• 일치했던 경우는 끝점만 일치할 경우를 t=2로 체크해놓고 1과의 교점을 출력
• 겹쳤던 경우는 t=3으로 체크해 놓고 1만을 출력
• 그 외 경우는 모두 만나지 않으므로 0만을 출력

if (t==1 and on_segment(x,y)) or t==2:print(1,x,y)
elif t==3: print(1)
else:print(0)

 

*치팅을 막기 위해 코드 전문은 올리지 않았습니다.