기하학 알고리즘 - CCW와 기본 연산 - soo:bak

작성일 :

기하학 알고리즘이란?

게임에서 캐릭터가 벽을 통과하지 못하게 하려면 충돌 감지가 필요합니다.

지도 앱에서 현재 위치가 특정 영역 안에 있는지 확인하려면 점과 다각형의 포함 관계를 판별해야 합니다.

이런 문제들은 모두 기하학 알고리즘으로 해결합니다.


기하학 알고리즘(Computational Geometry) 은 점, 선, 다각형 등 기하학적 객체를 다루는 알고리즘입니다.

게임 개발, 지도 서비스, 컴퓨터 그래픽스 등 다양한 분야에서 활용됩니다.


벡터의 기초

기하학 알고리즘의 핵심은 벡터 연산입니다.


벡터 표현

점 A(x₁, y₁)에서 점 B(x₂, y₂)로의 벡터:

\[\vec{AB} = (x_2 - x_1, y_2 - y_1)\]


예를 들어, A(1, 2)에서 B(4, 6)으로의 벡터는 (3, 4)입니다.


벡터의 내적 (Dot Product)

\[\vec{A} \cdot \vec{B} = x_1 \times x_2 + y_1 \times y_2 = |\vec{A}||\vec{B}|\cos\theta\]


내적의 특징:

  • 내적이 0이면 두 벡터는 수직
  • 내적이 양수이면 사이각이 90° 미만 (예각)
  • 내적이 음수이면 사이각이 90° 초과 (둔각)


벡터의 외적 (Cross Product)

2D에서 외적은 스칼라 값을 반환합니다.

\[\vec{A} \times \vec{B} = x_1 \times y_2 - y_1 \times x_2 = |\vec{A}||\vec{B}|\sin\theta\]


외적의 부호로 두 벡터의 방향 관계를 알 수 있습니다:

  • 양수: B가 A의 반시계 방향에 있음
  • 음수: B가 A의 시계 방향에 있음
  • 0: A와 B가 평행 (같은 직선 위)


외적의 절댓값은 두 벡터가 이루는 평행사변형의 넓이입니다.


CCW (Counter-Clockwise)

CCW는 세 점의 방향 관계를 판별하는 알고리즘입니다.


세 점 A, B, C가 주어졌을 때, A에서 B로 가고 B에서 C로 갈 때 어느 방향으로 꺾이는지 판별합니다:

  • 양수: 반시계 방향 (왼쪽으로 꺾임)
  • 음수: 시계 방향 (오른쪽으로 꺾임)
  • 0: 일직선


CCW 공식

벡터 $\vec{AB}$와 벡터 $\vec{AC}$의 외적으로 계산합니다.

\[CCW = \vec{AB} \times \vec{AC} = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)\]


CCW 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

typedef long long ll;

struct Point {
  ll x, y;
};

// 세 점의 방향 관계 판별
// 반환값: 1(반시계), -1(시계), 0(일직선)
ll ccw(Point a, Point b, Point c) {
  ll result = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

  if (result > 0)
    return 1;   // 반시계 방향
  if (result < 0)
    return -1;  // 시계 방향
  return 0;     // 일직선
}


CCW 예시

1
2
3
4

    C(1, 3)
    ↑
    |
A(0, 0) → B(2, 1)

CCW(A, B, C)를 계산하면:

1
2

CCW = (2-0)(3-0) - (1-0)(1-0)
    = 6 - 1 = 5 > 0

결과가 양수이므로 반시계 방향입니다. A에서 B로 가고 C로 갈 때 왼쪽으로 꺾입니다.


선분 교차 판정

두 선분이 교차하는지 CCW를 이용해 판별합니다.


아이디어

선분 AB와 선분 CD가 교차하려면:

  1. A와 B가 선분 CD의 양쪽에 있어야 합니다.
  2. C와 D가 선분 AB의 양쪽에 있어야 합니다.


1
2

CCW(C, D, A) × CCW(C, D, B) < 0   (A와 B가 CD의 양쪽)
CCW(A, B, C) × CCW(A, B, D) < 0   (C와 D가 AB의 양쪽)

두 조건을 모두 만족하면 교차합니다.


일직선 위의 경우

CCW 값이 0인 경우, 네 점이 일직선 위에 있습니다. 이때는 점이 선분 위에 있는지 추가 확인이 필요합니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 점 p가 선분 ab 위에 있는지 확인 (일직선일 때 사용)
bool onSegment(Point p, Point a, Point b) {
  return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
         min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

// 선분 ab와 선분 cd가 교차하는지 판별
bool intersect(Point a, Point b, Point c, Point d) {
  ll d1 = ccw(c, d, a);
  ll d2 = ccw(c, d, b);
  ll d3 = ccw(a, b, c);
  ll d4 = ccw(a, b, d);

  // 일반적인 교차 (양쪽에 있는 경우)
  if (d1 * d2 < 0 && d3 * d4 < 0)
    return true;

  // 한 점이 다른 선분 위에 있는 경우
  if (d1 == 0 && onSegment(a, c, d))
    return true;
  if (d2 == 0 && onSegment(b, c, d))
    return true;
  if (d3 == 0 && onSegment(c, a, b))
    return true;
  if (d4 == 0 && onSegment(d, a, b))
    return true;

  return false;
}


다각형의 넓이

신발끈 공식 (Shoelace Formula)

n개의 꼭짓점으로 이루어진 다각형의 넓이를 구하는 공식입니다.

\[S = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \right|\]


꼭짓점을 순서대로 나열하고, 인접한 점들의 외적을 모두 더합니다. 마지막 점과 첫 점도 연결해야 합니다.


“신발끈”이라는 이름은 계산 과정이 신발끈을 묶는 모양과 비슷해서 붙여졌습니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12

double polygonArea(vector<Point>& p) {
  int n = p.size();
  ll sum = 0;

  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;  // 다음 점 (마지막 다음은 첫 점)
    sum += p[i].x * p[j].y;
    sum -= p[j].x * p[i].y;
  }

  return abs(sum) / 2.0;
}


예시

삼각형 (0, 0), (4, 0), (2, 3)의 넓이:

1
2
3
4

sum = (0×0 - 4×0) + (4×3 - 2×0) + (2×0 - 0×3)
    = 0 + 12 + 0 = 12

넓이 = |12| / 2 = 6


점과 다각형의 포함 관계

점이 다각형 내부에 있는지 판별합니다.


Ray Casting Algorithm

점에서 오른쪽으로 수평 반직선을 그어, 다각형의 변과 몇 번 교차하는지 셉니다.

  • 교차 횟수가 홀수면 내부
  • 교차 횟수가 짝수면 외부


직관적으로, 다각형 안에서 밖으로 나가려면 반드시 변을 넘어야 합니다.

안에서 시작하면 홀수 번 넘어야 밖으로 나가고, 밖에서 시작하면 짝수 번(0 포함) 넘어야 밖에 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool isInside(Point p, vector<Point>& polygon) {
  int n = polygon.size();
  int count = 0;

  for (int i = 0; i < n; i++) {
    Point a = polygon[i];
    Point b = polygon[(i + 1) % n];

    // 수평 반직선과 선분 ab가 교차하는지 확인
    if ((a.y > p.y) != (b.y > p.y)) {
      double x = (double)(b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
      if (p.x < x)
        count++;
    }
  }

  return count % 2 == 1;
}


두 점 사이의 거리

유클리드 거리

\[d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\] 
1
2
3
4
5

double dist(Point a, Point b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}


거리의 제곱 (정수 연산용)

실수 오차를 피하려면 가능한 한 제곱 상태로 비교하는 것이 좋습니다.

1
2
3
4
5

ll distSquared(Point a, Point b) {
  ll dx = a.x - b.x;
  ll dy = a.y - b.y;
  return dx * dx + dy * dy;
}


“점 A가 점 B보다 원점에 가까운가?”를 판별할 때, sqrt를 쓰지 않고 제곱 값으로 비교하면 됩니다.


주의사항: 실수 오차

기하 문제에서는 실수 오차에 특히 주의해야 합니다.


1. 정수로 계산 가능하면 정수 사용

CCW, 거리 제곱 비교 등은 정수로 처리할 수 있습니다. 불필요한 실수 연산을 피합니다.


2. 오차 허용 범위(EPS) 설정

실수 비교 시 직접 ==를 쓰지 말고, 오차 범위 내인지 확인합니다.

1
2
3
4
5

const double EPS = 1e-9;

bool equal(double a, double b) {
  return abs(a - b) < EPS;
}


3. long long 사용

좌표 범위가 10⁶ 정도면, 곱셈 시 10¹²까지 갈 수 있어서 int로는 오버플로우가 발생합니다. long long을 사용합니다.


마무리


문제 핵심 기법
세 점의 방향 판별 CCW
선분 교차 판정 CCW 4번
다각형 넓이 신발끈 공식 (외적의 합)
점의 내부/외부 판정 Ray Casting
볼록 껍질 CCW + 정렬


기하 문제는 실수 오차에 주의하고, 가능하면 정수 연산을 사용하는 것이 안전합니다.


관련 문제

이 블로그의 다른 글