C++ Delaunay Refinement

Eizo W. 2017/1/11

初期ドロネー	refine

ソース

• ソース
• 開発環境・ビルドはDelaunay 三角形分割参照。
• codeblocksのプロジェクトファイル名はDelaunay_refine.cbp
• 何か気づいた点等がありましたら、連絡を頂ければ幸いです。eizo49@hotmail.co.jp

プログラムについて

• Ø.Hjell and M.Dæhle[1]"7 Delaunay Refinement Mesh Generation"にあるRuppertアルゴリズム([3])の実装である。
• アルゴリズムについては、自分の理解できた範囲で、ここにまとめた。 詳細は[1],[2]を参考していただきたい。
• "Refinement"とは、すべてのドロネー三角形の内角を一定角度(Rアルゴリズムは約20度)以上にすることである。
• そのためには、外接円の半径と三角形の最小辺の長さの比を√2より小さくすればよい(正弦定理）。
• この比の上限を1とする(最小角は約30度)Chewアルゴリズムもあるようだが、自分は見ていない。
• このプログラムでも、比を1より小さくすればそれなりのものが表示されるが、これがChewのアルゴリズムなのかわからない。
• 上の図は100個の点でドロネーを作り(左図)、それをrefineしたものである(右図)。
• この点の数は、"main.cpp"の中で変更できる(200,000個まで確認)。
• 点はランダムに発生するが、初期状態ではseedを固定しているので適宜変更を("delauny.cpp", Delaunay::init())。
• 元々R.アルゴリズムはconstrainedドロネーを対象にしているが、このプログラムは単純なドロネーのrefineである。
• 今回もTTL(Triangulation Template Library) を多く利用させてもらった。
  プログラム全体の構成も、ドロネープログラム同様このライブラリの方法を手本に組み立てた。
  本当に[1]の著者には心より感謝したいと思います。

関数について

• 中心となる関数は"refine.h"にあるsplitSegment(...)とremoveSkinny(...)の2つである。
  splitSegmentは境界エッジを直径とする円が他の点を含まなくなるまで再帰的に2等分する。
  2等分するかどうか判定するのが"NewTraits.h"内のencroachTest(...)である。
  removeSkinnyは最小角が基準に満たない(skinny)三角形の外心に点を挿入し、skinnyを消去する。
• 上の2つの関数は"delaunay.cpp"内のDelaunay::refine(...)から呼ばれる。
  ここで三角形がskinnyかどうかの判定を行う。判定する関数は"delaunya.cpp"にあるstatic skinny(...)である。
  skinny(...)関数は外接円の中心座標・半径を計算するが、その公式は杉原[4]p233の式を利用させてもらった 。

ドロネー作成プログラムの修正について

• ドロネー作成の最終段階で境界を凸にし、境界と外枠の間にある三角形を消去する(図1)。
  黄色線のように凹んだところの両端を結んで境界を作る。
• 問題は緑線のように3点が一直線上にある場合にもこれを三角形として保持する(3辺からなる「退化」三角形)。
  理論上これではrefineできない(はず)。

• そこで次のように修正した(図2)。
  1. pp'の長さがある一定の数より小さいときpの座標をp'の座標に変更し、△ApBを消去。
     (ハーフエッジデータ構造なので片方のAp,pBエッジは境界エッジとして残る)
  2. もしp'がAかBに近いときはp'を消去。
  3. ハーフエッジデータ構造上そんな簡単に消去はできないが、TTLライブラリにはそのような関数が用意されている。!!
• 具体的には"ttl.h"内のttl::removeBoundaryNode(...)を修正。その関数のソースに修正内容を記してあるので参照を。
• 実際プログラムを動かしてみると上のような事態は起きていない。これについても関数のソースを参照してほしい。

参考

1. Ø.Hjell and M.Dæhlen Triangulation and Applications. Springer-Verlag 2006
2. Ø.Hjell A Triangulation Template Library(TTL) : Generic Design of Triangulation Software 2000
3. J. Ruppert A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation JOURNAL OF ALGORITM 1994
4. 杉原厚吉 FORTRAN 計算幾何 プログラミング. 岩波書店 1998