Pythonでポリゴンの面積を求める方法：靴ひも公式を使った実装

はじめに

2次元平面上に、単純な多角形（ポリゴン）の頂点を時計回りまたは反時計回りの順に並べた座標リストが与えられたとします。このとき、その多角形の面積を計算するのが本記事の目的です。

例えば、入力が points = [(0, 0), (0, 5), (3, 5), (3, 0)] のような場合、これは幅3・高さ5の長方形を表しているため、出力は 15.0 となります。

解法の考え方：靴ひも公式（Shoelace Formula）

この問題は、有名な靴ひも公式（測量士の公式）を使うことで効率的に解けます。隣り合う2頂点ごとに外積 x1*y2 - y1*x2 を計算し、それらをすべて足し合わせて絶対値を2で割ると、多角形の面積が求まります。

アルゴリズムの手順

• 関数 getInfo(x1, y1, x2, y2) を定義し、x1*y2 - y1*x2 を返すようにします。
• メイン処理では以下を行います。
  • N := 頂点リスト points の要素数
  • (firstx, firsty) := points[0]（最初の頂点）
  • (prevx, prevy) := (firstx, firsty)
  • res := 0（面積の累積値）
• i を 1 から N-1 まで繰り返します。
  • (nextx, nexty) := points[i]
  • res := res + getInfo(prevx, prevy, nextx, nexty)
  • prevx := nextx、prevy := nexty に更新
• 最後の頂点から最初の頂点へ戻る辺についても getInfo() の結果を res に加算します。
• |res| / 2.0 を返します。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def getInfo(x1, y1, x2, y2):
    return x1*y2 - y1*x2

def solve(points):
    N = len(points)
    firstx, firsty = points[0]
    prevx, prevy = firstx, firsty
    res = 0

    for i in range(1, N):
        nextx, nexty = points[i]
        res = res + getInfo(prevx, prevy, nextx, nexty)
        prevx = nextx
        prevy = nexty
    res = res + getInfo(prevx, prevy, firstx, firsty)
    return abs(res)/2.0

points = [(0, 0), (0, 5), (3, 5), (3, 0)]
print(solve(points))

入力

[(0, 0), (0, 5), (3, 5), (3, 0)]

出力

15.0

まとめ

このアルゴリズムの計算量は O(N) で、頂点数 N に対して線形時間で面積を求められます。凸多角形だけでなく凹みのある単純多角形にも対応できるため、地理情報システム（GIS）やコンピュータグラフィックスなど、さまざまな分野で応用される実用的な手法です。