Blogopolisから学ぶ計算幾何

第6回 多角形の幾何(前編)

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

外積の計算

平面幾何における外積の式を,ここで改めて導入しましょう。

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

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

右辺を見ると,これはベクトルaとbを辺とする平行四辺形の符号付き面積に等しくなることが分かります(図6⁠⁠。

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

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

ベクトルaを(x1, y1),ベクトルbを(x2, y2)と成分表示し,これらの成分を使って平行四辺形の面積を求め,外積の計算式を導いてみましょう。

図7 ベクトル成分表示と平行四辺形

図7 ベクトル成分表示と平行四辺形

図7のように補助線を引くと,平行四辺形の面積は,ベクトルa+bを対角線とする長方形の面積から,(1)(2)(3)の領域の面積を引いたものとして求められます。これは簡単に計算でき,以下の式が得られます。

式4 ベクトルの成分による外積の計算式

式4 ベクトルの成分による外積の計算式

それでは,この外積の計算をユーティリティメソッドとして実装しておきましょう。GeomUtilsクラスを作成し,cross()メソッドを以下のように追加します。メソッド名のcrossは,3次元の外積がクロス積とも呼ばれることに由来します。

cross()メソッドの追加(Java)

public class GeomUtils {
    public static double cross(double x1, double y1, double x2, double y2) {
        return x1 * y2 - x2 * y1;
    }
}

CCW関数

さて,外積を利用して,CCWという関数を作ることができます。CCWの名前は,反時計回りを意味するcounterclockwiseに由来しており,次の入力と出力を持ちます。

入力: 3点a, b, cの座標

出力: a→b→cと進むとき,その道のりが反時計回りになる場合は正の値。時計回りになる場合は負の値。a, b, cが一直線上にある場合はゼロ。

なお,ここで時計回り,反時計回りというときは,y座標が下から上に向かって増加する座標系を前提とすることにします。CCW関数の入力と出力の対応を図8に示します。

図8 CCW関数

図8 CCW関数

外積とCCW関数には,非常にシンプルな関係があります。aからbへ向かうベクトルabと,bからcへ向かうベクトルbcの外積を考えます(ベクトルの向きに注意してください⁠⁠。abとbcのなす角度をθとすると,ベクトルが反時計回りになる場合はsinθが正の値になるため,外積も正になります。また,ベクトルが時計回りになる場合はsinθが負の値になるため,外積も負になります。つまり実質的に,ベクトルabとbcの外積をそのままCCW関数として使えてしまうわけです。

では,CCW関数を実装してみましょう。a, b, cの座標をそれぞれ(x1, y1), (x2, y2), (x3, y3)として引数にとるccw()メソッドを,GeomUtilsクラスに追加します。また,a, b, cの各座標をPoint2Dオブジェクトで引数にとるccw()メソッドも用意することにします。

ccw()クラスの追加(Java)

    public static double ccw(double x1, double y1, double x2, double y2,
            double x3, double y3) {
        return cross(x2 - x1, y2 - y1, x3 - x2, y3 - y2);
    }

    public static double ccw(Point2D p1, Point2D p2, Point2D p3) {
        return ccw(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY());
    }

最後に,ConvexPolygonクラスのコンストラクタに,このccw()メソッドを使った凸性の判定処理を追加してみましょう。先に述べたように,凸多角形では辺が常に時計回りか反時計回りのどちらかになり,凸でない多角形では時計回りと反時計回りが混在します。したがって,コンストラクタに渡された頂点座標を巡回しながら,CCW値の正負が統一されているかどうかをチェックしていけば良いことになります。

以下,この方針にしたがって多角形の凸性をチェックし,凸でない場合にはエラーを発生させるコードを示します。

凸性の判定処理(Java)

    // verticesには凸多角形の頂点座標が順番に格納してあるものとする
    public ConvexPolygon(List<Point2D> vertices) {
        int size = vertices.size();
        if (size < 3) { // 角数が3未満の場合はエラー
            throw new IllegalArgumentException();
        }
        this.vertices = vertices;
        edges = new ArrayList<LineSegment>();

        // 基準となるCCW値を計算
        double ccw0 = GeomUtils.ccw(vertices.get(0), vertices.get(1), vertices.get(2));
        if (ccw0 == 0) { // ゼロの場合はエラー
            throw new IllegalArgumentException("Polygon is not convex.");
        }
        for (int i = 1; i < size; i++) {
            Point2D v1 = vertices.get(i); // i番目の頂点
            Point2D v2 = vertices.get((i + 1) % size); // v1の次の頂点
            Point2D v3 = vertices.get((i + 2) % size); // v2の次の頂点
            double ccw = GeomUtils.ccw(v1, v2, v3); // CCW値を計算
            if (ccw0 * ccw <= 0) { // 基準値と符号が異なる,またはゼロの場合はエラー
                throw new IllegalArgumentException("Polygon is not convex.");
            }
        }

        for (int i = 0; i < size; i++) {
            Point2D v1 = vertices.get(i); // i番目の頂点
            Point2D v2 = vertices.get((i + 1) % size); // v1の次の頂点
            // 2つの頂点から辺の線分を作成して登録
            edges.add(new LineSegment(
                    v1.getX(), v1.getY(), v2.getX(), v2.getY()));
        }
    }

まとめと次回予告

今回は,多角形の凸性を取り上げました。ベクトルの外積とCCW関数について学習し,CCW関数を使って多角形の凸性判定を行いました。また,凸多角形を表現するConvexPolygonクラスを実装しました。

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

次回は,多角形の包含判定や面積について考えていきます。お楽しみに!

著者プロフィール

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

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

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