선분의 교차 판정

선분은 직선 상의 두 점과 그 두 점 사이의 점들로 구성되는 유한인 직선의 부분이다. 간단히 두 점을 잇는 최단거리다. 샤프심 두 개를 책상에 쏟았다. 샤프심을 선분이라고 봤을 때 이 두 가닥의 샤프심의 위치관계를 몇 가지로 나누어 설명할 수 있을까. 우선 두 샤프심이 서로 닿은 경우와 닿지 않은 경우가 있을 것이다. 그리고 닿은 경우에는 겹친 경우도 있을 것이다. 닿지 않은 경우도 나란히 놓여서 샤프심의 길이가 무한히 늘어나도 닿지 않는 특수한 경우와 그렇지 않은 경우로 나눌 수 있다.

1. 벡터의 외적

벡터는 고등수학에 따르면 크기와 방향을 가진 물리량을 의미한다. 쉽게 생각하면 화살표로 볼 수 있다. 길이도 있고 방향도 있다. 선분끼리는 더하거나 뺀다는 연산을 길이만 두고 할 수 있으나 벡터는 방향까지 있으므로 2차원 연산을 할 수 있다. 면적이 나올 수 있다.

벡터의 연산은 내적과 외적이 있다. 연산 결과는 이렇다.
내적→스칼라
외적→벡터

수학적 지식의 부족으로 자세한 설명은 어렵지만 외적의 결과는 벡터이기 때문에 방향을 갖는다. 연산 결과로는 부호를 갖는 형식으로 만들 수 있다. 따라서 두 벡터의 외적을 취하면 부호를 통해 두 벡터, 방향을 없앤다면 선분이 놓여있는 방향의 관계를 알 수 있다.

2. CCW(counter clock wise)

반시계방향으로 꺾느냐를 판별하는 방법에 외적이 쓰인다. 앞서 작성했던 컨벡스헐 문제에 이미 관련내용이 정리되어있다.

세 점 A, B, C를 두고 벡터AB, 벡터BC를 만들면 하나의 벡터를 꺾은 것처럼 된다. 그 꺾인 방향은 넷 중 하나인데 벡터AB의 방향을 기준으로 오른쪽, 왼쪽 그리고 꺾지 않은 상태, 반대 방향으로 꺾인 상태다. 이런 관계를 극좌표계에서 보면 두 벡터가 이루는 각이 각각 양수, 음수, 0, 180이다. 두 벡터가 이루는 각이 양의 크기를 갖는 경우, 벡터도 양의 값을 갖는다. 반대의 경우는 당연 음수고 0과 180일 때는  0이 나온다.

이 외적 값을 이용해 세 점을 연달아 이은 두 벡터가 왼쪽으로 꺾이는지 오른쪽으로 꺾이는지를 판별하는 방법이 CCW 알고리즘이다. 알고리즘이라고 할 것도 없고 그냥 수식이다.

def CCW(p1, p2, p3):
    k = (p1[1]-p2[1])*(p2[0]-p3[0])-(p1[0]-p2[0])*(p2[1]-p3[1])
    if k > 0:
        return 1
    elif k < 0:
        return -1
    else:
        return 0

여기서 벡터 사이의 각의 크기에 따라 k값이 어떻게 변화하느냐가 궁금했는데 이는 대략 sin함수의 형태를 띤다. 그래서 이 k값을 비교해 각의 크기를 비교하는 짓은 하면 안된다. 하려면 다른 처리 과정이 또 필요하다고 한다.

3. 두 선분의 관계

이제 두 선분을 놓고 보자. 점 A, B를 잇는 선분과 점 C, D를 잇는 선분이 있다.

두 선분이 "교차"했다면 한 선분의 양 끝은 다른 선분의 연장으로 만들어진 직선을 기준으로 다른 위치에 놓여있어야 한다.

이렇게. A는 직선 CD의 왼쪽, B는 반대쪽에 있다. 만약 두 점이 모두 같은 위치에 놓였다면?

아무리 생각해도 그런 경우에 선분이 교차하는 경우는 존재하지 않는다. 아 물론 점 B가 직선 CD의 일부인 경우가 있다. 하지만 그것조차 직선 위에 있는 상태이기 때문에 점 A와는 다른 위치에 있는 것으로 본다. 그럼 이 관계를 정리할 수 있는 방법은 무엇인가. CCW를 여기서 이렇게 쓸 수 있다.

벡터CD를 두고, 벡터DA, 벡터DB에 대해 각각 외적을 취하면 부호가 다르게 나온다. 그러면 이제 두 선분이 주어졌을 때, 두 번의 외적 결과를 비교해 하나의 선분, 나머지 한 선분의 전체인 직선의 교차여부를 판단할 수 있다. 다음과 같은 경우는 외적의 결과가 다른 부호임에도 교차하지 않는 선분이다.

이런 경우는 어찌하나, 외적을 반대로 한 번 더해주면 된다. 이번에는 벡터AB를 놓고 벡터BD, 벡터,BC의 외적을 각각 구해보면 둘 다 같은 부호다. 그럼 이제 이렇게 정리할 수 있다.

 

두 선분이 주어졌을 때, 선분의 양 끝 점으로 CCW를 실행해서 서로 다른 부호가 나타나면 두 선분은 교차한 것으로 볼 수 있다.

a = (x1,y1)
b = (x2,y2)
c = (x3,y3)
d = (x4,y4)

ccw1 = CCW(a,b,c)*CCW(a,b,d)
ccw2 = CCW(c,d,a)*CCW(c,d,b)

if ccw1 <= 0 and ccw2 <= 0:
    print("두 선분은 교차한다.")

# 하지만 이것은 틀렸습니다.

 

4. 예외 처리

CCW의 값이 모두 0이 나와버리는 경우가 존재한다.

이 경우는 두 선분이 교차하지 않지만 CCW의 값이 모두 0이 나와버린다. 이런 경우는 선분의 좌표가 서로 교차되는지 따로 확인해주면 된다.

if ccw1 == ccw2 == 0:
    minabx = min(a[0],b[0])
    maxabx = max(a[0],b[0])
    mincdx = min(c[0],d[0])
    maxcdx = max(c[0],d[0])
    minaby = min(a[1],b[1])
    maxaby = max(a[1],b[1])
    mincdy = min(c[1],d[1])
    maxcdy = max(c[1],d[1])
    
    if minabx <= maxcdx and mincdx <= maxabx and minaby <= maxcdy and mincdy <= maxaby:
        print("두 선분은 교차한다.")
    else:
        print("두 선분은 평행하며 교차하지 않는다.")
elif ccw1 <= 0 and ccw2 <= 0:
    print("두 선분은 교차한다.")
else:
    print("두 선분은 교차하지 않는다.")

 

5. 관련 문제

17386번 문제는 세 점이 일직선 위에 있는 경우가 없기 때문에 나란한 경우의 까다로운 판정을 생략할 수 있다.

17386번: 선분 교차 1

 

17387번 문제는 나란한 경우도 판정해줘야 한다. 17387번 코드로 17386 제출하면 당연히 맞았습니다.

 

17387번: 선분 교차 2