Blogopolisから学ぶ計算幾何

第11回 ボロノイ図の作成(前編)

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

半平面交差にもとづくボロノイ図の作成

それでは,ボロノイ図を作成する具体的なアルゴリズムを考えていきましょう。今回は,直感的に理解しやすく実装も容易な,半平面交差にもとづく方法を取り上げます(本連載では扱いませんが,より高度なアルゴリズムとして,平面走査法にもとづくFortuneのアルゴリズムと呼ばれる手法もあります⁠⁠。

図6 ボロノイ領域

図6 ボロノイ領域

図6を見てください。母点aを母点b, c, dが取り囲んでいるとき,母点aのボロノイ領域はどのような形状になるでしょうか。容易に分かるように,これは,aとb,aとc,aとdそれぞれの垂直二等分線で囲まれた三角形です。

このことは,次のように言い換えることができます。aとbの垂直二等分線によって作り出される2つの半平面(half plane)のうち,aを含む方の半平面をh(a, b)とおきます。同様に,半平面h(a, c)とh(a, d)を考えます。すると,母点aのボロノイ領域は,h(a, b), h(a, c), h(a, d)の3つの半平面の共通部分,すなわち交差領域として求めることができます。

母点の数がどれだけ増えても,この考え方はそのまま適用可能です。ある母点のボロノイ領域は,その母点と他の各母点の垂直二等分線から作られる半平面の交差領域となるのです。

さて,前々回前回と,凸多角形同士の交差領域を計算する方法を学習してきたので,これをうまく流用することを考えます。半平面は無限に広がる領域ですが,その平面分割線を辺として持つ十分に大きな凸多角形を作れば,その凸多角形は実用上,半平面と見なすことができます。したがって,半平面から凸多角形への変換作業を行うことで,凸多角形の交差計算のアルゴリズムをそのまま用い,半平面の交差領域が求められることになります。

垂直二等分線の計算

半平面を凸多角形に置き換える方法は次回に譲ることにして,今回はまず,垂直二等分線の計算を実装しておきます。

点p1の座標を(x1, y1),点p2の座標を(x2, y2)とするとき,p1とp2の垂直二等分線の方程式を求めてみましょう。

垂直二等分線を次のように媒介変数表示してみます。

画像

垂直二等分線はp1とp2の中点を通るので,上の式において

画像

となります。

次に,mとnの値を求めます。垂直二等分線と,p1とp2を結ぶ直線は直交するので,この2つの直線から作った2つのベクトルの内積はゼロになるはずです。すなわち

画像

となり,これを計算すると,mとnを例えば次のように決めることができます。

画像

以上で媒介変数表示が完成したので,tに適当な値を2つ(例えば0と1)代入して,垂直二等分線が通る2点を求めます。この2点を前回までの連載で実装済みのLine#fromPoints()メソッドに渡すことで,直線オブジェクトを作成できます。

それでは,この方針にもとづき,LineクラスにperpendicularBisector()メソッドを追加してみましょう。

リスト perpendicularBisector()メソッドの追加(Java)

public static Line perpendicularBisector(double x1, double y1,
        double x2, double y2) {
    double cx = (x1 + x2) / 2.0;
    double cy = (y1 + y2) / 2.0;
    return fromPoints(cx, cy, cx + (y1 - y2), cy + (x2 - x1));
}

次回以降,この垂直二等分線をもとに半平面を生成し,ボロノイ図の作成へと進んでいきます。

まとめと次回予告

今回は,本連載最後のトピックとして,ボロノイ図の説明を行いました。ボロノイ辺が母点の垂直二等分線になっているという性質を示し,ボロノイ図の作成の準備段階として,2点の座標から垂直二等分線を求めるコードを実装しました。

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

次回は,凸多角形の交差計算アルゴリズムを利用して半平面の交差領域を求め,ボロノイ領域を計算する段階へと入っていきます。お楽しみに!

著者プロフィール

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

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

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