はじめに

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

凸多角形とは

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

さて、凸性のある多角形を凸多角形（convex polygon）と呼びます。

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

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

凸多角形クラスの作成

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

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）で統一されています。

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

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

ベクトルの外積

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

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

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

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

外積の計算

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

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

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

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

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

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に示します。

外積と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()メソッドも用意することにします。

    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値の正負が統一されているかどうかをチェックしていけば良いことになります。

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

    // 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クラスを実装しました。

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