はじめに

前々回は凸多角形を取り上げましたが，今回はその凸多角形に対する演算として，点の包含判定方法と面積の計算方法を学習します。

Blogopolisにおける多角形の点包含判定と面積計算

Blogopolisでは，多角形の土地にマウスカーソルを合わせると，その土地がハイライト表示され，さらにクリックすることで土地の詳細情報が表示されるようになっています（図1⁠）⁠。内部的には，マウスカーソルが移動するたびに，その座標が画面上の各多角形の内部にあるか，外部にあるかを判定しているわけです。

また，Blogopolisでは，1つ1つのブログ記事を表す土地の面積が，その記事へのはてなブックマーク数に応じて決められており，多くのブックマークを集めた記事ほど大きな土地を獲得するようになっています。これは内部的には，土地の区画を生成する過程で，各多角形の面積を計算しながら，適切な面積比になるような調整を行っているわけです。

こうした「点の包含判定」や「面積の計算」といった演算は，長方形や円に対して行うのであれば非常に簡単です。しかし，Blogopolisのような多角形の場合，どうすれば良いのでしょうか。

多角形の点包含判定

まず，凸多角形の点包含判定問題を考えます。これは，与えられた点(x, y)が，凸多角形の内部にあるか，それとも外部にあるかを調べるものです。

点(x, y)を始点とし，右水平方向に永遠に延びる半直線（half-line）を考えます。もし，点が凸多角形の内部に存在するのであれば，この半直線は，多角形の「境界から脱出する」ために，多角形が持ついずれかの辺と，必ず1回交差します（図2⁠）⁠。

一方，点が凸多角形の外部に存在するのであれば，半直線は多角形の辺とはまったく交差しないか，一度多角形の内部に「突入」してから「突き抜ける」かたちになります。つまり，半直線と辺の交差回数は，0回または2回になります（図3⁠）⁠。

このように，凸多角形に対しては，半直線と辺の交差回数が1回であれば点を包含しており，0回か2回であれば包含していないと判断することができます。

なお，以上の判定条件は，凸でない多角形についても一般化が可能です。一般の多角形に対しては，半直線と辺の交差回数が奇数であれば点を包含しており，偶数であれば包含していないと判断できます。

この方針にしたがい，前回作成したConvexPolygonクラスに，半直線と辺の交差回数の偶奇から点の包含を判定するcontains()メソッドを記述してみましょう。ここで問題となるのは，半直線のクラスを本連載では作成していないことです。しかし，十分な長さを持つLineSegmentオブジェクトを用意すれば，これは擬似的に半直線と見なすことができますので，今回はLineSegmentオブジェクトを半直線の代用とすることにします。

public boolean contains(double x, double y) {
    // 多角形のy座標範囲を求める
    double minY = Double.POSITIVE_INFINITY;
    double maxY = Double.NEGATIVE_INFINITY;
    for (Point2D v : vertices) {
        minY = Math.min(minY, v.getY());
        maxY = Math.max(maxY, v.getY());
    }
    // yが最小値-最大値の範囲外の場合はfalseを返す
    if (y <= minY || y >= maxY) {
        return false;
    }
    // 与えられた座標を始点とし，右方向に十分長く延びる擬似的な半直線を作成
    LineSegment halfLine = new LineSegment(x, y, x + 10000000, y);
    int count = 0;
    for (LineSegment edge : edges) {
        // 半直線が辺の終点とちょうど重なる場合，次の辺の始点とも交差が検出され，
        // 二重にカウントされてしまうため，カウントをスキップする
        if (edge.y2 == y) {
            continue;
        }
        if (edge.intersects(halfLine)) {
            count++;
        }
    }
    // 交差回数が奇数の場合は点を包含
    return count % 2 == 1;
}

上のコードでは，初めに多角形のy座標範囲を求めた後，渡された点のy座標がその範囲にない場合は，交差回数をチェックせずにfalseを返すようにしています。このようにしないと，点のy座標が多角形の一番上の頂点または一番下の頂点のy座標と一致する場合に，正しい判定が行われない可能性があります（なぜか考えてみてください⁠）⁠。

念のため再度述べますが，この点包含判定のアルゴリズムは，凸でない多角形にも適用できます。