Blogopolisから学ぶ計算幾何

第8回 多角形の幾何(後編)

この記事を読むのに必要な時間:およそ 2 分

多角形の面積計算

続いて,凸多角形の面積を計算する方法を考えてみましょう。面積と聞いて,前々回の内容から,何か思い出すことがないでしょうか。そう,外積です。2つのベクトルの外積は,そのベクトルが作る平行四辺形の符号付き面積に等しくなるのでした。外積の式と図を以下に再掲します。

式1 平面幾何におけるベクトルの外積

式1 平面幾何におけるベクトルの外積

図4 平行四辺形の符号付き面積

図4 平行四辺形の符号付き面積

この外積をうまく利用すれば,凸多角形の面積計算ができそうです。話を簡単にするために,図5のように,凸多角形が原点(0, 0)を含むと仮定しましょう。

図5 原点を包含する凸多角形

図5 原点を包含する凸多角形

次に,図6のように,原点から凸多角形の各頂点へと線分を引きます。頂点をA, B, C, ...とすると,ベクトルA, B, C, ...は,まさにこれらの線分によって表されるベクトルとなります。

図6 各頂点のベクトル

図6 各頂点のベクトル

ここで,ベクトルAとベクトルBの外積がどんな量になるかを考えてみると,それは図7で示すような平行四辺形の面積です。ちょうど,三角形OABの面積の2倍になるわけです。

図7 ベクトルの外積

図7 ベクトルの外積

もうわかりましたね。AとBの外積,BとCの外積,...というように,隣り合う頂点のベクトル同士の外積をそれぞれ計算して合計し,2で割れば,凸多角形の面積が得られるのです。ただし,頂点の巡回順が時計回りの場合,この値は負になりますので,絶対値を見る必要があります。

そして,この外積を使った面積計算の方法は,多角形が原点を含まない場合でも,さらには多角形が凸でない場合(⁠⁠五芒星」のように,辺同士が交差する場合は除く)でも,まったく同様に適用できてしまいます(なぜこのようなことが成立するのか,図を描いて考えてみてください⁠⁠。

それでは,ConvexPolygonクラスに,多角形の面積を取得するgetArea()メソッドを追加してみましょう。

リスト getArea()メソッドの記述(Java)

public double getArea() {
    double crossSum = 0; // 外積の合計
    int size = vertices.size();
    // 頂点を巡回
    for (int i = 0; i < size; i++) {
        Point2D v1 = vertices.get(i);
        Point2D v2 = vertices.get((i + 1) % size);
        // 外積を計算
        double cross = GeomUtils.cross(v1, v2);
        crossSum += cross; // 外積を加算
    }
    return Math.abs(crossSum / 2.0);
}

前々回の実装により,ConvexPolygonオブジェクトは,多角形の頂点を,反時計回りまたは時計回りの順番にしたがって,verticesフィールドに保持する仕様になっています。この前提があるため,verticesの要素を先頭から辿っていくことで,外積の計算に必要な隣接する頂点の組を順に得られることになります。

まとめと次回予告

今回は,多角形に対する演算として,点の包含判定と面積計算の2つを取り上げました。今回紹介した方法は,凸多角形クラスであるConvexPolygonのメソッドとして実装しましたが,凸でない多角形にも適用することができます。

今回作成したプログラムのソースコードがダウンロードできます。

次回は,凸多角形の「オーバーレイ」について考えます。お楽しみに!

著者プロフィール

浜本階生(はまもとかいせい)

1981年生まれ。栃木県出身。東京工業大学情報工学科卒業。技術やアイデアの組み合わせから面白いソフトウェアを生み出したいと日々考えている。現在,ブログの解析および視覚化の試みとして「TopHatenar」「Blogopolis」を開発,運用中。

URLhttp://d.hatena.ne.jp/kaiseh/