Blogopolisから学ぶ計算幾何

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

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

ボロノイ領域の計算

それではいよいよ,ボロノイ図の計算へと進みましょう。

ある母点のボロノイ領域を求める方針は,次のようになります。まず,途中の計算結果を格納するために,ConvexPolygonオブジェクトを確保しておきます。そして,自身の母点以外の各母点に対し,それぞれ垂直二等分線を計算し,そこから半平面を求めます。この半平面と,途中計算用のConvexPolygonオブジェクトとの交差領域を求め,ConvexPolygonオブジェクトを更新します。こうすると,ConvexPolygonオブジェクトをナイフで少しずつ削るようにして,ボロノイ領域が確定していきます。

以上の方針にしたがって,VoronoiGeneratorクラスを記述してみます。凸多角形の交差計算クラス第10回⁠,そしてPseudoHalfPlaneGeneratorとすでに道具が揃っているので,VoronoiGeneratorクラス自身のコードはかなり簡潔なものになります。

リスト VoronoiGeneratorクラス(Java)

public class VoronoiGenerator {
    private PseudoHalfPlaneGenerator halfPlaneGenerator = new PseudoHalfPlaneGenerator(
            10); // この値を大きくしすぎると計算誤差が無視できなくなる
    private PolygonIntersectionCalculator intersectionCalculator = new PolygonIntersectionCalculator();

    // areaの領域内で,母点sitesの各ボロノイ領域をリストにして返す。
    // areaおよびsitesの各座標が,halfPlaneGeneratorの境界内に収まるように注意すること
    public List<ConvexPolygon> execute(ConvexPolygon area, List<Point2D> sites) {
        List<ConvexPolygon> result = new ArrayList<ConvexPolygon>();
        for (Point2D s1 : sites) {
            ConvexPolygon region = null; // 途中計算結果格納用の領域
            for (Point2D s2 : sites) {
                if (s1 == s2) {
                    continue;
                }
                // s1とs2の垂直二等分線を求める
                Line line = Line.perpendicularBisector(s1, s2);
                // 垂直二等分線による半平面のうち,s1を含む方を求める
                ConvexPolygon halfPlane = halfPlaneGenerator.execute(line, s1);
                if (region == null) { // 初回計算時なら
                    // areaと半平面の交差を求める
                    region = intersectionCalculator.execute(area, halfPlane);
                } else { // 2回目以降なら
                    // これまでの計算結果と半平面の交差を求める
                    region = intersectionCalculator.execute(region, halfPlane);
                }
            }
            // 最終的な計算結果をボロノイ領域とする
            result.add(region);
        }
        return result;
    }
}

VoronoiGeneratorクラスのexecute()メソッドは,areaとsitesの2つの引数を持ちます。areaには,ボロノイ図の外枠となる図形を指定します。sitesは,各母点の座標リストです。計算が終了すると,各母点に対応するボロノイ領域のリストが戻り値として得られます。

デモプログラム

今回解説したアルゴリズムをグラフィカルに動作確認できるよう,Swingアプリケーションのデモプログラムを用意しました。Java Web Start形式になっており,こちらをクリックして直接起動できます。ソースコードは本記事には掲載しませんので,アーカイブをダウンロードして確認してください。

図3 デモプログラム

図3 デモプログラム

デモプログラムを起動すると,キャンバスに複数の母点と,その母点から作成されるボロノイ図が表示されます。キャンバス上でマウスクリックやドラッグをすることで,母点を自由に追加または移動したり,削除したりすることができます。

最後に

最終回となる今回は,ボロノイ図を作成するプログラムを完成させました。このプログラムには,第1回からのほぼすべての学習内容が応用されています。道具を少しずつ積み上げることによって,より難しい問題が解けるようになることを実感していただけたのではないでしょうか。

今回作成したプログラムのソースコードは,こちらからダウンロードできます。

本連載をきっかけとして,計算幾何学を利用した面白いソフトウェアが生まれることを願っています。12回にわたってお付き合いいただき,ありがとうございました!

著者プロフィール

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

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

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