C에서의 폴리곤 볼록성 검사: 알고리즘과 구현

C로 볼록 다각형 검사: 이론부터 견고한 구현까지

다각형이 볼록인지 확인하는 작업은 계산 기하학의 핵심 과제입니다. 게임 엔진, 내비게이션 시스템, 컴퓨터 그래픽스에서 필수적입니다. 볼록 도형은 처리 속도가 빠르기 때문에 이 검사는 중요한 최적화 단계입니다.

알고리즘의 기하학적 기초

다각형의 볼록성은 꼭짓점을 순회하며 회전 방향으로 결정됩니다. 모든 회전이 같은 방향(왼쪽 또는 오른쪽)으로 일어나면 볼록입니다. 방향이 바뀌면 오목합니다.

세 점 A, B, C에 대한 회전 방향은 외적의 부호로 계산합니다:

cross = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

• cross > 0 — 왼쪽 회전
• cross < 0 — 오른쪽 회전
• cross = 0 — 세 점이 일직선

이 공식은 벡터 AB와 AC가 이루는 평행사변형의 부호 있는 면적을 줍니다. 부호는 점 C가 A에서 B 방향으로 "위" 또는 "아래"에 있는지 나타냅니다.

기본 데이터 구조

점과 다각형을 위한 구조체로 시작합니다. 꼭짓점 수는 런타임에 알 수 있으므로 동적 할당합니다.

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point *vertices;
    int n;
} Polygon;

생성과 소멸 함수로 메모리를 관리합니다:

Polygon* CreatePolygon(int n) {
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;
    p->n = n;
    p->vertices = malloc(n * sizeof(Point));
    if (!p->vertices) {
        free(p);
        return NULL;
    }
    return p;
}

void DestroyPolygon(Polygon *p) {
    if (!p) return;
    free(p->vertices);
    free(p);
}

방향 함수와 오버플로 문제

핵심 Orient 함수는 외적을 계산합니다. long long을 사용해 좌표 곱셈 시 오버플로를 방지하지만, 64비트 타입도 한계가 있습니다.

long long Orient(Point a, Point b, Point c) {
    return (long long)(b.x - a.x) * (c.y - a.y) -
           (long long)(b.y - a.y) * (c.x - a.x);
}

중요한 애플리케이션에서는 오버플로 보호를 추가하세요:

#include <limits.h>

int SafeMul(long long a, long long b, long long *res) {
    if (a > 0 && b > 0 && a > LLONG_MAX / b) return 0;
    if (a > 0 && b < 0 && b < LLONG_MIN / a) return 0;
    if (a < 0 && b > 0 && a < LLONG_MIN / b) return 0;
    if (a < 0 && b < 0 && a < LLONG_MAX / b) return 0;
    *res = a * b;
    return 1;
}

long long OrientSafe(Point a, Point b, Point c) {
    long long p1, p2;
    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2)) {
        // 오버플로 처리: 0 반환은 일직선과 충돌
        // 실제로는 에러 플래그 설정 또는 __int128 사용
        printf("OVERFLOW\n");
        exit(1);
    }
    return p1 - p2;
}

중요: 오버플로 시 0 반환은 잘못된 것입니다. 일직선을 의미하기 때문입니다. 엄격한 코드에서는 에러 플래그나 더 넓은 타입을 사용하세요.

볼록성 검사 알고리즘

주요 IsConvex 함수는 모든 꼭짓점 삼중에 대한 외적 부호를 확인합니다. sign은 첫 번째 0이 아닌 회전 방향을 추적합니다.

int IsConvex(const Polygon *p) {
    int sign = 0;
    for (int i = 0; i < p->n; i++) {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];
        long long cross = Orient(a, b, c);
        if (cross == 0) continue; // 일직선 점 건너뛰기
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // 첫 방향 고정
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // 방향 변경 — 볼록 아님
        }
    }
    return 1; // 모든 회전이 같은 방향
}

주요 구현 특징:

• % p->n으로 순환 순회.
• 일직선 점(cross == 0)은 건너뛰며, 직선 구간이 있는 다각형에 적합.
• O(n) 시간 복잡도, 상수 추가 공간.

완전한 프로그램 예제

이 코드는 stdin에서 다각형을 읽어 분석하는 완전한 애플리케이션입니다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 구조체와 방향 함수 (위와 동일)
// ...

int ReadPolygon(Polygon *p) {
    for (int i = 0; i < p->n; i++) {
        if (scanf("%d %d", &p->vertices[i].x, &p->vertices[i].y) != 2) return 0;
    }
    return 1;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 3) {
        printf("INPUT ERROR: need at least 3 vertices\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("MEMORY ERROR\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("INPUT ERROR: invalid coordinates\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "CONVEX\n" : "NOT CONVEX\n");
    DestroyPolygon(p);
    return 0;
}

실무 고려사항과 제한점

알고리즘은 꼭짓점이 순회 순서(시계/반시계)로 주어지고, 다각형이 단순(자기 교차 없음)임을 가정합니다.

주요 포인트:

• 일직선 처리: cross == 0 건너뛰기는 직선 가장자리가 있는 볼록 다각형에 적합하지만 입력 오류를 숨길 수 있습니다.
• 오버플로 보호: 프로덕션 코드에서는 안전 곱셈이나 __int128이 필요하며, 큰 좌표에 특히 그렇습니다.
• 성능: 기본 알고리즘은 O(n) 최적이지만 OrientSafe는 검사로 느려집니다. 입력 범위에 따라 선택하세요.
• 적용 범위: 2D 다각형 전용. 3D는 면 검사나 부피 부호 분석 필요.
• 대안: 복잡한 경우 CGAL이나 Boost.Geometry 라이브러리, 또는 GPU 가속 사용.

— Editorial Team