두 선분이 주어질 때 선분이 교차하는지 판별하는 방법을 알아보겠습니다
선분 AB, CD 가 다음과 같이 있다고 가정하겠습니다
이 때 선분 AB, CD 가 교차하는지 확인하는 방법은
삼각형의 면적을 구하는 공식+벡터 를 통해서 결정할 수 있습니다
이를 구하는 함수는 보통 CCW (반시계방향의 줄임말) 으로 세점에 대한 방향성을 확인하는 함수라 칭하겠습니다
삼각형의 면적 + 벡터를 구하는 공식은 다음과 같습니다
1, 2, 3 을 각각 함수의 인자로 받게될 선분의 정점이라고 가정한다면
다음과 같은 함수를 만들 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
|
typedef struct {
int x, y;
}pii;
int ccw(pii a, pii b, pii c) {
int ans = (b.x - a.x) * (c.y - a.y) - (b.y - a.y)* (c.x - a.x);
if (ans < 0) return 1;
else if (ans > 0) return -1;
else return 0;
}
|
위의 그림에서 선분 AB로 선분CD를 확인하는 CCW는 다음과 같이 호출할 수 있습니다
CCW(A,B,C), CCW(A,B,D)
CCW(A,B,C) 의 의미는 선분 AB 에 대한 정점 C 의 방향을 벡터로 반환받는다는 의미입니다
이 때 CCW(A,B,C) * CCW(A,B,D) 의 곱이 음수이면, 즉 각 함수의 반환값이 0이 아닌 음수와 양수이면
두 선분은 교차하는 것으로 판별할 수 있습니다.
만약 값이 0 이라면 두 선분은 평행하다는 의미입니다.
지금까지의 설명은 임의의 볼록다각형에서 사용할 수 있는 방법입니다.
다시 정의하자면, 어떤 주어진 볼록다각형의 그 선 위에 있는 좌표끼리로만 판단할 수 있다는 의미입니다.
다음 설명할 것은 볼록다각형이 아닌 좌표평면에 대한 두 선분의 교차를 판별하는 방법입니다.
정해진 선 위에서 존재하는 정점이 아니라면 다음과 같은 경우가 있을 수 있습니다.
선분AB 에 대해서 선분CD 에 대한 CCW 를 구하게 되면 분명 그 곱은 음수가 될 것입니다.
교차한다는 의미가 됩니다.
하지만 육안으로 보면 두 선분은 교차하지 않고 있습니다.
어떻게 교차하는지 확인할 수 있을까요?
그 방법은 두 선분에 대한 CCW를 모두 구해주는 것입니다.
선분AB 에 대한 선분CD, 선분 CD에 대한 선분 AB 이 될 것입니다.
그리고 다음과 같은 조건에 의해 두 선분이 교차한다고 할 수 있습니다.
CCW(A,B,C)*CCW(A,B,D) <=0 && CCW(C,D,A)*CCW(C,D,B) <=0
이 식에는 다음과 같은 반례가 존재합니다.
다음과 같은 경우 두선분 각각 CCW 를 구했을 때 둘다 0이라는 값을 가지게 됩니다.
이때는 위와 같은 상태인지, 아래와 같은 상태인지 알 수 없게 됩니다.
이럴 때 두 선분이 교차하는지 확인하는 방법은 정점의 상대적인 위치를 확인해주는 것입니다.
B가 C 보다 크거나 같고 A 가 D 보다 작거나 같으면 두 선분은 교차하게 됩니다.
A<=D && B>=C
'algorithm > algorithm' 카테고리의 다른 글
| 볼록껍질 선분 처리하기 (0) | 2020.02.28 |
|---|---|
| 유클리드 호제법 (0) | 2020.02.28 |
| 세그먼트 트리 정리 (0) | 2020.02.05 |
| 삼분 탐색(Ternary search) (0) | 2020.01.16 |
| LCS (0) | 2019.07.04 |
