Delauney2D.png

任意の点群から逐次追加方、ボロノイ図ドロネー図 を生成します。

 ▼ サンプルプログラム
 ・Delauney2D.zip

 

離散ボロノイ図であれば、3D空間で TCone を重ねていけば簡単に描けてしまいますが、

 ・グラフィックスハードウェアによるボロノイ図の描画とその周辺 @ 山本修身

エッジが線分として明確に定義される 連続ボロノイ図 となると、構造をきちんとオブジェクトとして扱わないといけないので結構面倒です。

もっとも今回は、ボロノイ図を直接生成するのではなく、その双対図形である ドロネー図 を生成することで目的を達します。ボロノイ図のセルは任意の多角形(ボロノイ多角形)になりますが、ドロネー図のセルは常に三角形(ドロネー三角形)なので、一般的なポリゴンモデルと同じようにデータ構造化しやすいからです。

ちなみに今回、アルゴリズムを端的に表現するために、高速化までは施しておりません。点を増やす度に、変更の及ぶドロネー三角形を総当たりで検索しているため、計算時間が O(n) で増加します。なので実用的な目的には、対象空間を格子に区切るなどして、空間最適化を施すべきでしょう。

 

▼ LUX .pas

・function Pow2( const o_:Double ) :Double; inline;
二乗関数 Sqr の名前が分りにくいので、自分好みに変更しました。意味はありません。

・function Roo2( const o_:Double ) :Double; inline;
平方根関数 Sqrt の名前が分りにくいので、自分好みに変更しました。意味はありません。

 

▼ LUX.D2 .pas

・TDouble2D
System.Types.
TPointF では精度が悪いので、Double 精度の代替構造体を作りました。

・TDoubleCircle
 円を定義する構造体です。
 - Center :TDouble2D;
  中心座標。
 - Radius :Double;
  半径。

 

▼ LUX.Delaunay.D2 .pas

・TPoin
 "点"を示すクラスです。
 - Position :TDouble2D
  位置座標。

・TFace
 ドロネー三角形のクラスです。
 - Poin[ const I_:Byte ] :TPoin
  I_ 番目の頂点が依存する TPoin 。
 - Face[ const I_:Byte ] :TFace
  I_ 番目の頂点が対向する TFace 。
 - Corn[ const I_:Byte ] :Byte
  I_ 番目の頂点が対向する頂点番号。
 - Open               :Byte
  どの頂点が無限遠点か。ない場合は 0 。
 - Circle               :TDoubleCircle
  ドロネー三角形の外接円(空円)。
 - function IsHitCircle( const Pos_:TDouble2D ) :Boolean;
  与えられた2D座標が外接円の中にあるか判定するメソッド。

・TDelaunay
 ドロネー図本体としてのクラスです。
 - Poins :TObjectList<TPoin>
  点 TPoin を管理するリスト。
 - Faces :TObjectList<TFace>
  ドロネー三角形 TFace を管理するリスト。
 - function HitCircleFace( const Pos_:TDouble2D ) :TFace;
  与えられた2D座標が、どのドロネー三角形の外接円に含まれるか検索するメソッド。
 - function AddPoin( const Pos_:TDouble2D ) :TPoin;
  指定した2D座標を新たな点としてドロネー図に追加するメソッド。 

 

▼どんなアルゴリズムなの?

すみません、説明が難しいので、後日改めて図をアップします。m(_ _)m 申し訳ありません。