[2D]두 직선의 교점 구하기

 

2D상의 A,B를 지나는 직선과 C,D를 지나는 직선의 교점을 구하는 방정식을 구해보도록 합시다.

$$\begin{eqnarray} l_1&=A+(B-A)\times t_1 \\ l_2&=C+(D-C)\times t_2 \\ A+(B-A)\times t_1 &= C+(D-C)\times t_2\end{eqnarray}$$

두 직선은 교점은 위의 방정식을 통하여 구할 수 있습니다.

이 방정식을 풀어보도록 합시다.

위 방정식은 2개의 변수를 가지고 있으므로 2개의 식이 있어야만 방정식을 풀수 있습니다.

따라서 이 방정식을 매개변수 $x,y$에 대해서 풀어보면,

$$\begin{eqnarray} A_x+(B_x-A_x)\times t_1 &= C_x+(D_x-C_x)\times t_2 \\ A_y+(B_y-A_y)\times t_1 &= C_y+(D_y-C_y)\times t_2\end{eqnarray}$$

(4)번 식에서 $t_2$를 구해 (5)번 식에 대입하면,

$$\begin{eqnarray} A_y+(B_y-A_y)\times t_1 &=& C_y+(D_y-C_y)\times \frac{(A_x-C_x)+(B_x-A_x)\times t_1}{(D_x-C_x)} \\ (A_y-C_y)*(D_x-C_x) &=& (D_y-C_y)*(A_x-C_x)+((B_x-A_x)*(D_y-C_y)-(B_y-A_y)*(D_x-C_x))\times t_1 \\ t_1 &=& \frac{(A_y-C_y)*(D_x-C_x)-(A_x-C_x)*(D_y-C_y)}{(B_x-A_x)*(D_y-C_y)-(B_y-A_y)*(D_x-C_x)}\end{eqnarray}$$

이렇게 해서 $t_1$를 구했습니다.

만일 분모가 0이 되면 $t_1$을 구할 수가 없게 되고 따라서 교차점도 구할 수 없습니다.
(두 직선이 평행할 경우)

$$(B_x-A_x)*(D_y-C_y)-(B_y-A_y)*(D_x-C_x)=0$$

이렇게 구한 $t_1$을 점 A,B를 지나는 직선의 매개 방정식에 넣으면 교차점을 구할 수 있습니다.

$$P=A+(B-A)\times t_1$$

만일 $0<=t_1<=1$일 경우에는 선분 A,B사이에 교차점이 존재하고,

그렇지 않을 경우에는 선분 A,B 외부에 교차점이 존재하게 됩니다.