2차원 평면상에서 선분 AB와 CD의 정보가 주어질 때, 두 선분의 교차 여부를 빠르게 판단할 수 있는 방법이 있다. 벡터의 외적(벡터곱)을 이용하는 방법이다.
그림 1과 같이 두 선분이 교차하는 경우를 생각해 보자. 벡터 BA를 기준으로 점 C와 점 D가 서로 다른 회전방향에 있으므로, 아래 두 경우는 벡터곱 연산의 결과로 나온 z값의 부호가 다르다.
- 벡터 BA와 벡터 BC를 외적한 결과
- 벡터 BA와 벡터 BD를 외적한 결과
벡터 DC에 대해서도 역시 부호가 다르게 된다.
- 벡터 DC와 벡터 DA를 외적한 결과
- 벡터 DC와 벡터 DB를 외적한 결과
그림 1. 교차하는 두 선분
그림 2. 교차하지 않는 두 선분
Javascript로 표현하면 아래와 같이 쓸 수 있다.
let p1 = line1.p1; let p2 = line1.p2; let p3 = line2.p1; let p4 = line2.p2; let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y); let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y); let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y); let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y); return sign1*sign2<0 && sign3*sign4<0; |
그러나 위 코드에는 문제점이 있는데, 그림 3과 같이 두 선분의 기울기가 같을 때는 교차하지 않는 것으로 판단한다는 것이다. (이런 결과를 의도했다면 문제가 되지 않겠지만..)
그림 3. 두 선분의 기울기가 같고, 교차점이 무수히 많은 경우
그림 3과 같은 경우에도 두 선분이 교차하는 것으로 판정하기 위해, 비교문을 아래와 같이 고치면 또다른 문제가 발생한다. 그림 4와 같이 기울기가 같고 서로 떨어져 있을 때 잘못 판정한다는 것이다.
return sign1*sign2<=0 && sign3*sign4<=0; |
그림 4. 교차 여부를 잘못 판정한 경우
두 선분이 완전히 떨어져 있을 경우(더 정확히 말하면, 각각의 선분이 이루는 직사각형 영역이 서로 겹치지 않는 경우)에 false를 리턴하면 이 문제를 해결할 수 있다. 외적 연산에 앞서 사전 영역 검사를 하는 것이다.
아래 코드에서 모든 부호가 0일 때 true를 반환하는 부분을 추가한 이유는, 그림 3과 같이 교차점이 무수히 많은 경우도 교차하는 것으로 판단하기 위해서이다.
let p1 = line1.p1; let p2 = line1.p2; let p3 = line2.p1; let p4 = line2.p2; if(Math.max(p1.x, p2.x) < Math.min(p3.x, p4.x)) return false; if(Math.min(p1.x, p2.x) > Math.max(p3.x, p4.x)) return false; if(Math.max(p1.y, p2.y) < Math.min(p3.y, p4.y)) return false; if(Math.min(p1.y, p2.y) > Math.max(p3.y, p4.y)) return false; let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y); let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y); let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y); let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y); if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true; return sign1*sign2<=0 && sign3*sign4<=0; |
그림 5. 교차 여부를 정상적으로 판정한 경우
경우에 따라서 그림 6과 같이 선분의 끝점이 교차할 때는 교차하지 않는 것으로 판단하는 것이 필요할 때가 있다.
그림 6, 7. 두 선분이 교차하는 것으로 판단하는 경우
아래 코드에서와 같이 사전 영역 검사에 동등 조건을 넣어 좀더 엄격하게 바꾸고(그림 6과 관련), 마지막의 리턴 코드에서 동등 조건을 제거한다.(그림 7과 관련)
let p1 = line1.p1; let p2 = line1.p2; let p3 = line2.p1; let p4 = line2.p2; if(Math.max(p1.x, p2.x) <= Math.min(p3.x, p4.x)) return false; if(Math.min(p1.x, p2.x) >= Math.max(p3.x, p4.x)) return false; if(Math.max(p1.y, p2.y) <= Math.min(p3.y, p4.y)) return false; if(Math.min(p1.y, p2.y) >= Math.max(p3.y, p4.y)) return false; let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y); let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y); let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y); let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y); if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true; return sign1*sign2<0 && sign3*sign4<0; |
결론
만들고자 하는 프로그램에 따라 선분 끝점을 어떻게 판단해야할지가 달라진다. 위 코드를 활용하여 비교문들을 조정하면 선분의 교차 판단을 목적에 맞게 할 수 있을 것이다.
소스코드
동작하는 전체 코드는(Javascript)는 아래 github에서 다운로드할 수 있습니다.
https://github.com/tibyte/algorithms/tree/master/line-intersection