[解決済み] 2次元の多角形の面積はどのように計算するのですか？

質問

2次元空間に自己交差しない点が並んでいると仮定して、得られる多角形の面積を求める効率的な方法は何か？

余談ですが、これは宿題ではなく、私はコードを探しているわけではありません。 私は、私自身の方法を実装するために使用できる説明を探しています。 私は点のリストから三角形のシーケンスをプルすることについて私のアイデアを持っていますが、私はおそらく私がキャッチしない凸と凹の多角形に関するエッジケースの束があることを知っています。

どのように解決するのですか？

ここで 標準的な方法 です。基本的には各頂点の周りのクロスプロダクトを合計します。三角測量よりずっと簡単。

Pythonコードは、(x,y)頂点座標のリストとして表される多角形が与えられると、最後の頂点から最初の頂点へ暗黙のうちに回り込みます。

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

David Lehavi氏のコメントです。このアルゴリズムがなぜ機能するのかを述べておく価値があります。それは グリーンの定理 を応用したものです。 プラニメーター が機能するのと同じです。より具体的には

上記の式 =

integral_over_perimeter(-y dx + x dy) =

integral_over_area((-(-dy)/dy+dx/dx) dy dx) =

2 Area