삼각분할 없이 다각형 넓이를 구하는 C++ 슬리커 알고리즘 구현 방법

개요

이 글에서는 삼각분할(Triangulation) 과정 없이 슬리커(Slicker) 알고리즘을 활용해 다각형의 넓이를 계산하는 C++ 프로그램을 소개합니다. 슬리커 알고리즘은 신발끈 공식(Shoelace Formula)이라고도 불리며, 다각형의 꼭짓점 좌표만 있으면 O(n)의 시간 복잡도로 간단하고 빠르게 넓이를 구할 수 있는 효율적인 기하학 알고리즘입니다.

이 알고리즘은 일반적인 수학 관례대로 y축의 양수 방향이 위쪽을 가리킨다고 가정합니다. 반면 컴퓨터 화면 좌표계처럼 y축 양수가 아래쪽인 환경에서는, 해당 좌표계를 기준으로 꼭짓점을 반시계 방향으로 나열하는 것이 가장 간단한 해결 방법입니다. 이렇게 하면 두 좌표계의 영향이 서로 상쇄되어 최종적으로 양수의 면적 값을 얻을 수 있습니다.

알고리즘 의사코드

Begin
    Area() 함수는 다각형 p를 인자로 받아 다각형의 넓이를 계산합니다.
    for i = 0 to p.n-1
        j = (i + 1) % p.n 으로 초기화
        t = t + ((p.p[i].b * p.p[j].b) - (p.p[j].a * p.p[i].b)) 계산
    return t/2
End

C++ 예제 코드

#include <iostream>
using namespace std;

const int MAX = 200;

class P { // 변수 선언용 클래스
private:
public:
    double a, b;
};

class Polygon {
private:
public:
    P p[MAX];
    int n;

    Polygon() { // 다각형의 각 점 좌표 저장
        for (int i = 0; i < MAX; i++)
            P p[i];
    }
};

double Area(Polygon p) { // 넓이 계산
    double t = 0;
    for (int i = 0; i < p.n; i++) {
        int j = (i + 1) % p.n;
        t += (p.p[i].b * p.p[j].b) - (p.p[j].a * p.p[i].b);
    }
    return t / 2;
}

int main(int argc, char **argv) {
    Polygon p;

    cout << "Enter the number of points in Polygon: ";
    cin >> p.n;
    cout << "Enter the coordinates of each point: ";
    for (int i = 0; i < p.n; i++) {
        cin >> p.p[i].a;
        cin >> p.p[i].b;
    }

    double a = Area(p);
    if (a > 0) // 넓이가 0보다 큰 경우
        cout << "The Area of Polygon with " << p.n
            << " points using Slicker Algorithm is : " << a;
    else
        cout << "The Area of Polygon with " << p.n
            << " points using Slicker Algorithm is : " << (a * -1);
}

실행 결과

Enter the number of points in Polygon: 6
Enter the coordinates of each point:
1 1
2 2
3 3
4 4
5 5
6 7
The Area of Polygon with 6 points using Slicker Algorithm is : 2.5

알고리즘 동작 원리

슬리커 알고리즘의 핵심은 다각형을 이루는 인접한 두 꼭짓점 쌍마다 교차 곱(cross product) 형태의 값을 누적하는 것입니다. 코드에서는 나머지 연산자(%)를 사용해 마지막 꼭짓점과 첫 번째 꼭짓점도 자연스럽게 연결되도록 처리합니다. 모든 항을 더한 뒤 2로 나누면 다각형의 넓이가 되며, 꼭짓점이 시계 방향으로 입력된 경우 결과가 음수로 나올 수 있으므로 -1을 곱해 양수로 변환한 후 출력합니다.