위키득계정 ↗
기술

선분 교차 판정

선분 교차 판정기술
영어
Segment intersection test
입력
끝점 네 개로 주어진 두 선분
기본 연산
방향 판정과 좌표 구간 비교
구분할 경우
내부 교차와 끝점 접촉 및 공선 겹침
선분 교차 판정은 두 선분이 공통점을 갖는지 결정하는 계산이다. 평면에서는 CCW 방향 판정과 좌표 구간의 겹침을 함께 사용해 교점을 직접 계산하지 않고도 판별할 수 있다.

직선 교점과 선분 교차

두 선분을 연장한 직선이 만나더라도 실제 교점이 두 선분 안에 놓이지 않으면 선분은 교차하지 않는다. 또한 두 선분이 같은 직선 위에서 겹치는 경우에는 교점이 하나가 아닐 수 있다. 문제에서 끝점 접촉도 교차로 볼 것인지 먼저 정해야 한다.

서로 반대편인지 검사

공선이 아닌 두 선분 AB와 CD에서는 A와 B가 직선 CD의 같은 쪽에만 놓이지 않고, C와 D도 직선 AB의 같은 쪽에만 놓이지 않아야 한다. 이를 CCW 값의 부호로 검사할 수 있다. (0, 0)부터 (4, 4)와 (0, 4)부터 (4, 0)의 두 선분은 서로 가로질러 만난다.

공선인 경우의 구간

같은 직선 위에서는 방향 판정값이 모두 0이 될 수 있으므로 좌표 구간이 겹치는지 확인한다. (0, 0)부터 (1, 0)과 (3, 0)부터 (4, 0)은 모두 공선이지만 서로 떨어져 있다. x와 y축으로 투영한 닫힌 구간의 겹침을 검사하면 수직선분도 같은 틀로 처리할 수 있다.

교점 좌표가 필요하지 않을 때

정수 끝점의 교점은 정수가 아닐 수 있지만 교차 여부는 방향식과 범위 비교만으로 정수 연산을 사용해 판정할 수 있다. 다만 중간 곱의 오버플로를 고려해야 한다. 방향값끼리 큰 곱을 새로 만드는 대신 부호를 비교하는 방식도 검토할 수 있다.

관련 문서

CCW 판정 / 선분 / 직선의 방정식 / 행렬식 / 볼록 껍질 / 그레이엄 스캔