Blogopolisから学ぶ計算幾何

第12回 ボロノイ図の作成(後編)

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

はじめに

前回は,半平面の交差にもとづいてボロノイ図を計算するための考え方を説明しました。最終回となる今回は,疑似半平面の生成を実装した上で,ボロノイ図作成のプログラムを完成させます。

凸多角形による疑似半平面表現

前回も述べた通り,ある母点のボロノイ領域を求めるには,その母点と他の各母点の垂直二等分線から作られる全ての半平面の交差を計算する必要があります。すでに学習済みの凸多角形の交差計算方法を,そのまま半平面の交差計算にも利用するため,半平面を擬似的に凸多角形へと変換することを考えます。

図1を見てください。点線で囲まれた正方形の内部が,実際にボロノイ図の計算を行いたい座標範囲だとします。この正方形を取り囲むように,三角形が置かれています。(0, -10)といった頂点座標のとり方に特別な意味はなく,正方形を覆い尽くしていることがポイントです。

図1 境界三角形の設定

図1 境界三角形の設定

ある直線が与えられたとき,図2の緑色部分のように,三角形を直線で切断するかたちで凸多角形を生成すれば,この凸多角形は実用上,直線による半平面と同等だと見なすことができます(境界の図形には三角形ではなく四角形などを使ってもかまいませんが,三角形を使うことで,切断の計算をよりシンプルに記述できます)⁠

図2 疑似半平面

図2 疑似半平面

実際にこの切断を行い,疑似的な半平面を生成するPseudoHalfPlaneGeneratorクラスの実装を以下に示します。このクラスはまず,コンストラクタで指定された大きさを使い,図1と相似な三角形を用意します。その後,execute()メソッドで半平面を作成します。

execute()メソッドは,直線のline引数と例示点のexample引数を持ちます。lineによって作られる2つの半平面のうち,exampleを含む方の半平面に対応する疑似半平面が,ConvexPolygonオブジェクトとして作成されます。

リスト PseudoHalfPlaneGeneratorクラスの実装(Java)

public class PseudoHalfPlaneGenerator {
    private Point2D boundary1; // 境界点1
    private Point2D boundary2; // 境界点2
    private Point2D boundary3; // 境界点3
    private LineSegment border1; // 境界線1
    private LineSegment border2; // 境界線2
    private LineSegment border3; // 境界線3
    private double distanceThreshold; // 交差の場合分けを正確に行うための閾値

    // boundaryの値を大きくすると計算誤差が無視できなくなるので注意!
    public PseudoHalfPlaneGenerator(double boundary) {
        boundary1 = new Point2D.Double(0, -boundary);
        boundary2 = new Point2D.Double(-boundary, boundary);
        boundary3 = new Point2D.Double(boundary, boundary);
        border1 = new LineSegment(boundary1, boundary2);
        border2 = new LineSegment(boundary2, boundary3);
        border3 = new LineSegment(boundary3, boundary1);
        distanceThreshold = boundary / 1000.0;
    }

    public ConvexPolygon execute(Line line, Point2D example) {
        // lineと各境界線の交差を調べる
        Point2D p1 = border1.getIntersectionPoint(line);
        Point2D p2 = border2.getIntersectionPoint(line);
        Point2D p3 = border3.getIntersectionPoint(line);

        List<Point2D> vertices = new ArrayList<Point2D>();
        // lineが境界線1および2と交差する場合
        if (p1 != null && p2 != null && p1.distance(p2) >= distanceThreshold) {
            // 境界点2とexampleがlineから見て同じ側にあるなら
            if (GeomUtils.ccw(p1, boundary2, p2)
                    * GeomUtils.ccw(p1, example, p2) > 0) {
                // 境界点2を含む方の切断後頂点リストを生成
                addVertices(vertices, p1, boundary2, p2);
            } else { // そうでないなら
                // 境界点2を含まない方の切断後頂点リストを生成
                addVertices(vertices, p1, p2, boundary3, boundary1);
            }
        } else if (p2 != null && p3 != null
                && p2.distance(p3) >= distanceThreshold) { // lineが境界線2および3と交差する場合
            // 境界点3とexampleがlineから見て同じ側にあるなら
            if (GeomUtils.ccw(p2, boundary3, p3)
                    * GeomUtils.ccw(p2, example, p3) > 0) {
                // 境界点3を含む方の切断後頂点リストを生成
                addVertices(vertices, p2, boundary3, p3);
            } else { // そうでないなら
                // 境界点3を含まない方の切断後頂点リストを生成
                addVertices(vertices, p2, p3, boundary1, boundary2);
            }
        } else if (p3 != null && p1 != null
                && p3.distance(p1) >= distanceThreshold) { // lineが境界線3および1と交差する場合
            // 境界点1とexampleがlineから見て同じ側にあるなら
            if (GeomUtils.ccw(p3, boundary1, p1)
                    * GeomUtils.ccw(p3, example, p1) > 0) {
                // 境界点1を含む方の切断後頂点リストを生成
                addVertices(vertices, p3, boundary1, p1);
            } else { // そうでないなら
                // 境界点1を含まない方の切断後頂点リストを生成
                addVertices(vertices, p3, p1, boundary2, boundary3);
            }
        } else {
            throw new IllegalArgumentException(
                    "Cannot create a pseudo half plane.");
        }

        // 頂点リストから凸多角形を生成して返す
        return new ConvexPolygon(vertices);
    }

    // listにpointsを追加する。このとき,同一座標の重複追加を避ける
    private void addVertices(List<Point2D> list, Point2D... points) {
        for (Point2D p : points) {
            if (list.isEmpty()) {
                list.add(p);
            } else {
                Point2D first = list.get(0);
                Point2D last = list.get(list.size() - 1);
                if (!p.equals(first) && !p.equals(last)) {
                    list.add(p);
                }
            }
        }
    }
}

著者プロフィール

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

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

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

コメント

コメントの記入