[C++] CCW / 두 선분의 교차 판단

선분 교차 판단 알고리즘은 2차원 평면 위에서 두 선분이 주어졌을 때, 두 선분이 서로 교차하는지 교차하지 않는지 판단하는 알고리즘이다. 이 알고리즘을 학습하기 위해서 선행되어야 하는 기하 알고리즘이 있는데, 그 개념은 CCW이다. CCW (Counter Clock Wise)는 2차원 평면 위에 놓인 3개의 점에 대해서 어떤 방향성이 있는지 알려주며 이 방향성 정보를 사용해 선분이 서로 교차하는지 판단하게 된다.

 

 

 

 

 

 

 

 CCW 

 

먼저 3개의 점으로 나타낼 수 있는 방향성의 종류에는 무엇이 있는지 알아봐야 한다. 3개의 점을 임의의 순서대로 이어서 나온 방향성은 아래와 같이 1) 시계 방향 2) 반시계 방향 3) 일직선  3종류가 있을 수 있다.

 

 

 

 

세 점으로 만들 수 있는 방향성

 

 

 

 

그러면 이제 3개의 각 점에 대한 좌표정보가 주어지면 그 방향성을 어떻게 구하는지 그 계산 과정에 대해서 알아봐야 하는데, 외적에 대한 이해가 필요하다. 방향성을 판단하는데 외적을 사용하는 이유는 아래의 블로그에 나와있으며 중고등학교 과정에서 한 번쯤 사용해보았을 사선 공식을 사용하게 된다.

 

 

 

 

https://wogud6792.tistory.com/11

외적 (CCW 알고리즘)

 

 

 

 

이제부터 2차원 평면상에 3개의 점을 $p_1, p_2, p_3$ 라고 가정하고, 각각의 좌표는 $x_i, y_i$ 라고 해보면, 외적의 결과를 다음과 같이 계산할 수 있다.

 

 

 

$$ S = (x_{1}y_{2} + x_{2}y_{3} + x_{3}y_{1}) - (x_{2}y_{1} + x_{3}y_{2} + x_{1}y_{3}) $$

 

 

 

$S$ 의 값에 대해 나올 수 있는 부호에 따라 다시 3종류로 분류해볼 수 있다. 그리고 외적의 개념에 의해 그 방향성을 아래와 같이 판단할 수 있다.

 

 

1. $S < 0$ : 시계방향
2. $S > 0$ : 반시계 방향
3. $S = 0$ : 일직선(평행)

 

 

int ccw(pair<int, int>p1, pair<int, int>p2, pair<int, int>p3) {
    int s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
    s -= (p1.second * p2.first + p2.second * p3.first + p3.second * p1.first);

    if (s > 0) return 1;
    else if (s == 0) return 0;
    else return -1; 
}

 

 

 

 

 

 

 

 두 선분의 교차 판단 알고리즘 

 

이제 3점이 주어졌을 때, 그 방향성을 파악할 수 있게 되었으니 두 선분의 교차 판단을 할 준비가 되었다. 먼저 두 선분이 교차하는 상황부터 예를 들어 확인해보자.

 

 

 

두 선분의 교차 판단(1) : 선분의 교차

 

 

 

 

$p_1, p_2, p_3$와 $p_1, p_2, p_4$ 에 대해서 각각 CCW알고리즘으로 계산한다면 한쪽은 1(반시계방향), 다른 한쪽은 -1(시계방향)의 결과 값을 얻을 수 있다. 비슷한 예시로, $p_1, p_2, p_3$가 일직선상에 존재한다면 한쪽은 0, 다른 한쪽은 1 또는 -1의 값을 얻을 수 있다. 따라서, 위의 그래프를 가지고 판단할 수 있는 정보는 아래 수식과 동일하다.

 

 

 

 

$$ \text{CCW}(p_1, p_2, p_3) \times  \text{CCW}(p_1, p_2, p_4) \leq 0 $$

 

 

 

 

하지만, 위의 허술한 예시와 수식에는 반례가 존재한다. 그 반례는 아래와 같이 두 선분 $l_{1}$과 $l_{2}$가 교차하지 않음에도 위의 조건에서는 교차한다고 판단을 하게 되는 것이다.

 

 

 

두 선분의 교차 판단(2) : 교차 하지 않는 선분

 

 

 

물론, 위의 $l_1$이 기준이 되는 수식$\text{CCW}(p_1, p_2, p_3) \times \text{CCW}(p_1, p_2, p_4) \leq 0 $)에 대해서는 만족을 하지만, $l_2$가 기준이 되는 수식에서는 둘 다 반시계 방향 또는 둘 다 시계방향으로 볼 수 있다. 이렇기 때문에 $l_2$ 에 대해서도 CCW를 진행해야 한다. 결과적으로 $l_1$을 기준으로 하는 CCW의 결과 값과 $l_2$를 기준으로 하는 CCW의 결과 값 모두가 0 이하일 때, 교차한다고 판단할 수 있다.

 

 

 

 

$$(\text{CCW}(p_1, p_2, p_3) \times \text{CCW}(p_1, p_2, p_4) \leq 0) \;\&\&\; (\text{CCW}(p_3, p_4, p_1) \times 
\text{CCW}(p_3, p_4, p_2) \leq 0)$$

 

 

 

 

하지만 안타깝게도, 이렇게 새롭게 조건이 추가되었음에도 불구하고 반례는 여전히 1개 존재한다. 반례는 두 선분이 교차하지 않으면서 일직선 관계에 놓여있는 경우로 모든 CCW의 값이 0이 되는 예시이다.

 

 

 

두 선분의 교차 판단(3) : 두 선분이 일직선 상에 존재

 

 

 

 

모든 선분이 일직선 상에 존재할 때 즉, 서로의 CCW의 값이 모두 0인 경우에는 따로 분리를 해야 한다. 그렇다면 일직선 상에 있음에도 두 선분이 교차하는 경우는 서로 포개져 있는 경우 뿐이다. 해당 경우를 제외하고 두 선분은 모두 분리되어 있다.

 

 

 

 

 

지금까지의 모든 조건들을 합쳐서 교차 여부를 판단하는 함수를 C++로 작성해보면 아래와 같다.

 

#define pii pair<int, int>

bool isIntersect(pair<pii, pii> l1, pair<pii, pii> l2) {

    pii p1 = l1.first;
    pii p2 = l1.second;
    pii p3 = l2.first;
    pii p4 = l2.second;

    int p1p2 = ccw(p1, p2, p3) * ccw(p1, p2, p4); // l1 기준
    int p3p4 = ccw(p3, p4, p1) * ccw(p3, p4, p2); // l2 기준

    // 두 직선이 일직선 상에 존재
    if (p1p2 == 0 && p3p4 == 0) {
    	// 비교를 일반화하기 위한 점 위치 변경
        if (p1 > p2) swap(p2, p1);
        if (p3 > p4) swap(p3, p4);
        
        return p3 <= p2 && p1 <= p4; // 두 선분이 포개어져 있는지 확인
    }
    
    return p1p2 <= 0 && p3p4 <= 0;
    
}