최소 비용 다각형 삼각분할(Triangulation) 알고리즘 – 동적 계획법으로 구현하기

다각형 내부에서 서로 교차하지 않는 대각선들이 삼각형을 이루도록 분할하는 것을 삼각분할(Triangulation)이라고 합니다. 이 글에서 다룰 문제는 다양한 삼각분할 방법 중 최소 비용이 드는 삼각분할을 찾는 것입니다.

삼각분할의 총비용은 그것을 구성하는 개별 삼각형들의 가중치를 모두 더한 값으로 정의됩니다. 여기서 각 삼각형의 가중치는 세 변의 길이를 모두 더한 값, 즉 삼각형의 둘레(perimeter)로 계산합니다.

입력과 출력

입력:
다각형을 이루는 점들 {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}
출력:
삼각분할의 총비용. 이 예제에서 삼각분할의 비용은 15.3006입니다.

알고리즘

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 구간(gap) 단위로 부분 문제를 채워 나가며, 각 구간에서 가능한 분할점 k를 모두 시도해 최솟값을 구하는 방식입니다.

minCost(polygon, n)

여기서 cost() 함수는 삼각형의 둘레를 계산하는 데 사용됩니다.

입력: 다각형을 구성하는 점들의 집합과 점의 개수 n

출력 − 다각형 삼각분할의 최소 비용

Begin
    if n < 3, then
        return 0
    define table of order n x n
    i := 0

    for gap := 0 to n-1, do
        for j := gap to n-1, do
            if j < i+2, then
                table[i,j] := 0
            else
                table[i, j] = ∞
                for k := i+1 to j-1, do
                    val := table[i, k] + table[k, j] + cost(i, j, k)
                    if table[i, j] > val
                        table[i, j] := val
            i := i + 1
        done
    done
    return table[0, n-1]
End

알고리즘 동작 원리

• 점이 3개 미만이면 삼각형을 만들 수 없으므로 비용은 0입니다.
• table[i][j]는 i번째 점부터 j번째 점까지의 부분 다각형을 삼각분할하는 최소 비용을 저장합니다.
• j가 i+2보다 작으면 두 점 사이에 삼각형을 만들 수 없으므로 비용은 0입니다.
• 그 외의 경우, 분할점 k를 i+1부터 j-1까지 순회하며 table[i][k] + table[k][j] + cost(i, j, k)의 최솟값을 찾아 갱신합니다.
• cost(i, j, k)는 점 i, j, k로 이루어진 삼각형의 둘레(세 변의 길이의 합)입니다.

C++ 구현 예제

#include <iostream>
#include <cmath>
#include <iomanip>
#define MAX 1000000.0
using namespace std;

struct Point {
    int x, y;
};

double min(double x, double y) {
    return (x <= y)? x : y;
}

double dist(Point p1, Point p2) {     // p1과 p2 사이의 거리 계산
    return sqrt(pow((p1.x-p2.x),2) + pow((p1.y-p2.y),2));
}

double cost(Point triangle[], int i, int j, int k) {
    Point p1 = triangle[i], p2 = triangle[j], p3 = triangle[k];
    return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);     // 삼각형의 둘레
}

double minimumCost(Point polygon[], int n) {
    if (n < 3)     // 다각형의 점이 3개 미만인 경우
        return 0;
    double table[n][n];

    for (int gap = 0; gap < n; gap++) {
        for (int i = 0, j = gap; j < n; i++, j++) {
            if (j < i+2)
                table[i][j] = 0.0;
            else {
                table[i][j] = MAX;

                for (int k = i+1; k < j; k++) {
                    double val = table[i][k] + table[k][j] + cost(polygon,i,j,k);
                    if (table[i][j] > val)
                        table[i][j] = val;     // 최솟값으로 테이블 갱신
                }
            }
        }
    }   
    return  table[0][n-1];
}

int main() {
    Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
    int n = 5;
    cout <<"The minimumcost: " <<minimumCost(points, n);
}

실행 결과

The minimumcost: 15.3006

마무리

이 알고리즘은 행렬 곱셈 순서 문제와 유사한 구조를 가지며, 시간 복잡도는 O(n³)입니다. 다각형의 정점 개수가 n일 때 가능한 모든 분할 조합을 고려하되, 이미 계산된 부분 문제의 결과를 재활용함으로써 지수 시간의 완전 탐색보다 훨씬 효율적으로 최적 해를 구할 수 있습니다.