두 선분의 교차 판정

이 글은 CCW를 알고 있는 독자를 대상으로 합니다.

CCW에 대해 궁금하신 분들은 이 글을 참고해주세요.

1. 세 점이 한 직선위에 위치하지 않은 경우

세 점이 한 직선위에 위치하지 않은 경우에는, 선분의 양 끝점을 마주보는 꼭짓점으로 하는 사각형을 그릴 수 있습니다.

예를 들어, 선분 $A$의 양 끝점 $p_0(x_0, y_0), p_2(x_2, y_2)$과 선분 $B$의 양 끝점 $p_1(x_1, y_1), p_3(x_3, y_3)$를 각 꼭짓점으로 가지는 사각형 $p_0p_1p_2p_3$을 그릴 수 있습니다.

위 그림에서 볼 수 있는 것 처럼 두 선분이 만난다면, 사각형은 볼록 사각형이 되고, 두 선분이 만나지 않는 다면 오목 사각형이 되는 것을 확인할 수 있습니다.

$0 \le i < 4$인 정수 $i$에 대해 $R_i = CCW(P_i, P_{(i+1) \% 4}, P_{(i + 2) \% 4})$를 계산하고, 4개의 부호가 모두 같으면, 교차하는 선분, 부호가 하나라도 다르면, 두 선분은 교차하지 않는다고 판정할 수 있습니다.

즉, 모든 $i$에 대해서 $R_i \times R_{(i+1) \% 4} > 0$을 만족하면 됩니다.

2. 세 점만 한 직선 위에 위치한 경우

세 점이 한 직선 위에 위치해 있는 경우, 위 과정과 동일하게 $R_i$들을 계산하면,

$R_i$들 중 1개 이상이 0이 됩니다.

한 직선 위에 있는 세 점에 대해 CCW를 수행하는 경우 그 크기가 0이 되기 때문입니다.

이 경우 위와 동일한 공식으로 판정하기에는, $R_i \times R_{(i+1) \% 4}$가 0이 되는 경우가 있기 때문에, 동일한 기준을 사용할 수 없습니다.

세 점만 한 직선 위에 위치한 경우는 아래 그림처럼 크게 3가지 경우로 나누어 볼 수 있습니다.

세 경우 중에서 선분이 교차하는 경우는 첫 번째와 두 번째 경우인데, 이 두 경우 모두 0이 아닌 $R_i$들은 모두 같은 부호를 가지고 있는 것을 알 수 있습니다.

네 점이 한 직선 위에 있지 않은 이상, $R_i$와 $R_{(i+2)\%4}$모두 0인 경우는 없으므로, 모든 $i$에 대해서 $R_i \times R_{(i+1) \% 4} \ge 0$을 만족하면 됩니다.

1번째 경우 CCW의 부호를 검사하면 $R_i$는 $[0, -, -, -]$의 형태가 됩니다. (좌표의 순서를 바꾸더라도 $0$의 위치나 $-$가 모두 $+$로 바뀌는 등의 차이만 있을 뿐, 연속되는 두 값을 곱했을 때 0 이상이 되는 것을 확인할 수 있습니다.

2번째 경우 CCW의 부호를 검사하면 $[0, 0, -, -]$ 등의 형태가 될 수 있습니다. 이 경우 또한 연속되는 두 값을 곱했을 때 항상 0 이상이 되는 것을 확인할 수 있습니다.

마지막 경우 CCW의 부호를 검사하면 $[0, +, -, -]$ 의 형태가 되는데, 이 경우에는 반드시 이웃하는 두 $R_i$를 곱했을 때 0 미만이 되는 경우가 생깁니다. ($R_1 \times R_2$)

3. 네 점 모두 한 직선 위에 위치한 경우

네 점 모두 한 직선 위에 있는 경우는 아래 그림처럼 2가지 상태가 있을 수 있습니다.

위의 경우들처럼 CCW를 계산해도, 모두 0이 되기 때문에 같은 방식으로 교차판정을 하는 것을 어렵습니다.

따라서 이 경우 점들 간의 정렬이 필요합니다. 먼저 $P_i(x_{P_i}, y_{P_i}) \le P_j(x_{P_j}, y_{P_j})$를 다음과 같이 정의합니다.

Struct Point {
  ll x, y;

  bool operator<=(const Point &b) const {
    if(x != b.x) {
      return x < b.x;
    } else {
      return y <= b.y;
    }
  }
}

$P_0$와 $P_2$가 $P_0 \le P_2$가 되도록 정렬해주고, $P_1$과 $P_3$도 $P_1 \le P_3$를 만족하도록 정렬해줍니다.

이렇게 정렬된 상태에서, $P_1 \le P_2$와 $P_0 \le P_3$ 모두 참이라면, 두 선분은 만난다고 판정할 수 있습니다.

실제 대회 상황에서의 구현

실제 대회에서 이런 유형의 문제를 만났을 때, 위의 설명처럼 정확한 개념을 알고 있는 것도 중요하지만, 어떻게 코드로 빠르게 구현하느냐도 중요하다고 볼 수 있습니다.

지금부터는, 코드로 구현할 때 논리의 흐름 위주로 설명하도록 하겠습니다.

1. 모든 $i (0 \le i < 4)$에 대해서 $CCW(P_i, P_{(i+1) \% 4}, P_{(i + 2) \% 4})$를 계산합니다.
2. 계산된 CCW가 모두 0인 아닌 경우와 모두 0인 경우로 나눕니다.
3. 계산된 CCW가 모두 0이 아닌 경우, 모든 $i$에 대해서 $R_i \times R_{(i+1) \% 4} \ge 0$을 만족하는지 확인합니다.
4. 계산된 CCW가 모두 0인 경우, 점들을 정렬하고 $P_1 \le P_2$와 $P_0 \le P_3$을 모두 만족하는지 확인합니다.

CCW의 값의 범위는 좌표의 범위의 제곱과 같고, 3번 과정에서 두 CCW의 결과값을 곱하는 과정이 있으므로 오버플로우가 발생하지 않도록 주의합니다.

아래는 위 과정을 C++코드로 표현한 것입니다.

#include <bits/stdc++.h>
using namespace std;

struct Point {
  int x, y;

  bool operator<=(const Point &b) const {
    if(x != b.x) {
      return x < b.x;
    } else {
      return y <= b.y;
    }
  }
};

// ccw의 결과를 곱할 때 오버플로우가 발생하지 않도록, CCW 결과값 대신 부호만을 반환합니다.
int ccw(Point a, Point b, Point c) {
  ll result = a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y;
  if (result > 0) {
    return 1;
  } else if (result == 0) {
    return 0;
  } else {
    return -1;
  }
}

Point p[4];
int ccw_results[4];

bool all_zero() {
  for(int i = 0; i < 4; i++) {
    if(ccw_results[i] != 0) return false;
  }
  return true;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> p[0].x >> p[0].y >> p[2].x >> p[2].y;
  cin >> p[1].x >> p[1].y >> p[3].x >> p[3].y;

  // 1. 모든 i에 대한 CCW를 계산합니다.
  for(int i = 0; i < 4; i++) {
    ccw_results[i] = ccw(p[i], p[(i+1)%4], p[(i+2)%4]);
  }

  bool flag = true;
  // 2. 계산된 CCW가 모두 0이 아닌 경우와 모두 0인 경우로 나눕니다.
  if(!all_zero()) {
    // 3. 계산된 CCW가 모두 0이 아닌 경우, 모든 i에 대해서 인접한 두 CCW의 곱이 0 이상인지 확인합니다.
    for(int i = 0; i < 4; i++) {
      if(ccw_results[i] * ccw_results[(i+1)%4] < 0) {
        flag = false;
      }
    }
  } else {
    // 4. 계산된 CCW가 모두 0인 경우, 점들을 정렬합니다.
    if(p[2] < p[0]) {
      swap(p[0], p[2]);
    }
    if(p[3] < p[1]) {
      swap(p[1], p[3]);
    }
    // 4-2. P_1 ≤ P_2 와 P_0 ≤ P_3P을 모두 만족하는지 확인합니다.
    if(p[1] <= p[2] && p[0] <= p[3]) {
      flag = true;
    } else {
      flag = false;
    }
  }
  // flag가 true라면, 두 선분은 교차합니다.
  if(flag) {
    cout << "두 선분은 교차합니다!\n";
  } else {
    cout << "두 선분은 교차하지 않습니다!\n";
  }
  return 0;
}

더 간단한 구현

https://www.acmicpc.net/source/58920501