多角形の最小コスト三角形分割アルゴリズムを解説【動的計画法・C++実装あり】

多角形において、互いに交差しない対角線によって三角形が形成されるとき、これを三角形分割（トライアンギュレーション）と呼びます。この記事では、数多くある三角形分割の中から、最小のコストとなる分割方法を求めるアルゴリズムを解説します。

三角形分割のコストは、その構成要素である各三角形の重みの総和として定義されます。各三角形の重みは、3辺の長さをすべて足し合わせた値、すなわち三角形の周長で求められます。

入力と出力

入力: 多角形の頂点の集合 {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}
出力: 三角形分割の総コスト。この例では 15.3006 となります。

アルゴリズム

minCost(polygon, n)

ここで cost() は、三角形の周長を計算するために使用します。

入力: 多角形を構成する点の集合と、点の総数。

出力: 多角形の三角形分割における最小コスト。

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

アルゴリズムのポイント

この問題は動的計画法（DP）を用いることで効率的に解けます。区間 [i, j] における最小コストを table[i][j] に記録し、分割点となる頂点 k を順に試しながら、区間を [i, k] と [k, j] に分けた場合のコストを計算します。すべての分割点の中で最小の値を採用することで、最適解が得られます。計算量は O(n³) です。

実装例（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³) の計算量で求められます。区間ごとの最小コストを表に記録しながら更新していくことで、考えられるすべての三角形分割の中から、最もコストの低い分割方法を効率的に見つけることができます。