高速なドロネー三角形分割

https://gyazo.com/47b1f3de543953e5f24cee8453d25eac

「コンピュータジオメトリ」という書籍を参考にして、これに載ってるドロネー三角形分割のやりかたを実装してみた。

この本は、幾何アルゴリズムの証明や計算量の解析が載っていて、しかも日本語で書かれているという徳の高い本。

理論どおりの計算量に近付けるための工夫というか、データ構造のもちかたも載っていて、その辺もまったく知らなかったので初学者にとっては貴重な情報源な気がする。

でもけっこう難しい。空間的な操作の翻訳の日本語での説明は、同じところを4回くらい読むという手法でなんとか読みすすめられたたけど、数式や知らない定理がでてくるところがけっこうあって、そっちの知識が不足しているからがんばってなんとか読めたかんじだった。

三角形分割は好きな形状のなにかを画面に描きたいとおもったときに必要になりそうだったので、実装してみたかったアルゴリズム。 この本で紹介されているドロネー三角形分割は、隣接する三角形の辺を交換するというただそんだけの操作を再帰的にやるだけで実装できるため、総当たりな探索をほぼやらずににけっこう高速に実装できる余地があるものだった。

ドロネー三角形分割とは

ドロネー三角形分割は、任意の点を与えてあげると、それらを線で結んで、三角形が敷き詰められた状態にするアルゴリズム。

ドロネー三角形分割と呼ばれているけど、ボロノイ図のセル同士をあるルールで線で結んだ「ドロネー図」というグラフがあり、これをよく見ると、角度最適な三角形の集合になっとる、という特徴を持っている。ということらしい。

つまり、ドロネー三角形分割をするということと、ドロネーグラフを描くということはほぼ同じことのようです。

角度最適な三角形分割

任意の点の集合から三角形分割を得るには、結果はひとつではなく、幾通りかの結果がありえる。

また、そのうち、どの三角形分割が望ましいか、かっこいいか、についても、色々な基準があるみたいだけど、ドロネー三角分割は、「三角形の最小角度が最大になる」分割方法になる。

反対に、三角形の最小角度が最大になる三角形分割は、ドロネーグラフであることの必要充分条件であるので、これをアルゴリズムの判定につかう。

ある三角形が、ドロネーグラフの一部かどうかの判定は、ボロノイ図の性質を応用すると、その三角形の外接円の内部に他の点が含まれているかどうか? を調べるだけでわかる。

しかし、この判定のやりかただと、どの点を調べるべきかどうかが定まらないので、比較対象の点が多くなってしまう。

そこで、「三角形が不正かどうか」ではなく、「辺が不正かどうか」という概念を導入する。

不正な辺とは、もしその辺を「フリップ」して三角形をつくりなおした場合に、より角度が最適な三角形になる場合のことを言う。

辺フリップとは、つまり、その辺を一旦ぶち消して、2つの三角形を1つの四角形に戻した後で、別の対角線をつかって分割をやりなおす操作。

「不正な辺」かどうかの判定をするには、その辺と隣接している三角形だけが対象になるので、総当たりで探索する必要がなくなる。

分割の途中経過を有向グラフで管理する

もうひとつおもしろいと思った工夫が、三角形分割した結果だけをメモリに持つのではなく、分割する過程ででてきた親の三角形や、辺フリップ前の不正な三角形もとりあえずメモリにすべて残しておいて、どんな道筋で分割されてきたからの過程もすべてグラフで管理しておく。というもの。

このデータ構造をもっておくことによって、ある点が含まれている三角形を調べたいときに、ぜんぶの三角形を調べなくてもよくなる。 上から辿っていき、ヒットした三角形に子ども(つまり分割後や辺フリップ後の三角形)が存在したら、そっちも調べる。このやりかたを導入すると、高々グラフの高さの回数だけ判定すれば良くなる。

流れ

アルゴリズムの全体の流れ実装には、逐次添加法を使う。 三角形分割したい点の集合のうち、点をひとつずつ添加していて、その時点での三角形分割をつくっていく。

点をひとつ追加する

新しく追加された点を含んでいる三角形をみつける

その三角形を、新しい点が頂点になるように３つに分割する (点が辺の上にある場合は4つに分割する)

分割してできた三角形は、新しく追加された辺を3つ含んでいる。この3つの辺が「不正な辺」かどうか判定する

「不正な辺」を、辺フリップする

辺フリップすると、新しい辺が生まれるので、この新しい辺についても「不正な辺」かどうか判定し、もしそうなら辺フリップする

これを再帰的におこなう

一応、このやりかたで実装してみたサンプルがこれ。

https://vimeo.com/332447471

これは任意の制御点をきれいに曲線で結んだ形状を自動生成する UI コンポーネント。

さわるとぐにゃぐにゃします。

任意の制御点を移動させるだけで「ぐにゃ」るというのはたぶん使いやすいインターフェースだと思う(たぶん)

https://gyazo.com/8feee0aebfe2d42e46418f667c34ccee