컴퓨터 그래픽스나 충돌 감지 등 다양한 분야에서 자주 등장하는 문제 중 하나는 두 선분이 서로 교차하는지 판별하는 것입니다. 첫 번째 선분의 양 끝점을 p1, p2라 하고, 두 번째 선분의 양 끝점을 q1, q2라고 할 때, 두 선분의 교차 여부를 효율적으로 확인할 수 있습니다.
교차 조건
두 선분이 교차한다고 판단할 수 있는 대표적인 조건은 다음과 같습니다.
- (p1, p2, q1)과 (p1, p2, q2)의 방향(orientation)이 서로 다르고,
- (q1, q2, p1)과 (q1, q2, p2)의 방향 역시 서로 다를 때
여기서 '방향'이란 세 점이 이루는 회전 방향을 의미하며, 시계 방향(clockwise), 반시계 방향(anti-clockwise), 그리고 세 점이 한 직선 위에 있는 경우(collinear)로 나눌 수 있습니다.
또한 특수한 경우로, 네 점 (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2)가 모두 일직선상에 있으면서 선분 범위 내에 겹치는 부분이 존재할 때도 교차로 판단해야 합니다.
입력 및 출력 예시
입력:
두 선분의 좌표
선분 1: (0, 0) → (5, 5)
선분 2: (2, -10) → (3, 10)
출력:
Lines are intersecting (두 선분은 교차함)
알고리즘
1. direction(a, b, c)
입력: 세 개의 점
출력: 세 점이 일직선상에 있는지, 반시계 방향인지, 시계 방향인지 판별
세 점의 방향은 외적(cross product)의 부호를 이용해 계산합니다. 값이 0이면 세 점은 일직선상에 있고, 음수면 반시계 방향, 양수면 시계 방향입니다.
Begin
val := (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)
if val = 0, then
return collinear // 일직선
else if val < 0, then
return anti-clockwise // 반시계 방향
return clockwise // 시계 방향
End
2. isIntersect(l1, l2)
입력: 두 선분 (각 선분은 두 점으로 구성)
출력: 두 선분이 교차하면 true, 아니면 false
Begin
dir1 = direction(l1.p1, l1.p2, l2.p1);
dir2 = direction(l1.p1, l1.p2, l2.p2);
dir3 = direction(l2.p1, l2.p2, l1.p1);
dir4 = direction(l2.p1, l2.p2, l1.p2);
if dir1 ≠ dir2 and dir3 ≠ dir4, then
return true // 일반적인 교차 경우
if dir1 = 0 and l2.p1 is on line l1, then
return true // 끝점이 상대 선분 위에 있는 경우
if dir2 = 0 and l2.p2 is on line l1, then
return true
if dir3 = 0 and l1.p1 is on line l2, then
return true
if dir4 = 0 and l1.p2 is on line l2, then
return true
return false
End
C++ 전체 예제 코드
#include<iostream>
using namespace std;
struct Point {
int x, y;
};
struct line {
Point p1, p2;
};
// 점 p가 선분 l1 위에 있는지 확인
bool onLine(line l1, Point p) {
if(p.x >= min(l1.p1.x, l1.p2.x) && p.x <= max(l1.p1.x, l1.p2.x) &&
p.y >= min(l1.p1.y, l1.p2.y) && p.y <= max(l1.p1.y, l1.p2.y))
return true;
return false;
}
// 세 점의 방향 판별
int direction(Point a, Point b, Point c) {
int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (val == 0)
return 0; // 일직선(collinear)
else if (val < 0)
return 2; // 반시계 방향
else
return 1; // 시계 방향
}
// 두 선분의 교차 여부 판별
bool isIntersect(line l1, line l2) {
// 각 선분의 끝점에 대해 네 가지 방향을 계산
int dir1 = direction(l1.p1, l1.p2, l2.p1);
int dir2 = direction(l1.p1, l1.p2, l2.p2);
int dir3 = direction(l2.p1, l2.p2, l1.p1);
int dir4 = direction(l2.p1, l2.p2, l1.p2);
if(dir1 != dir2 && dir3 != dir4)
return true; // 두 선분이 교차함
// 일직선상에 있으면서 끝점이 상대 선분 위에 놓이는 특수 경우 처리
if(dir1 == 0 && onLine(l1, l2.p1))
return true;
if(dir2 == 0 && onLine(l1, l2.p2))
return true;
if(dir3 == 0 && onLine(l2, l1.p1))
return true;
if(dir4 == 0 && onLine(l2, l1.p2))
return true;
return false;
}
int main() {
line l1 = {{0, 0}, {5, 5}};
line l2 = {{2, -10}, {3, 10}};
if(isIntersect(l1, l2))
cout << "Lines are intersecting";
else
cout << "Lines are not intersecting";
}
동작 원리 요약
이 알고리즘의 핵심은 외적을 통한 방향 판별입니다. 어떤 선분의 양 끝점이 다른 선분을 기준으로 서로 반대편에 위치하고, 동시에 그 반대도 성립하면 두 선분은 반드시 교차합니다. 또한 세 점이 일직선상에 있는 경우(dir 값이 0)에는 해당 점이 실제로 상대 선분의 범위 안에 있는지 onLine 함수로 추가 검사하여, 끝점이 맞닿거나 선분이 겹치는 특수한 경우까지 정확하게 처리합니다.
실행 결과
Lines are intersecting