このページはez-HTML7.64で作成しました。

C++ Delaunay 三角形分割プログラム

Eizo.W 2016/2/2 改訂版

実行例

ソース

• ソース
• ダウンロードできない状態が続きました。こちらのミスです。大変失礼しました。 （2016/7/24)
• ダウンロード、コンパイル等はダウンロードした人の責任でお願いします。
• 何か気づいた点等がありましたら、連絡を頂ければ幸いです。eizo49@hotmail.co.jp

開発環境

• OS::wondows7 32bits
• コンパイラ::MinGW-MSYS(以下 mingw)
• コンパイラ & デバッガ::Code::Blocks 13.12 (以下 codeblocks)
• グラフィクス::OpenGL+FreeGLUT 2.8.1 (以下 freeglut)
• その他(スマートポインタ、多倍長整数計算)::boost 1.58.0 (以下 boost)

ビルド

「開発環境」のライブラリ、ファイルが所定の場所にあることを前提。

1. mingw コマンド窓で、"g++ -I. -o delaunay main.cpp delaunay.cpp -lfreeglut -lopnegl32"と打ち込む。
2. codeblocksで添付ファイル(delaunay.cbp)を開き、"Build"。
3. デフォルトでは、100個のランダムな点(-1.0 < = x , y < = 1.0)からdelaunayを生成。もし点の数を変更したい場合は、 delaunay.cpp Delaunay::init()を変更する(100,000個まで確認)。

プログラムについて

プログラムは、前回( 2012/10/1)に作成したDelaunay分割の改訂版である。 基幹部分は前とほとんど変わらないので、それを引用する。

Delaunay分割については、簡単な解説を作成した。
全面的に参考にさせてもらったのが、下の参考[1]の著者のサイトにある TTL(Triangulation Template Library)である。
「TTL」とはハーフエッジデータ構造を基本に、異なった面を移動していく手段として「ダーツ(dart)」という概念を導入したものである。
ダーツはそれ以外いろいろな機能をもっているが、詳しくは[1]か上のサイトをみてほしい。そのサイトにTTLとその応用としてDelaunay分割プログラムソース(C++) がある。それに全面的に依拠して作ったのが今回のプログラムである。 僭越にも名前空間名もそのまま使わせてもらった(注::この改訂版では一部変更)。
Delaunay分割には色々のアルゴリズムがある。上のTTLは「逐次添加法」のひとつである「Edge-Swapping法」である(修正2017/1/11)。当然このプログラムもそれを採用した。
記号摂動(杉原[2])
プログラムの大きな問題の1つに「誤差」、「退化」(3点が一直線で三角形ができない。Delaunayの外接円テストで4点が同一円周上に載る等)がある。 これを回避する方法の1つに「整数帰着法」、「記号摂動」がある。これについてはここを参照。

---

*以下のGMPライブラリは改訂版では使わない(注参照)。

---

「整数帰着法」は「多倍長整数を」を使う。 これはGMP(The GNU Multiple Precisio Arithmetic Library)を使った (注::改訂版では boost::cpp_intを使うことにした)。
これについては、あまり自信がない。皆さんのご叱正をお待ちします。
遠慮なくご意見をお寄せ下さい(「著作権」の問題もあれば)。
ここ以下何行か削除(2017/1/11)。

改訂点

• 前の版では、ポイントの座標を浮動小数点数と整数、2種類のタイプで保持していた。
  これでは使用メモリが大きくなる.これを、ポイントデータはdouble型とし、必要に応じて(記号摂動) 整数に変換することにした(記号摂動をやるかどうかの判定条件を決定する必要がある)。
• Delaunay分割で使う数式は、次の3種類である。前の版はこれがごちゃごちゃだったので整理した(ttl_util.h)。 カッコ内はttl_util.h内の関数名である。
  1. 四角形の凹凸判定(crossProduct2d(...))
  2. ポイントが含まれる三角形の決定(oreint2dfast(...),orient2d_perturb(...))
  3. 三角形の「局所最適」判定(「外接円テスト」)(orient3dfast(...), orient3d_perturb(...))
• 以上のことに関しては簡単な解説-補足を参照してほしい。
• 点のポインタを保持するのに、スマートポインタを使用した(boost::shared_ptr)。 スマートポインタについてはMeyers[3]を参照。

その他(ファイル)

名前空間	ファイル(クラス等)
delaunay	delaunay.h(Delaunay etc)
	delaunay.cpp
	ttl/halfedge/HeDart.h(Dart)
	ttl/halfedge/NewTraits.h(NewTraits)
ttl	ttl.h(ttl 関数テンプレート)
ttl_constr	ttl_constr.h(ttl.hで#include,使わない)
ttl_util	ttl/ttl_util.h(ユーティリティ)
なし	assert_true.h(デバグ用マクロ)

他の作成プログラム(削除・追加2017/1/11)

• Delaunay Refinement(2017/01/11)

参考

1. Ø.Hjell and M.Dæhlen Triangulation and Applications. Springer-Verlag 2006
2. 杉原厚吉 FORTRAN 計算幾何 プログラミング. 岩波書店 1998
3. S.Meyers EffectiveC++ third edition Addison-Wesley 2011