선분 교차 판별하기

두 선분이 주어질 때 선분이 교차하는지 판별하는 방법을 알아보겠습니다

 

선분 AB, CD 가 다음과 같이 있다고 가정하겠습니다

이 때 선분 AB, CD 가 교차하는지 확인하는 방법은

삼각형의 면적을 구하는 공식+벡터 를 통해서 결정할 수 있습니다

 

이를 구하는 함수는 보통 CCW (반시계방향의 줄임말) 으로 세점에 대한 방향성을 확인하는 함수라 칭하겠습니다

삼각형의 면적 + 벡터를 구하는 공식은 다음과 같습니다

1, 2, 3 을 각각 함수의 인자로 받게될 선분의 정점이라고 가정한다면

다음과 같은 함수를 만들 수 있습니다.

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를 모두 구해주는 것입니다.

선분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