직선의 교점 찾기

Point
P1 = (x1, y1)
P2 = (x2, y2)
P3 = (x3, y3)
P4 = (x4, y4)

Line

Line1 = (P1, P2) = P(t) = (1-t)P1 + tP2
Line2 = (P3, P4) = P(s) = (1-s)P3 + sP4


intersection point

(1-t)P1 + tP2 = (1-s)P3 + sP4

x,y로 분할

(1-t)x1 + tx2 = (1-s)x3 + sx4
x1 - tx1 + tx2 = x3 -sx3 + sx4
x1 + t(x2 - x1) = x3 + s(x4 - x3)


(1-t)y1 + ty2 = (1-s)y3 + sy4
y1 - ty1 + ty2 = y3 -sy3 + sy4
y1 + t(y2 - y1) = y3 + s(y4 - y3)


x1 + t(x2 - x1) = x3 + s(x4 - x3)
y1 + t(y2 - y1) = y3 + s(y4 - y3)



x1 + t(x2 - x1) = x3 + s(x4 - x3)
t(x2 - x1) + (x1 - x3) = s(x4 - x3)
s = (t(x2 - x1) + (x1 - x3))/(x4 - x3)



y1 + t(y2 - y1) = y3 + s(y4 - y3)
t(y2 - y1) + (y1 - y3) = s(y4 - y3)
s = (t(y2 - y1) + (y1 - y3))/(y4 - y3)



(t(x2 - x1) + (x1 - x3))/(x4 - x3) = (t(y2 - y1) + (y1 - y3))/(y4 - y3)


(t(x2 - x1)(y4 - y3) + (x1 - x3)(y4 - y3))/(x4 - x3)(y4 - y3)
= (t(x4 - x3)(y2 - y1) + (x4 - x3)(y1 - y3))/(x4 - x3)(y4 - y3)




 
 t(x2 - x1)(y4 - y3) + (x1 - x3)(y4 - y3)
 = t(x4 - x3)(y2 - y1) + (x4 - x3)(y1 - y3)

 
 t(x2 - x1)(y4 - y3) - t(x4 - x3)(y2 - y1)
 = (x4 - x3)(y1 - y3) - (x1 - x3)(y4 - y3)
 

 t((x2 - x1)(y4 - y3) - (x4 - x3)(y2 - y1))
 = (x4 - x3)(y1 - y3) - (x1 - x3)(y4 - y3)
 
 
 
 
 
t =
(x4 - x3)(y1 - y3) - (x1 - x3)(y4 - y3)
---------------------------------------
(x2 - x1)(y4 - y3) - (x4 - x3)(y2 - y1)


s = (t(x2 - x1) + (x1 - x3))/(x4 - x3)

 
 
(x2 - x1)(y4 - y3) - (x4 - x3)(y2 - y1) 가 0이 아니고

0 <= t,s <= 1 를 만족하면

교점이 있다.!