Blogopolisから学ぶ計算幾何

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

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

はじめに

本連載では,ごく単純な直線の式からスタートし,線分,多角形とステップアップしながら計算幾何を学習してきました。その最後の締めくくりとして,今回からは,ボロノイ図の作成方法を見ていくことにします。

ボロノイ図とは

まず,第1回でも簡単に触れたボロノイ図について,改めて説明します。 平面上に複数の母点が配置されているとき,それぞれの母点に最も近くなる点を集めると,母点ごとに「勢力図」のような領域が形成されます。この領域分割図をボロノイ図(voronoi diagram)といいます図1)⁠

図1 ボロノイ図

図1 ボロノイ図

ボロノイ図の各領域をボロノイ領域(voronoi region)と呼び,ボロノイ領域の境界線をボロノイ辺(voronoi edge)と呼びます。

ボロノイ辺の性質

ボロノイ図において,ボロノイ辺が持つ性質を考えてみましょう図2)⁠

図2 2つの母点とボロノイ辺

図2 2つの母点とボロノイ辺

母点aと母点bを隔てるボロノイ辺から少しでもaに向かって移動すると,その地点はbよりもaに近くなります。同様に,辺から少しでもbに向かって移動すると,その地点はaよりもbに近くなります。したがって,aとbを隔てるボロノイ辺は,aとbからちょうど距離の等しい点を集めた直線になることが分かります。すなわち,これはaとbの垂直二等分線(perpendicular bisector)ということになります。

ボロノイ図と最近傍探索

ボロノイ図は計算幾何学の代表的なテーマの1つであり,その応用範囲は多岐にわたります。1つの例として,最近傍探索(nearest neighbor search)問題を紹介しましょう。

ドライブ中にガソリンが少なくなったとき,最寄りのガソリンスタンドはどのようにして見つければ良いでしょうか。このように,点集合の中から最も近い点を探し出す問題を最近傍探索といいます。

解の候補を母点とするボロノイ図をあらかじめ作成しておくと,最近傍探索問題を高速に解くことができます。

図3 ボロノイ図を利用した最近傍探索

図3 ボロノイ図を利用した最近傍探索

図3において,赤い星印からもっとも近い母点を探すには,まず,適当な母点p0を選びます。次に,p0と隣接する母点のうち,星印にもっとも近くなる母点p1を見つけます。このようにして母点を辿っていくと,解である母点xに高速に到達することができます。

ボロノイ図とBlogopolis

もう1つ,ボロノイ図の応用例として,筆者の開発したBlogopolisを挙げてみたいと思います。

図4 Blogopolis

図4 Blogopolis

Blogopolisは,ブロガーがそのブックマーク獲得数に応じた大きさの「土地」を持っており,その土地に各ブログ記事を表す「ビル」が建つという構造になっています。この「土地」「ビル」の区画分けのうち,前者にボロノイ図が使われています。

Blogopolisで使用しているボロノイ図は,加法的重み付きべき乗ボロノイ図(additively weighted power voronoi diagram)と呼ばれるものです。これは,通常のボロノイ図と少し異なり,各母点に重み(weight)が与えられ,母点の距離関数が重みの影響を受けるようになっています。その結果として,各ボロノイ辺が本来の垂直二等分線の位置から平行移動します図5)⁠

図5 通常のボロノイ図(左)と加法的重み付きべき乗ボロノイ図(右)

図5 通常のボロノイ図(左)と加法的重み付きべき乗ボロノイ図(右)

図5の左右を比較すると,大きな重み(円の大きさで示されています)を持つ母点のボロノイ領域が,小さな重みの領域を「押しのけて」いる様子が分かると思います。Blogopolisでは,この重みを適切に設定することで,ボロノイ領域の面積比を意図的に操作し,ブロガーのブックマーク獲得数の比率に一致させているわけです。

著者プロフィール

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

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

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

コメント

コメントの記入