Blogopolisから学ぶ計算幾何

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

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

はじめに

今回は,凸性を持つ多角形について考察していきます。多角形は辺として線分を持ちますので,前回までに学習した線分の知識は,そのまま多角形の幾何にも活かすことができます。

凸多角形とは

図形に凹みが存在しないとき,その図形は凸であるといいます。もっと厳密に述べると,図形の内部のどんな2点をとっても,その2点を結ぶ線分が図形に含まれるとき,図形は凸になります。図1の場合,左の図形は凸ですが,右の図形は凸ではありません。

図1 凸性

図1 凸性

さて,凸性のある多角形を凸多角形(convex polygon)と呼びます。

Blogopolisでは,島の外郭が凸多角形になっています(図2)⁠そして,島の内部のあらゆる土地の区画もまた,例外なく凸多角形になっています(図3)⁠これは,凸多角形が計算処理上,便利な性質を多く備えているため,凸多角形を意図的に採用しているのです。

図2 Blogopolisの外郭

図2 Blogopolisの外郭

図3 Blogopolisの内部

図3 Blogopolisの内部

今回は,この凸多角形がテーマになります。

凸多角形クラスの作成

まず,凸多角形を表現するクラスを用意しておきましょう。以下のようにConvexPolygonクラスを作成します。このクラスは,コンストラクタで頂点(vertex)の座標リストを与えるものとします。また,頂点の座標リストをもとに凸多角形の辺(edge)を作成し,LineSegmentオブジェクトのリストとして保持するものとします。

LineSegmentオブジェクト(Java)

public class ConvexPolygon {
    private List<Point2D> vertices; // 頂点
    private List<LineSegment> edges; // 辺

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

    // 指定位置の頂点を取得
    public Point2D getVertex(int index) {
        return vertices.get(index);
    }

    // 指定位置の辺を取得
    public LineSegment getEdge(int index) {
        return edges.get(index);
    }

    // 辺の数(=角数)を取得
    public int getEdgeCount() {
        return edges.size();
    }
}

凸性の判定

ConvexPolygonクラスを作成したことで,凸多角形のデータ構造は準備できました。しかし,コンストラクタに渡された頂点座標のリストが,凸多角形の条件をみたしているかどうかは分かりません。ここで,ConvexPolygonオブジェクトが凸になることを保証するために,頂点リスト引数の検査を行い,凸でない場合はエラーを発生させたいとします。

多角形の頂点データをもとに,その多角形が凸であるかどうかを判定するには,どうすれば良いのでしょうか。

図4を見てください。多角形の1頂点から出発して,一筆書きのように辺を巡回し,元の頂点に戻ってくる道のりを考えます。新しい頂点に到達したとき,進行方向に回転が加わるわけですが,凸多角形の場合,その回転方向はすべて左向き(反時計回り, counterclockwise)か,右向き(時計回り, clockwise)で統一されています。

図4 多角形と辺の回転の向き

図4 多角形と辺の回転の向き

これに対し,凸でない多角形では,凹んでいる頂点のところで回転の向きが逆になります。すなわち,時計回りと反時計回りが混在するのです。このように,多角形の辺の回転方向を調べることで,凸性を判定することができます。

以下,回転方向の計算に求められる知識として,ベクトルの外積と,外積にもとづくCCW関数について見ていくことにします。

ベクトルの外積

高校数学で学んだベクトルの内積を憶えているでしょうか。ベクトルaとbの内積(a・b)はスカラーとなり,aとbのなす角度θを使って以下の式で表されます。

式1 ベクトルの内積

式1 ベクトルの内積

さて,この内積と同じく重要性の高いベクトル演算に,外積というものがあります。3次元ベクトルの世界で,ベクトルaとbの外積(a×b)はベクトルとなり,その大きさは以下の式で表されます。

式2 ベクトルの外積の大きさ

式2 ベクトルの外積の大きさ

また,その向きはaとbを含む平面に垂直で,aからbへ右ねじが進む方向になります。この様子を図5に示します。

図5 外積の向き

図5 外積の向き

図5を見ると,xy平面上のベクトル同士の外積をとった場合,その結果のベクトルはz軸とちょうど重なり,xとyの成分は常にゼロになることが分かります。したがって,xy平面しか使わない平面幾何の世界では,単に外積の大きさ,つまりz成分のスカラー量だけを指して「外積」ということがあります。本連載でもこの考え方を採用し,外積をスカラーとします。

著者プロフィール

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

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

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

コメント

コメントの記入