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

선분 교차 판정이란

점 A, 점 B를 양 끝으로 하는 선분 AB와 점 C, 점 D를 양 끝으로 하는 선분 CD가 최소 1개 이상의 공통점을 가지는 경우를 두 선분이 교차한다고 말한다.

 

 

 

첫번째 그림과 같이 한 점에서 공통점을 가지는 경우, 두번째와 세번째와 같이 공통점이 여러개인 경우도 있다.

 

 

 

 

 

 

두 선분의 공통점이 없는경우 교차하지 않는다고 한다.

 

 

 

 

선분의 교차 여부를 판별하는데는 두가지 방법이 있다.

첫번째 방법은 각 선분을 매개변수 방정식으로 변환하여 두 방정식의 연립방정식의 해를 구하는 것이다.

두번째 방법은 벡터의 외적을 사용하여 판별할수 있다.

 

 

 

 

매개변수 방정식을 통해 교차여부 판별

 

점 A\((x_{1},y_{1})\)과 점 B\((x_{2},y_{2})\)을 양끝으로 하는 선분AB가 있다.

매개변수 방정식이란 이 선분위의 x,y좌표를 매개변수 t를 이용해서 표현하는 것이다.

 

 

 

이 선분 위의 점의 x좌표는 \( x = x_{1}+t(x_{2}- x_{1}), 0\leq t\leq 1\) 으로 표현할 수 있다.

 

 

마찬가지로 y좌표는 \( y = y_{1}+t(y_{2}- y_{1}),0\leq t\leq 1\) 으로 표현할 수 있다.

 

 

 

 

 

 

 

점 A\((A_{x},A_{y})\)와 점 B\((B_{x},B_{y})\)를 양 끝 으로 하는 선분 AB를 매개변수 s를 이용하여 표현하게 되면

$$ x = A_{x}+s(B_{x}-A_{x}), 0\leq s\leq 1 $$

$$ y = A_{y}+s(B_{y}-A_{y}),0\leq s\leq 1 $$ 이 된다.

 

점 C\((C_{x},C_{y})\)와 점 D\((D_{x},D_{y})\)를 양 끝 으로 하는 선분 CD도 매개변수 t를 이용하여 표현하게 되면

$$ x = C_{x}+t(D_{x}-C_{x}), 0\leq t\leq 1 $$

$$ y = C_{y}+t(D_{y}-C_{y}),0\leq t\leq 1 $$ 이 된다.

 

 

 

 

 

 

 

 

만약 선분 AB와 선분 CD의 교점이 존재한다면, 선분 위의 점x,y를 같게 만드는 s,t가 \(0\leq s,t \leq1\) 내에 존재해야된다.

$$ A_{x}+s(B_{x}- A_{x}) = C_{x}+t(D_{x}-C_{x})$$

$$ A_{y}+s(B_{y}- A_{y}) = C_{y}+t(D_{y}-C_{y})$$

 

 

 

 

 

 

먼저 위의 식을 \(as+bt=c\) 의 형식으로 바꾼 뒤 역행렬을 곱하여 해를 구하게 되면

$$ s(B_{x}- A_{x})-t(D_{x}-C_{x}) = C_{x}-A_{x}$$

\(a= B_{x}- A_{x}, b= -(D_{x}-C_{x}),e=C_{x}-A_{x}\)로 치환

$$ as+bt = e$$

 

$$ s(B_{y}- A_{y})-t(D_{y}-C_{y}) = C_{y}-A_{y}$$

\(c=B_{y}- A_{y},d=-(D_{y}-C_{y}),f=C_{y}-A_{y}\)로 치환

$$ cs+dt = f$$

 

 

 

 

$$\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix}\begin{pmatrix}
s \\ t
\end{pmatrix}
=
\begin{pmatrix}
e \\  f
\end{pmatrix} $$

 

 

 

$$\begin{pmatrix}
s \\ t
\end{pmatrix}
=
\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix}^{-1}
\begin{pmatrix}
e \\ f
\end{pmatrix} $$

 

 

 

$$ \begin{pmatrix}
s \\ t
\end{pmatrix}
=
\frac{1}{ad-bc}\begin{pmatrix}
d & -b \\
-c & a \\
\end{pmatrix}
\begin{pmatrix}
e \\ f
\end{pmatrix}$$

 

 

 

$$s = \frac{de-bf}{ad-bc}$$

$$t=\frac{af-ce}{ad-bc} $$

가 된다.

 

 

 

매개변수 방정식의 해가 존재하는 경우

 

만약 \(ad-bc\neq 0\)인 경우에는 s,t 값을 구할수 있다.

이때 \(0\leq s\leq 1,0\leq t\leq 1\) 를 만족한다면 교점이 존재하는 것이다.

구한 s,t가 범위 밖이라면 교차하지 않는다.

 

 

 

 

 

 

 

 

 

평행하거나 일치하는 경우

 

\(ad-bc= 0\)인 경우에는 두 방정식이 평행하거나 일치하는 경우이다. 따라서 추가적인 확인이 필요하다.

 

 

 

만약 \(ad-bc=0\)이면서 \(as+bt=e\) 위의 한 점이 \(cs+dt=f\)위에 있다면, 두 방정식은 일치하게 된다.

\(as+bt=e\)위의 점 \((0,\frac{e}{b})\)를 \(cs+dt=f\)에 대입하면,

\(\frac{de}{b} = f\), 즉 \(de-bf=0\)이 된다.

 

 

 

 

 

평행한 경우

 

\(de-bf\neq0\) 라면 두 방정식이 평행한 경우이다. 조건을 만족하는 s,t가 존재하지 않는다. 두 선분은 교점이 없다.

 

 

 

 

 

 

 

일치하는 경우(두 선분이 한 직선 위에 있는 경우)

 

두 방정식이 일치하는 경우(\(de-bf=0\))는 조건을 만족하는 s,t가 무수히 많이 존재하게 된다. 즉 선분 AB와 선분 CD가 한 직선 위에 놓이게 된다.

 

 

 

두 선분이 한 직선 위에 놓이게 될경우 기울기 1을 기준으로 1보다 작다면 x축에, 1보다 크다면 y축에 수선의 발을 내린다.

\(abs(A_{x}-B_{x})\) 와 \(abs(A_{y}-B_{y})\) 중 큰 쪽의 축에 투영한다.

 

 

이렇게 되면 x축에 투영되는 경우 {선분 AB와 선분 CD중 더 오른쪽에 있는 선분의 왼쪽 점}이 {선분 AB와 선분 CD중 더 왼쪽에 있는 선분의 오른쪽 점} 보다 작아야한다.

그림에서는 오른쪽에 있는 선분이 AB이고 왼쪽에 있는 선분이 CD이다.

따라서 선분AB의 왼쪽점인 \(A_{x}\)가 선분 CD의 오른쪽 점인 \(D_{x}\) 보다 작아야한다.

\(max(min(A_{x},B_{x}),min(C_{x},D_{x}))\leq min(max(A_{x},B_{x}),max(C_{x},D_{x}))\) 가 된다.

 

 

하나 씩 살펴보면 max(선분AB의 왼쪽점, 선분CD의 왼쪽점) 을 하게되면 오른쪽에 있는 선분의 왼쪽점을 얻을 수 있다.

min(선분AB의 오른쪽점, 선분CD의 오른쪽점)을 하면 왼쪽에 있는 선분의 오른쪽 점을 얻을 수 있다.

 

 

 

 

y축에 투영하는 경우도 마찬가지로 

\(max(min(A_{y},B_{y}),min(C_{y},D_{y}))\leq min(max(A_{y},B_{y}),max(C_{y},D_{y}))\) 가 된다.

 

 

x축에 우선 투영하고 만약 x값이 같다면 y축에 투영하면 같은 결과를 얻을 수 있다.

\(max(min(A,B),min(C,D))\leq min(max(A,B),max(C,D))\) 가 된다.

 

 

 

교점이 하나일때 좌표를 구하는 방법

 

s,t가 \( 0\leq s\leq 1 , 0\leq t\leq 1 \) 범위 인경우, 매개변수 방정식에 대입하면 교점의 좌표를 구할 수 있다.

\(x = x_{1}+s(x_{2}- x_{1})\)

\(y = y_{1}+s(y_{2}- y_{1})\)

 

또한 두 선분이 한 직선 위에 있으면서 선분의 양 끝 점이 겹치는 경우, A,B,C,D 중에서 겹치게 되는 점이 교점이 된다.

 

 

 

 

python 구현

 

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

a,b,e = Bx-Ax, -(Dx-Cx), Cx-Ax
c,d,f = By-Ay, -(Dy-Cy), Cy-Ay
A = (Ax,Ay);B = (Bx,By);C = (Cx,Cy);D = (Dx,Dy);

 

좌표를 입력받고 매개변수 연립방정식을 풀기 위해 값을 치환해 준다.

 

 

# as+bt=e, cs+dt=f 연립방정식의 해
def solve(a,b,c,d,e,f):
    # 두 방정식이 평행하거나 일치하는 경우
    if a*d-b*c == 0:
        # 일치하는 경우 (두 선분이 한 직선 위에 있는 경우)
        if d*e-b*f==0:
        	# x축에 우선투영, x값이 같다면 y축에 투영
            if max(min(A,B),min(C,D)) <= min(max(A,B),max(C,D)):
                print(1)
            else:
                print(0)
        # 평행한 경우
        else:
            print(0)
    else:
        s = (d*e-b*f)/(a*d-b*c)
        t = (a*f-c*e)/(a*d-b*c)
        if 0<=s<=1 and 0<=t<=1:
            print(1)
        else:
            print(0)

 

연립방정식의 해를 구한다. 만약 \(ad-bc\neq0\) 라면 s,t값이 0이상 1이하 범위에 해당하는지 확인한다.

해당 범위에 있으면 교차하는것이고, 범위밖이라면 교차하지 않는다.

\(ad-bc=0\)인 경우에는 \(de-bf\)를 확인한다. 0이 아니라면 평행한것이고, 0이라면 두 선분은 한 직선위에 있는 것이다.

두 선분을 x축또는 y축에 투영해서 교차하는지 확인한다.

 

 

 

 

 

 

 

선분 교차 판별을 통해 해결할 수 있는 문제

 

[백준] 20149 선분 교차 3

[백준] 20149 선분 교차 3