開発メモ

Triangle

Triangle に関するドキュメントの日本語訳,メモなど

コマンドラインスイッチ

triangle [-prq__a__uAcDjevngBPNEIOXzo_YS__iFlsCQVh] input_file
'_'にはオプションとして数値を指定することがある.
スイッチの数値の間にスペースを入れてはいけない.
-pスイッチが指定された場合,'input_file'は .nodeまたは.polyの拡張子を
持つファイルでなければならない.
-rスイッチが指定された場合,.nodeファイルと.eleファイルを入力しなけれ
ばならない.さらに,できれば.polyファイルと.areaファイルも入力する.
これらのファイルのフォーマットは以下で説明する.
-p

Planar Straight Line Graph(.polyファイル: 頂点,線分,ホール,領域の属
性,領域の制約) を読む.
入力に応じた制約付きDelaunay三角形分割を生成する.
-s, -q, -a, -uが指定されれば,confirming Delaunay三角形分割を生成する.
完全なDelaunay三角形分割が必要なら,-D オプションを使う.
-pが指定されない場合,triangleは.nodeファイルを読む.
-r

以前に生成されたメッシュを精錬する.
メッシュは.nodeファイルと.eleファイルから読まれる.
-pも指定された場合,.polyファイルが読まれ,メッシュ内の辺を制約するた
めに使用される.
(数値指定無しで)-aも指定された場合,.areaファイルが読まれ,メッシュ
状に領域の制約を課する
生成に関する詳細は以下で詳しく述べる.
-q

ドローネ精製による高品質なメッシュ生成.
すべての角度が20度から140度となるように頂点が追加される.
最小角を20度から変更するには,'q'の後にその値を指定する.
指定された角度は小数点を含むことができるが,指数表現は受け付けない.
最小角は最大角の範囲も示すことに注意.
最小角が28.6度以下であれば,triangleは終了することが数学的に保証される
(ただし,無限の計算精度を想定).
実験では,最小角が34度以上でもしばしば成功した.しかしながら,いくつか
のメッシュに対する不十分な少数の精度に関連する問題を避けるために,最小
角を小さくする必要があるかもしれない.
-a

三角形の最大面積を制限する.
'a'に続いて数値を与えると,その値の面積を越える三角形は生成されない.
数値の指定が無ければ,.areaファイル(-rが指定された場合)または.polyファ
イルが面積の最大値の制約を指定する.
.areaファイルは各三角形に対する個別の面積制約を含む.posterioriの誤差
推定に基づいた有限要素メッシュ精製において有益である.
.polyファイルには,オプションとして線分で拘束された各領域の面積の制約
を含めることができる.それによって,PSLGの最初の三角形分割で三角形の密
度を制御できる.
-aオプションを二回与えることによって,固定の面積制約と変化する面積制約
の両方を課することができる(一方は数値を与え,もう一方には数値を与えな
い).
面積値は小数点を含むことができる.
-u

三角形のサイズにユーザ定義の制約を課す.
2通りの使い方がある.
一つは,任意の制約をコード化するためにtriangle.c内の triunsuitable()関
数を編集して再コンパイルすること.
もう一つは, EXTERNAL_SET シンボルをセットして,他で定義された
triunsuitable()とリンクすること.
いずれの場合も,-uスイッチはすべての三角形に適用されるユーザ定義のテス
トを発生する.
-A

各三角形が属する線分境界領域を特定する,追加の浮動小数点属性を各三角形
へ割り当てる.
属性は.polyファイルによって領域へ割り当てられる.
領域が.polyファイルによって明示的にマークされていない場合,その領域内
の三角形には属性値0が割り当てられる.
-Aスイッチは,-pスイッチが有効,かつ,-rスイッチが無効,の場合にのみ効
果を持つ
-c

三角形分割の凸包上の線分を作成する.
頂点集合を三角形分割している場合,凸包のすべての辺を含む.polyファイル
が書き出される.
PSLGを三角形分割している場合,PSLGがどのような線分を持っているかに関わ
らず,PSLGの全凸包が三角形分割されるべきであることをこのスイッチは明示
する.
PSLGを三角形分割する際にこのスイッチを使わなければ,Triangleは入力PSLG
の線分で囲うことによって,三角形分割される領域を特定する.
注: もし注意しなければ,このスイッチは,PSLG線分と凸包線分の間に極め
て細い角度の挿入を引き起こす(そして,Trianguleの計算精度が足りなけれ
ばおそらく失敗する).
メッシュを精製しているなら,-cスイッチは異なる動作をする: メッシュの
境界辺を含む.polyファイルを書き出す(.polyファイルが読まれていない場合
に有益).
-D

Conforming Delaunay triangulation:
メッシュ内のすべての三角形がDelaunayの条件を満たすことを保証させたい
(あるいは,すべてのボロノイ頂点が三角形分割内に置く)場合にこのスイッ
チを使用する(いくつかの有限体積法がこれを要求する).
このスイッチはRuppertのオリジナルアルゴリズムを呼び出し,直径の円が侵
食されるすべての線分を分割する.
通常,頂点と三角形の数は増加する.
-j

最終的な三角形分割に属さない頂点を出力.nodeファイルから捨てる.
デフォルトでは,Triangleは入力.nodeファイルのすべての頂点を出力.nodeファ
イルへ出力する(それらのインデックスが変わらないように同じ順番で).
-jスイッチは,出力.nodeファイルにおいて入力頂点の重複,または,頂点が
ホールに'食われる'のを防止する.
このように,二つの入力頂点が完全に同じ座標値を持つなら,最初の方だけが
出力に現れる.
捨てられる頂点が存在する場合,出力.nodeファイルの頂点番号は入力.nodeファ
イルとは異なる.
-e

三角形分割の辺のリストを.edgeファイルへ出力する.
-v

三角形分割と対応するボロノイ図を出力する.
縮退の検出は想定しておらず,いくつかのボロノイ頂点は重複することがある.
以下のボロノイ図の議論を参照.
-n

各三角形の隣接三角形のリストを.neighファイルへ出力する.
-g

メッシュをGeomview用のオブジェクトファイル(.off)へ出力する.
-B

出力.nodeファイル,.polyファイル,.edgeファイルにboundary markerを出力し
ない.以下の境界マーカーに関する議論を参照.
 -P

.polyファイルを出力しない.
ディスクスペースを節約できるが,以降のメッシュ精製で制約辺を管理できな
くなる
-N

.nodeファイルを出力しない.(すなわち,点のリストを生成しない)
-E

.eleファイルを出力しない.(すなわち,三角形のリストを生成しない)
-I

繰り返し回数無し.

.nodeファイルと.polyファイルの出力を抑制し,入力ファイルを上書きしない.
(入力ファイルが.polyファイルだけなら,.nodeファイルは出力される)
-rスイッチと同時には使えない(-rは入力.eleファイルを上書きするので).
.nodeファイルが出力されず,追加されたSteiner点が全く記録されないので,
もし入力に.nodeファイルを使用するなら,-q, -q, -u, -sスイッチと同時に
このスイッチを使用すべきではない.
-O

No holes.
.polyファイルのホールを無視する.
-X

厳密な算術演算を行わない.
通常,Triangleはあるテストに対して,不正確なテストが十分なに精密でない
と考えられるなら,厳密な浮動小数演算を行う.
浮動小数の丸め誤差にも関わらず,厳密な算術演算は三角形分割アルゴリズム
の頑健性を保証する.
-Xスイッチによって厳密な算術演算を無効にすると,スピードは少し改善され
るが,有効なメッシュを生成するのに失敗する可能性がある.
非推奨.
-z

すべてのアイテムの開始番号を0にする.
このスイッチは入力の.nodeファイルや.polyファイルの最初の頂点の番号を書
き変えてしまうが,Triangleを他のプログラムから使用する場合には有益であ
る.
-o2

Generates second-order subparametric elements with six nodes each.
-Y

境界上に新しい頂点を作らない.
このスイッチは,ある隣接メッシュを確証するような,メッシュの境界が予約
されなければならない場合に有益である.
メッシュの品質をかなり犠牲にしなければならないだろうという点に警戒する
こと.
Triangleは品質を保とうとするが,得られるメッシュは貧弱な形状の三角形を
含むかもしれない.
すべての境界頂点が十分に近ければ,上手く働くだろう
内部の境界を含むすべての線分の分割を防止するには,このスイッチを二回指
定すること('-YY')
-S

Steiner点(入力に無い頂点,最小角と最大面積の制約を合わせるために追加
される)の最大数を指定する.
デフォルトでは制限無し.
このスイッチを値指定無しで使用すると,制限数は0になる.
制限された数よりも多くの頂点が必要になったとしても,Triangleは常に線分
の交差点に頂点を追加する.
Triangleが分割(-s)によって線分を挿入するとき,PLSGのすべての線分が回復
することを保証するために,必要なら制限を無視して,十分な頂点が常に追加
される.
-i

Delaunay三角形分割を構築するのに,分割統治アルゴリズムではなく逐次法を
使用する.
分割統治アルゴリズムが失敗する場合に試すこと.
-F

Delaunay三角形分割の構築にFortuneのsweeplineアルゴリズムを使用する.
注意: すべての計算において厳密な算術演算を使用してはいけない.正確な
結果は保証されない.
-l

分割統治アルゴリズムで垂直カットのみを使用する.
デフォルトでは,Triangleは垂直カットと水平カットを交互に使用する.
通常,交互に使用することでスピードが改善される(頂点集合が小さいか短い
そして広い場合を除いて)
このスイッチは主として理論的な興味である.
-s

制約付きDelaunay三角形分割を作るのではなく,線分を再帰的にその中点で分
割することで無理やり三角形分割することを指定する.
線分分割はRuppertのオリジナルアルゴリズムに忠実であるが,不必要に小さ
い三角形を作成してしまう.
このスイッチは主として研究的な興味のために使用される.
-C

最終的なメッシュの一貫性をチェックする.
-Xスイッチが使われていたとしても,チェックには厳密な算術演算を使用する.
Triangleのバグが疑わしい場合に有益である.
-Q

エラーが発生しない限り,Triangleの実行内容の出力をすべて抑制する.
-V

Verbose:
実行内容を詳細に出力する.
'V'を追加すると表示レベルがさらに上がる.
-Vによって,アルゴリズムの進行状況とより詳細な統計情報を得られる.
`-VV'によって頂点ごとの詳細が得られが,実行速度はかなり遅くなる.
`-VVVV'はデバッガのみに有用な情報.
-h

ヘルプメッセージを表示する.

定義

Delaunay Triangulation

Voronoi Diagram

PSLG (Planar Straight Line Graph)

頂点と線分の集合. 線分は辺で,端点はPSLG内のいずれかの頂点. 線分同士が交差する場合は,それぞれの端点でのみ交差する. PSLGは .poly ファイルに記録される.

CDT (Constrained Delaunay Triangulation)

conforming Delaunay Triangulation

各三角形はドローネの条件を満たす. PSLGの各線分は,三角形分割の辺の線形隣接列で表現される. 新しい頂点が現れると,各入力線分はより短い線分へ分割されることがある.

ファイルフォーマット

'#'はで始まる行はコメント

.node ファイル

1行目:
<頂点の数> <次元数(2で固定)> <属性の数> <boundary markerの数(0 or 1)>

残りの行:
<頂点番号> <x> <y> [attributes] [boundary marker]

属性(有限要素メッシュに関連付けられる,一般的には質量や伝導率などの物理量の浮動少数値)は変更無しで出力メッシュへコピーされる.-q, -a, -u, -D, -sが有効の場合,メッシュへ追加される各Steiner点へは線形補間によって属性値が割り当てられる.

1行目の4項目が'1'であれば,残りの行の最後の列はboundary markerを含むことが想定される.boundary markerは境界頂点とPSLG線分に留まる頂点を特定するために使用される.完全な説明は以下で行う.-Bスイッチで抑制されない限り,Triangleが作成する.nodeファイルには最後の列にboundary markerが含まれる.

.ele ファイル

1行目:
<三角形の数> <三角形あたりのノード数> <属性の数>

残りの行:
<三角形番号> <node> <node> <node> ... [attributes]

ノードは.nodeファイル内の対応するインデックス.最初の3つのノードは三角形の頂点で,反時計まわりにリストされる.(残りのノードがある場合,順番は使用される有限要素のタイプに依存する)

属性は.nodeファイルと同様.入力から出力三角形へは単純にマッピングできないので,Triangleは属性の補間を試みる.ただし,三角形分割の生成に伴って,近隣の三角形の間での属性の拡散が起こる.属性は線分をまたがった拡散はしない.よって,線分境界領域を特定するために使われる属性はそのまま残る.Triangleが生成する.eleファイルでは,-o2スイッチが使われない限り,各三角要素は3つのノード(頂点)を持つ.最初の3つのノードは三角形の頂点で反時計まわり順,4,5,6番目のノードは,それぞれ1,2,3番目の頂点の反対側の辺の中点に位置する.

.poly ファイル

1行目:    <頂点の数> <次元数(2で固定)> <属性の数> <boundary markerの数(0 or 1)>
以降の行: <頂点番号> <x> <y> [attributes] [boundary marker]

1行:      <線分の数> <boundary markerの数(0 or 1)>
以降の行: <線分番号> <端点> <端点> [boundary marker]

1行:      <holeの数>
以降の行: <hole番号> <x> <y>

オプション行: <領域属性,面積制約の数>
以降のオプション行: <領域番号> <x> <y> <attribute> <max area>

いくつかの追加情報と同様に,.polyファイルはPSLGを表現する.最初のセクションは.nodeファイルと全く同一のフォーマットで,すべての頂点をリストする.頂点が別の.nodeファイルにリストされることを示すために,<頂点の数>は0に設定されるかもしれない.この方法で示された頂点集合を使うと,三角形分割で線分を使うか否かを簡単 に切り替えられるという利点がある(-pスイッチが有効かどうかに依存)

第2セクションは線分をリストする.線分は三角形分割内で存在が強制される辺である. (スイッチの選択に応じて,線分はより小さい辺に分割されることがある)各線分は2つの端点のインデックスをリストすることで指定される.すなわち,端点は頂点リストに含まれなければならない.各点と同様に,各線分はboundary markerを持つことができる.

q, a, u, sが無効の場合,Triangleは制約付きDelaunay三角形分割を生成する(各線分は三角形分割内の単独辺として現れる).-q, -a, -u, -sが有効の場合,Triangleはconforming制約付きDelaunay三角形分割(線分はより小さい辺へ再分割されることがある)を生成する.

第3セクションは三角形分割内の穴を(-cが有効の場合は凹みも)リストする.穴は各穴の内部の点を特定することで指定される.三角形分割が形成された後,Triangleは三角形を飲み込み,各穴の点からその進行がPSLGの線分でブロックされるまで広げることで穴を生成する.各穴を線分で取り囲むことに,あるいは全三角形分割が飲み込まれるかもしれ ないことに注意しなればならない.もし線分で隣接する2つの三角形が飲み込まれれば,線分そのものも飲み込まれる.穴を線分上に置いてはいけない.さもなければ,Triangleは一方の線分を任意に選択する.

オプションの第4セクションは領域の(領域内の全三角形に関連付けられる)属性と,三角形面積の最大値制約をリストする.-A スイッチが有効,または,数値指定無しの-aスイッチが有効で-rスイッチが無効の場合にのみ,Triangleはこのセクションを読む.領域属性と面積制約は穴と同じ方法で伝播する:各属性または制約の点を指定し,属性または制約は点を含む(線分で拘束される)全領域に影響する.xy座標値の後に2つの値が書かれれば,一つ目は領域属性と想定され(ただし,-Aスイッチが有効の場合のみ),二つ目は面積制約と想定される(ただし,-aスイッチが有効の場合のみ).座標値の後に値を一つだけ指定するかもしれない.スイッチの選択によって,値は属性と面積制約のいずれも提供できる.もし-Aと-aの両方を有効にして,属性は割り当てるが面積制約を使わない場合は,最大面積値として負の値を使用すること.

三角形分割が.polyファイルから生成されるとき,三角形分割される全領域をPSLG線分で囲うか,-cスイッチ(PSLGの凸包を囲う追加の線分を自動的に作る)を使わなければならない.-cスイッチを使わなければ,Triangleは線分で囲われていないすべての三角形 を飲み込む.注意しなければ,全三角形分割が飲み込まれるかもしれない.-cスイッチを使えば,凸包領域内部に穴を適切に配置することで凹みを生成できる.

理想的なPSLGは交差した線分を持たない,あるいは,線分上に頂点が存在しない(もちろん,端点は除く)..polyファイルが理想的であることは要求されないが,何が誤りとなりうるかを知ってくべきである.計算精度が問題にならない限り,線分の交差は比較的安全である -- Triangleは交差点を計算し,三角形分割に追加する.同じ位置で交差する3つの線分が存在するなら,失敗を期待し,Triangleが交差点の位置を計算することを予期する.不動少数の丸め誤差に感謝する.Triangleはおそらく三つの線分が異なる3点で交差すると決定し,出力に非常に小さい三角形を見つけるだろう(Triangleが極小の三角形を生成しようとして,計算精度の最後のビットを用いて完全に失敗しない限り).入力ファイル中に交差点を置き,各線分を人手で分割するのはより良い.同様に,あなたが線分の中央に頂点を置き,Tirangleがその頂点で線分を分割することを望むなら,あなたは幸運を得るだろう.一方で,Triangleは頂点が線分上の厳密には乗っていないと判断するかもしれず,極めて尖った三角形を得るか,あるいは,高品質メッシュを生成しているなら多数の小さい三角形を得るだろう.

Triangleが.polyファイルを読むとき,サブ線分(入力線分の一部である辺)を含む.polyファイルも書き出す.-cスイッチが有効ならば,出力.polyファイルは凸包上のすべての辺も含む.それゆえ,出力.polyファイルは入力線分に関連付けられた辺を発見するのに有益であり,有限要素シミュレーションにおいて境界条件を設定することにも有益である. さらに,出力メッシュを精製するもりで,後の三角形分割で線分を失いたくないならば,出力.polyファイルが必要である.

.area ファイル

First line:  <# of triangles>
Following lines:  <triangle #> <maximum area>

.areaファイルはメッシュ精製に使われる最大面積を各三角形に関連付ける.他のファイルフォーマットと同様に,すべての三角形が連番で列挙されなければならない.負の面積を割り当てることで制約無しの三角形のままにすることもできる.

.edge ファイル

First line:  <# of edges> <# of boundary markers (0 or 1)>
Following lines:  <edge #> <endpoint> <endpoint> [boundary marker]

端点は対応する.nodeファイル内のインデックス. Triangleは(-uスイッチを使えば).edgeファイルを作成できるが,それを読むことはできない.boundary markerのオプション列は-Bスイッチによって抑制される.

ボロノイ図では,端点が一つの無限半直線となる特別な種類の辺も発見する.これらの辺に対しては,以下の異なるフォーマットが用いられる.

<edge #> <endpoint> -1 <direction x> <direction y>

'direction'は半直線の方向を示す不動小数ベクトルである.

.neigh ファイル

First line:  <# of triangles> <# of neighbors per triangle (always 3)>
Following lines:  <triangle #> <neighbor> <neighbor> <neighbor>

neighborsは対応する.eleファイル内のインデックス.インデックスが-1であれば,それは隣接が存在しないことを意味する(三角形が外側の境界上にあるので).三角形iの最初の隣接は,三角形iの最初の角の反対側である,など.

(-nスイッチを使用すると)Triangleは.neighファイルを作成するが,それを 読むことはできない.

struct trignulateio

struct triangulateio {
   /*
     'z'スイッチが使われなければ,最初のアイテム番号は'1'になる.
   */

   /*!
     In / out
     点座標値の配列.
     配列長はnumberofpoints
     最初の点のx座標は[0],y座標は[1].以降REAL*2ずつ続く.
   */
   REAL *pointlist;

   /*!
     In / out
     点の属性値の配列.
     1点あたり numberofpointattribute * REAL の領域を占有
     配列長は numberofpointattribute * numberofpoints
   */
   REAL *pointattributelist;

   /*!
     In / out
     点マーカーの配列.
     一点あたりint
   */
   int *pointmarkerlist;

   /*!
     In / out
     点の数
   */
   int numberofpoints;

   /*!
     In / out
     1点あたりの属性の数
   */
   int numberofpointattributes;

   /* ---------- */

   /*!
     In / out
     三角形の頂点の配列.
     最初の頂点は[0]で始まり,残りの二頂点は反時計回りで格納される.
     三角形が非線形要素を表現するなら,他のノードが続く.
     各三角形は'numberofcorners'個のintを占有する.
   */
   int *trianglelist;

   /*!
     In / out
     三角形の属性の配列.
     各三角形の属性は'numberoftriangleattributes個のREALを占有する.'
   */
   REAL *triangleattributelist;

   /*!
     In only
     三角形の面積制約の配列.
     三角形一つあたりに1個のREAL.
     入力のみ.
   */
   REAL *trianglearealist;

   /*!
     Out only
     三角形の隣接の配列.
     三角形一つあたりに3個のint
     出力のみ
   */
   int *neighborlist;

   /*!
     In / out
   */
   int numberoftriangles;

   /*!
     In / out
   */
   int numberofcorners;

   /*!
     In / out
   */
   int numberoftriangleattributes;

   /* ---------- */

   /*!
     In / out
     線分の端点の配列.
     最初の線分の端点は[0]と[1]のインデックス.
     各線分は2つのintを占有する.
   */
   int *segmentlist;

   /*!
     In / out
     線分マーカーの配列.
     各線分は1つのintを占有する.
   */
   int *segmentmarkerlist;

   /*!
     In / out
   */
   int numberofsegments;

   /* ---------- */

   /*!
     In / pointer to array copied out
     穴の配列.
     最初の穴のxy座標値は[0]と[1].
     各穴は2つのREALを占有する.
     入力のみだが,ポインタは出力構造体へコピーされる.
   */
   REAL *holelist;

   /*!
     In / copied out
   */
   int numberofholes;

   /* ---------- */

   /*!
     In / pointer to array copied out
     領域の属性と面積制約の配列.
     最初の制約のxy座標値は[0]と[1]に格納,属性値は[2]に格納.最大面積は
     [3]に格納される.
     各領域は4個のREALを占有する.
   */
   REAL *regionlist;

   /*!
     In / copied out
   */
   int numberofregions;

   /* ---------- */

   /*!
     Out only
   */
   int *edgelist;

   /*!
     Not used with Voronoi diagram; out only
   */
   int *edgemarkerlist;

   /*!
     Used only with Voronoi diagram; out only
   */
   REAL *normlist;

   /*!
     Out only
   */
   int numberofedges;
};

Tips

  • CDT_ONLYシンボルを有効にしておくと,メッシュ生成のコードがコンパイルされない.
  • zスイッチはポイントのインデックスを0から開始する.
  • Qスイッチ: quietモード
  • 境界マーカーが必要ないのであれば,-Nスイッチ(nodeの出力無し)を使うとメモリを節約できる.(境界マーカーが必要だがメモリを節約したい場合,triangulateを呼ぶ前に out->pointlistをin-pointlistへセットするトリックが使える)
  • vスイッチ(ボロノイ図出力)が無効の場合,triangulateの第3引数はNULLで良い.'in'と'out'をNULLにしてはいけない.'in'と'out'の特定のフィールドは(オプションの状態に応じて適切に)初期化されていなければならない.

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-03-14 (月) 14:51:37 (1313d)
SourceForge.JP
Creative Commons License
RoboCup tools by Hidehisa Akiyama is licensed under a Creative Commons 表示-非営利 2.1 日本 License.