三角測量不要！C++で実装するSlickerアルゴリズムによる多角形の面積計算プログラム

本記事では、多角形を三角形に分割する三角測量（Triangulation）を行わずに面積を求められる「Slickerアルゴリズム」を実装したC++プログラムを紹介します。

Slickerアルゴリズムとは

Slickerアルゴリズムは、隣り合う頂点の座標から外積に相当する値を順番に加算し、その合計を2で割ることで多角形の面積を直接求める手法です。この方式は「靴ひも公式（Shoelace Formula）」としても知られており、多角形を三角形に分割する前処理が不要なため、計算量はO(n)と非常に効率的です。凸多角形だけでなく凹多角形にもそのまま適用できます。

このアルゴリズムは、数学で一般的な「y軸の正方向が上向き」という座標系を前提としています。一方、画面座標のようにy軸の正方向が下向きのシステムでは、頂点を反時計回りの順に列挙するのが最も簡単な対処法です。こうすることで2つの符号の効果が打ち消し合い、正の面積が得られます。

アルゴリズムの流れ（擬似コード）

Begin
    関数Area()は、多角形pを引数として受け取り、その面積を計算する。
    for i = 0 to p.n-1
        j = (i + 1) % p.n を初期化する
        t = t + ((p.p[i].a * 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 { // 各頂点の座標を表すクラス
public:
    double a, b; // a: x座標, b: y座標
};

class Polygon { // 多角形を表すクラス
public:
    P p[MAX]; // 頂点の配列
    int n;    // 頂点の個数
};

// 面積の計算
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].a * 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:\n";
    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) // 面積が正の場合
        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);
}

コードのポイント

• クラスP：各頂点のx座標（a）とy座標（b）を保持します。
• クラスPolygon：最大200個の頂点を格納できる配列pと、頂点の個数nを持ちます。
• Area()関数：i番目の頂点と次の頂点 j = (i + 1) % n の座標を使った式を累加し、最後に2で割って面積を返します。剰余演算により、最後の頂点から最初の頂点へ戻る辺も自動的に計算に含まれます。
• 負の値への対応：頂点が時計回りに並んでいると計算結果が負になります。その場合は-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

まとめ

Slickerアルゴリズムを使えば、三角測量のような前処理なしに、頂点座標だけからO(n)の計算量で多角形の面積を求められます。頂点の並び順（時計回り・反時計回り）に注意すれば、任意の単純多角形に対して確実に面積を計算できる、シンプルかつ強力な手法です。