두 선분이 교차하는지 검사하려면?

이차원상에서 직선이라면 기울기가 다르기만 하면 즉, 평행하지만 않으면 언젠가는 만나게 된다.

그러나 직선이 아니라 선분이면 길이가 정해져 있다.

선분1과 선분2가 있을 때, 각각 직선으로 확장한 것을 직선1, 직선2라고 하자.

직선1로 선분2의 양 끝점을 양분한다면 선분2와 직선1이 만나게 된다. (이 조건만 만족한다면, 직선1 대신 선분1로 했을때 선분1이 확장되지 않아 선분2와 만나지 않을 수도 있다. 즉 선분2이 직선2로 봤을 때 한쪽에 존재하는 경우이다.)

반대로 직선2로 선분1의 양 끝점을 양분한다면 선분1과 직선2가 만나게 된다. ( 이 조건도 만족한다면, 선분1이 직선2의 한쪽에 있지 않아서 위 걱정이 사라지게 된다.)

위 두 조건을 만족한다면, 선분1과 선분2가 만나게 된다.

모든 경우의 수를 따져보면 위 가정이 맞다는 것을 확인 할 수 있다.

먼저, 직선이 두 점을 양분하는지 검사하려면?

f(x)=0라는 직선이 있을 때, 두 점을 각각 넣어서 부호가 반대인 것을 의미한다.

y=mx+b 라는 직선이라고 본다면, 검사할 점(x1,y1)의 x좌표를 넣어서 나온 y값(mx1+b. 직선위의 점)이 검사할 점의 y좌표(y1)보다 크냐 작냐에 따라 직선 아래 또는 위에 있을지 결정된다.  따라서 y1-(mx1+b)를 하게 된 부호가 중요하다.  다른 점 (x2,y2)도 마찬가지로 넣으면

y1-(mx1+b)

y2-(mx2+b)

위 두 값의 부호가 다르면 양분된다. (y=mx+b 직선이 두 점을 양분한다.)

즉, 위 두 값을 곱하여 0보다 작으면 위 조건을 만족하게 된다

직선 1의 기울기를 구하고 방정식을 구하면

y = m1 (x-x11) + y11

직선2의 기울기를 구하고 방정식을 구하면

y=m2(x-x21)+y21

조건1 ;직선1이 두점(x21, y21), (x22, y22)를 양분하는지 검사

f1=y21- (m1 x21 - m1 x11 + y11 )

f2=y22 - (m1 x22 - m1 x11 + y11 )

f1*f2 < 0 이면 양분 된다.

좀 더 정리하면 

f1=y21 - ( x21 (y12-y11)/(x12-x11)  - x11 (y12-y11)/(x12-x11) + y11)

 = { 1/(x12-x11) }  * {  y21(x12-x11) - x21(y12-y11) +x11(y12-y11) -y11(x12-x11) }

=  { 1/(x12-x11) }  * { (y21-y11)(x12-x11) - (x21-x11)(y12-y11) }

이렇게 된다.

f2=위와 동일하다 (y21대신 y22, x21대신 x22를 대입)

f2={1/(x12-x11)} * { (y22-y11)(x12-x11) - (x22-x11)(y12-y11) }

f1*f2의 부호만 관심있으므로 분수 부분을 없애기 위해 (x12-x11)^2을 곱해도 부호는 변함없다.

따라서 분수를 없애면

f1 = (y21-y11)(x12-x11) - (x21-x11)(y12-y11) 

f2 = (y22-y11)(x12-x11) - (x22-x11)(y12-y11) 

if f1*f2 <0 then 양분됨.

이를 파이썬 모듈로 작성하면 간단하다.

    '''input: 4 points
    output: True/False
    '''
    #  // line1 extension이 line2의 두 점을 양분하는지 검사..
    # 직선의 양분 판단
    f1= (x12-x11)*(y21-y11) - (y12-y11)*(x21-x11)
    f2= (x12-x11)*(y22-y11) - (y12-y11)*(x22-x11)
    if f1*f2 < 0 :
      return True
    else:
      return False

두 선분이 교차하는지 검사하려면 이것을 바꿔서 두 번하면 된다.

def is_cross_pt(x11,y11, x12,y12, x21,y21, x22,y22):
    b1 = is_divide_pt(x11,y11, x12,y12, x21,y21, x22,y22)
    b2 = is_divide_pt(x21,y21, x22,y22, x11,y11, x12,y12)
    if b1 and b2:
        return True

랜덤하게 점을 찍어서 그리고, 위 조건 모듈을 써서 판정해 본 그래프

잘 판정되었다. 위 모듈에서 주의해야 할 것은 수평이나 수직인 경우는 별도로 처리해 주어야 한다. divide by zero등도 신경써서 에러 처리를 해 주어야 할 것이다. 테스트해보니 수직, 수평에서도 잘 작동하였다. ( divide 부분을 미리 처리해 두어서 그런지 별 이상없음.)

두 선분의 교점 찾기 /intersection

선분1 ; (x11,y11) to (x12, y12)

선분2 ; (x21,y21) to (x22, y22)

위 두 선분이 주어졌을 때  교점의 좌표를 파이썬 함수로 만들어 보자.

선분 1의 기울기 ; m1

선분2의 기울기 ; m2

따라서 선분1의 직선은 기울기가 m1이고 (x11, y11)점을 지난다.

y = m1 (x-x11) + y11

선분2의 직선은 기울기가 m2이고 (x21,y21)점을 지난다.

y=m2(x-x21)+y21

위 두 직선의 교차점은 x, y가 같게 되므로 위 연립 방정식의 해가 된다.

m1x - m1 x11 + y11 = m2x - m2x21 + y21

(m1-m2)x = m1x11-y11-m2x21+y21

x = (m1x11-y11-m2x21+y21) / (m1-m2)

x를 구했으면 위 아무 방정식에 넣으면 y가 나온다.

y = m1(x-x11)+y11

import numpy as np
import matplotlib.pyplot as plt


def get_crosspt(x11,y11, x12,y12, x21,y21, x22,y22):
    if x12==x11 or x22==x21:
        print('delta x=0')
        return None
    m1 = (y12 - y11) / (x12 - x11)
    m2 = (y22 - y21) / (x22 - x21)
    if m1==m2:
        print('parallel')
        return None
    print(x11,y11, x12, y12, x21, y21, x22, y22, m1, m2)
    cx = (x11 * m1 - y11 - x21 * m2 + y21) / (m1 - m2)
    cy = m1 * (cx - x11) + y11

    return cx, cy


x11 =np.random.randint(1,50)
y11 =np.random.randint(1,50)
x12 =np.random.randint(50,100)
y12 =np.random.randint(50,100)
x21 =np.random.randint(1,50)
y21 =np.random.randint(50,100)
x22 =np.random.randint(50,100)
y22 =np.random.randint(1,50)

plt.figure()
plt.plot([x11,x12], [y11,y12], c='r')
plt.plot([x21,x22], [y21,y22], c='b')

cx, cy = get_crosspt(x11, y11, x12, y12, x21, y21, x22, y22)
plt.plot(cx, cy, 'ro')
plt.show()

선분이 수직, 수평인 경우는 기울기가 0가 되어 문제가 될 수 있다.

이 경우는 따로 처리한다.

def get_crosspt(x11,y11, x12,y12, x21,y21, x22,y22):
    if x12==x11 or x22==x21:
        print('delta x=0')
        if x12==x11:
            cx = x12
            m2 = (y22 - y21) / (x22 - x21)
            cy = m2 * (cx - x21) + y21
            return cx, cy
        if x22==x21:
            cx = x22
            m1 = (y12 - y11) / (x12 - x11)
            cy = m1 * (cx - x11) + y11
            return cx, cy

    m1 = (y12 - y11) / (x12 - x11)
    m2 = (y22 - y21) / (x22 - x21)
    if m1==m2:
        print('parallel')
        return None
    print(x11,y11, x12, y12, x21, y21, x22, y22, m1, m2)
    cx = (x11 * m1 - y11 - x21 * m2 + y21) / (m1 - m2)
    cy = m1 * (cx - x11) + y11

    return cx, cy

나중에 필요에 따라 겹치거나 평행한 경우도 검사해 주어야 한다. 이것은 다음에 직선이 두 점을 양분하는지 체크하면 된다.