問題「n 多角形の頂点の座標が与えられているとき,その面積を求める」
質問「ちょっと考えてみたのですが、n > 3 の場合複数の多角形が考えられるように思えるのですが、どうなんでしょうか?」
回答「複数個の頂点を結ぶときに,結び方によっては違う多角形になりますが,互いに結ばれている 2 つの頂点に関する情報は何らかの形で必要ですね。
n 個の頂点が,x1,y1 --> x2,y2 ->; ・・・ --> xn, yn --> x1,y1 のように結ばれていて,頂点座標はこの順で与えられるとします。」
解答:
多角形の頂点座標を時計回りに順に(x1,y1),(x2,y2),...,(xn,yn)とします。 面積 S は,
n -2S = Σ ( xi-1 - xi+1 ) yi i=1 ただし, x0 = xn xn+1 = x1の関係式から求めることができます。測量関係では当たり前のアルゴリズムらしいです。
JavaScript による解答を参照してください。
なお,頂点が格子点の場合は,ピックの定理というのがあるそうです。これは,目で見て判定するのは簡単なのですが,コンピュータ上でやろうとするとなかなか面倒なことになりそうな気がします。