点の集まりに「隣」を入れる —— ボロノイ図とドロネー三角形分割 #
Note
執筆: Devin(SWE-2 Max)。図はすべて
tools/svg-genのジェネレータが実際の幾何を計算して描いたもの。
散らばった10個の点だけがあるとする。点そのものには順番もつながりもない。この「ただの点の集まり」に対して、誰が誰の隣なのかを自然に決める方法が2つある。領域で考えるボロノイ図と、辺で考えるドロネー三角形分割だ。
「隣」が欲しい場面は多い。標高点の間を補間する地形モデル、板や流体を小さな要素に割るメッシュ生成、そして点の集まりをそのまま絵に変換する生成系アート。どれも最初の一歩は、この点だけの集合から構造を引き出すところだ。
この記事では垂直二等分線から始めて、2つの構造が同じものの表裏(双対)であるところまでを図で追う。以降の図はすべてこの10点を使い回し、凡例も記事全体で統一する。実線がドロネー側(三角形分割の辺)、破線がボロノイ側(セルの境界や二等分線)、太線は注目する要素、朱系のマークは「違反・ダメ」の印だ。
準備: 4つの道具 #
垂直二等分線 #
2点から等距離にある点の集まりは1本の直線になる。垂直二等分線だ。線の上ならどこへ動いても2点からの距離は等しい。
この直線は平面を2つの半分に割る。ある点側の半分(半平面という)は「もう一方の点よりその点に近い場所」の全体で、これがあとでボロノイ図のセルを組み立てる部品になる。
外接円と外心 #
一直線に並ばない3点を通る円はただ1つある。2つの辺の垂直二等分線は必ず1点で交わり、その点は3点すべてから等距離にある。この点を外心、できる円を外接円という。あとで何度も出るので覚えておきたい道具だ。
凸包 #
点集合を全部含む最小の凸多角形。凸とは「内部のどの2点を結ぶ線分も外にはみ出さない」ことで、ゴム紐を外側から締めた形と思えばよい。三角形分割はこの内側全体を覆う。
三角形分割 #
点を頂点とし、交差しない辺で凸包を三角形に埋め尽くしたもの。辺が途中で交わるのは認めない。
ついでに1つ仮定を置く。以降の話では点群が「一般位置」にある、すなわち3点が同一直線上にない・4点が同一円周上にないとする。これが崩れると話が分岐するのだが、詳しくは後半の退化の節に回す。
ボロノイ図: 一番近い点で割り分ける #
各サイト(母点)に対して「そのサイトが一番近い領域」を割り当てたものがボロノイ図だ。「サイト s に一番近い」領域は、他のサイト t それぞれについて「t より s に近い半平面」を全部掛け合わせたものになる。境界は垂直二等分線なので、セルは半平面の交わりとして切り取られていく。凸な形同士の交わりは凸なので、セルは必ず凸だ。
全体を描くとこうなる。内部のサイトのセルは有界な凸多角形、凸包の上に乗ったサイトのセルは無限に伸びる。外側には対になるサイトがいないので、境界が閉じないのだ。
ここで重要な観察。セルの角(ボロノイ頂点)は3つのセルが接する点で、3サイトから等距離にある。つまり3サイトの外接円の中心だ。しかもその円の中に他のサイトは入らない。入っていたらそのサイトの方が近いので、この点は3サイトのセルの接点にはなりえない。
ドロネー三角形分割: 双対を取る #
ボロノイ図ができたら、隣り合うセルの持ち主同士を全部結ぶ。それがドロネー三角形分割で、ボロノイ図の双対グラフになる。「双対」は役割の取り換えのことで、ボロノイ側のセル(領域)がドロネー側の頂点(サイト)に、セル同士の共有辺がドロネーの辺に、3セルの接点がドロネーの三角形に対応する。
この三角形分割には3つの顔がある。
- いまの定義(ボロノイ図の双対)
- 空円性: 各三角形の外接円の内部に、他のサイトを含まない
- 最小角の最大化: 全部の角を小さい順に並べた角度ベクトルを辞書式に最大化する
空円性が双対と一致するのは、さっきの観察の裏返しだ。セルが接する ⟺ その3サイトを通る空の円がある ⟺ 対応する三角形ができる。逆に言うと、外接円にサイトが入ってしまう分割はドロネーではない。
3つ目の顔は最適性。全部の三角形の角を集めて小さい順に並べた列を角度ベクトルという。2つの分割を比べるときは、先頭(最小角)が大きい方が勝ちで、同じなら次の角同士を見る、という辞書式の比較をする。ドロネーは、同じ点集合の全三角形分割の中でこの順序の最適解になる。特に最小角が最大になるので「細長い三角形が避けられる」とよく言われるが、あくまで同じ点集合の中での最適なので、点の配置が強制する細さは消えないことに注意したい。
個数も公式で決まる。n 個の点のうち凸包上にあるものを h 個とすると、どんな三角形分割でも同じ数になる。平面グラフの Euler の公式(頂点−辺+面=2)に「内側の面は全部三角形」という条件を入れると出る式だ。
| 量 | 式 | この10点の場合 |
|---|---|---|
| 三角形の数 | 2n − 2 − h | 11 |
| 辺の数 | 3n − 3 − h | 20 |
修復の仕組みもシンプルだ。外接円にサイトが入ってしまう「違法」な辺は、両側の三角形が作る四角形の対角線を入れ替えるだけで直せる。この操作をエッジフリップと呼ぶ。そして「全ての内部辺が局所的に空円条件を満たせば、全体がドロネー」という Delaunay の補題がある。違法な辺をフリップすると必ず角度ベクトルが改善し、改善は有限回で止まるので、止まったときには違法な辺が残っていない。つまりどんな三角形分割からでも、フリップの連鎖でドロネーに辿り着く。
双対の細部と退化 #
ドロネー辺の正確な特徴づけを確認しておこう。辺 pq がドロネーなのは「p, q を通る空円が存在する」ときで、「両端点を直径とする円が空」ではない。後者はより強い条件で、その辺は Gabriel 辺と呼ばれる別物だ(Gabriel ならドロネーだが、逆は成り立たない)。最小の反例は鈍角三角形1枚: 最長辺は外接円が空なのでドロネーだが、直径円は向かいの鈍角頂点を含む。円周角の定理で、直径を見込む角は円周上ならちょうど90°、円の内側からだと鈍角になる。だから鈍角の対辺は Gabriel になれない。
ドロネー辺とその双対ボロノイ辺は互いに垂直だが、線分としては交わらないこともある。上の例がまさにそうで、ボロノイ側の辺は鈍角三角形の外側に飛び出してしまう。
退化の話。4点が同一円周上にあるとドロネーは一意でない。どちらの対角線を取っても外接円は同じ大きな円(=空)なので、どちらも合法だ。対応するボロノイ頂点は3つではなく4つのセルが接する点になる。
ほかにも3点以上の共線や重複点が退化になる。実装上は記号摂動(点を無限小だけずらしたと仮想的に思うことで退化を消す技法)で扱うか、非一意であることを受け入れて任意に決める。あと「点 d が三角形の外接円に入るか」という円内判定は、座標から組める行列式の符号1つで書けるのだが、浮動小数点だと共円に近い入力で符号を取り違えるので、まともな実装では厳密な述語を使うのが定石だ。
作り方 #
中心となる操作はさっきのフリップだが、全体を一気に作る方法もいくつかある。概観だけ。
逐次添加(Bowyer–Watson)は実装が素直でよく使われる。新しい点を1つ入れ、その点を内包する外接円を持つ三角形を全部消し、残った穴(cavity)の境界を新しい点に縫い付ける。上の図のジェネレータ自体、このアルゴリズムを数十行で書いたものが動いている。
掃引線(Fortune)はボロノイ図を直接作る。放物線は「1点(焦点)と1直線(準線)から等距離にある点の集まり」なので、焦点=サイト・準線=掃引線として立てた放物線の上の点は、サイトと掃引線のちょうど真ん中にいる。サイトごとにこの放物線を立てると、それらの山なりの天辺(beach line)が掃引線の進行とともにボロノイ辺を吐いていく。放物線同士が交差する位置がちょうどボロノイ頂点だ。
放物面リフトは一番美しい見方。(x, y) の点を放物面 z = x²+y² の上の点 (x, y, x²+y²) に持ち上げると、ドロネーは持ち上げた点群の下側凸包(下から見上げたときに見える面)を射影したものになる。円が平面に、円内判定が「面の上下の比較」に化けるのがミソだ。1次元で書くと雰囲気が分かる: 1次元のドロネーはソート済みの隣接関係で、下側凸包はちょうど隣の点を結ぶ弦になる。間を飛ばす弦は、間の点がその下に出るので下側凸包にはならない。
計算量のまとめ。n は点の数で、O(...) は入力が増えたときの手間の増え方のおおよその見積もりだ。下界は Ω(n log n) で、1次元でもソートに帰着するのでこれより速くはならない。
| 手法 | 計算量 |
|---|---|
| Lawson のフリップ | O(n²) |
| Bowyer–Watson | 期待 O(n log n)、最悪 O(n²) |
| 分割統治(Guibas–Stolfi) | O(n log n) |
| Fortune | O(n log n) |
| 3次元凸包経由 | O(n log n) |
実用上はライブラリに任せればよい。Python なら scipy.spatial の Delaunay と Voronoi(Qhull 経由)で一瞬で出る。
性質と応用 #
ドロネーにはいくつもの近接グラフが包摂される。最近接グラフ ⊆ ユークリッド最小全域木 ⊆ 相対近傍グラフ ⊆ Gabriel グラフ ⊆ ドロネー、という包含列だ。同じ点群で並べると差が見える。
各グラフの定義はこんな感じで、内側ほど辺が疎になる。
- 最近接グラフ(NNG): 各点から一番近い点へ辺を張る
- ユークリッド最小全域木(EMST): 全点を総延長最小でつなぐ木
- 相対近傍グラフ(RNG): 辺 pq について、p, q を中心・|pq| を半径とする2円の重なり(月形)に他の点がない
- Gabriel グラフ: 辺 pq を直径とする円の中に他の点がない
月形は直径円より細い領域なので RNG の条件の方がきつく、辺は少なくなる。Gabriel 辺はドロネー辺の絞り込みなので、全部がドロネーに含まれるのも自然だ。
内側に含まれるものから、いくつか便利な性質が効いてくる。
- どの点の最近接点もドロネー隣接にあるので、最近接探索の候補は隣接だけに絞れる
- ユークリッド最小全域木の辺は全部ドロネーに含まれる
- ドロネーの辺だけを歩いても、どの2点間も直線距離の定数倍以内の道で行ける(t-スパナ)。この定数の上界は 1.998 未満と示されていて、最近では 1.6 程度まで絞る報告もある
応用をざっと。
- メッシュ生成: 有限要素法などの素地。ただしドロネー単体では点群の強制する細さが残るので、入力とは別に新しい点(Steiner 点)を賢く足していく Delaunay refinement で角度の下限を保証するのが実務。境界を固定したい場合は制限ドロネー(CDT)
- 地形モデリング(TIN): 標高点群から三角網を作り、補間や等高線へ
- 補間: natural neighbor 補間はボロノイセルの面積比で重みを決める
- ネットワーク・経路: スパナ性を幾何ルーティングの足場に、Gabriel グラフは平面化に使われる。ボロノイ辺は障害物サイトからの最大余白軌道としてロボット経路計画でも使われる
- 形状復元: alpha shapes は、外接円の半径が基準値 α を超える三角形・辺を落としてできるドロネーの部分複体。α を絞るほど点群の輪郭が彫り出される
- 画像・描画: セルの重心にサイトを移す Lloyd 反復を繰り返すとセルが均等化する(重心ボロノイ分割、CVT)。サイトの密度を画像の濃淡に合わせれば stippling / blue noise になる
メディアアート方面での使われ方も面白い。セルの塗り分けはそのままステンドグラス風の見た目になり、三角形のフラット塗りはローポリ風になる。しかも同じ点群から両方出せる。
実例もいくつかある。Golan Levin は Voronoi の網目をポートレートに重ねたシリーズを雑誌のために作っていて、Raven Kwok は来場者の顔からサイトを生成するインタラクティブ展示を UCCA に納めている。ローポリ風の Delaunay ポートレートは定番のジャンルだ。リンクは参照メンバーにまとめてある。
その先 #
- 3次元: 空球性で四面体分割になる。ただし角度の最適性は消え、外接球が空でも sliver と呼ばれるペラい四面体が残る。四面体数は最悪 Θ(n²)
- 制限ドロネー(CDT): 指定した辺を必ず残す緩和版。実務のメッシュや GIS はこちら
- 重み付き: サイトに重み(円の半径など)を持たせ、距離から重みを引いて比較する版。power diagram(Laguerre–Voronoi)と、それに双対する正則三角形分割に対応
- 高次ボロノイ: 「k 番目に近い点」で分割する版。その逆に「一番遠い点」での分割が farthest-point ボロノイ
まとめ #
- ボロノイ図は「一番近い点」で平面を割り分けたもの。セルの角は空の外接円の中心
- ドロネー三角形分割はその双対。空円性・最小角最大化と同じものの別の顔
- どちらも「ただの点」から隣接関係を引き出す仕組みで、だからこそメッシュ生成からメディアアートまで使い道が広い
参考にした資料は別メンバーにまとめてある(AI が集めたもの、各項目に確認範囲つき)。図の生成器は tools/svg-gen/examples/fig-*.ts、共有の点群と幾何プリミティブは同じく examples/geom.ts にある。