制約付きドロネー三角形分割

計算幾何学において、制約付きドロネー三角形分割は、ドロネー三角形分割の一般化であり、特定の線分を三角形分割の辺として強制的に組み込む。^{[ 1 ] [ 2 ]}ドロネー三角形分割自体は、辺によってどのように接続されるべきかに関係なく、与えられた頂点集合の位置のみに基づいている。これは効率的に計算可能であり、地理情報システムやメッシュ生成に応用されている。

意味

制約付きドロネー三角形分割問題への入力は、平面直線グラフ、つまり平面上の点と交差しない線分の集合である。この入力の制約付きドロネー三角形分割は、その凸包の三角形分割であり、すべての入力線分を辺として含み、入力の頂点のみを使用する。この入力に追加されるすべての辺について、三角形分割にするために の端点を通る円が存在し、その円の内部にある頂点は、 の少なくとも1つの端点から入力の線分によって見えないようにする必要がある。これは、点の2次元ドロネー三角形分割の定義特性、つまり各辺がその2つの端点を通る円を持ち、その円には他の頂点が含まれていないという特性を一般化したものである。これらの特性を満たす三角形分割は常に存在する。^{[ 1 ]}${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle e}$

ジョナサン・シューチュクはこの定義を、3次元入力、点と交差しない線分のシステム、3次元空間の三角形の制約付きドロネー三角形分割に一般化しました。しかし、このタイプのすべての入力が、彼の一般化された定義に従って制約付きドロネー三角形分割を持つわけではありません。^{[ 2 ]}

アルゴリズム

平面直線グラフの制約付きドロネー三角形分割を時間内に計算するアルゴリズムはいくつか知られている。^{[ 1 ] [ 3 ]}単純な多角形の制約付きドロネー三角形分割は線形時間で構築できる。^{[ 4 ]}${\displaystyle O(n\log n)}$

アプリケーション

地形測量では、現場で測量した点から三角測量図を作成します。三角測量の辺が河川を横切る場合、得られる面は河川の流路を正確に反映しません。そのため、河川、道路の端、山の尾根などに沿って破線を引きます。破線は三角測量図を作成する際の制約として使用されます。

制約付き Delaunay 三角形分割は、メッシュ生成のDelaunay 細分化法でも使用でき、メッシュを細分化するときにドメイン境界に強制的に適合させる方法として使用できます。

参考文献

1. Chew, L. Paul (1989)、「制約付きデローネ三角形分割」、Algorithmica、4 (1): 97– 108、doi : 10.1007/BF01553881、MR  0983658、S2CID  189918468
2. Shewchuk, Jonathan Richard (2008)、「一般次元制約付きドロネー法と制約付き正則三角形分割。I. 組合せ特性」、離散幾何学と計算幾何学、39 ( 1–3 ): 580–637、doi : 10.1007/s00454-008-9060-3、MR 2383774 
3. 王, 曹安; シューベルト, レンハート K. (1987)、「線分集合のドロネー三角形分割を構築するための最適アルゴリズム」、ソウル, D. (編)、第3回計算幾何学シンポジウム論文集、ウォータールー、オンタリオ州、カナダ、1987年6月8日～10日、ACM、pp.  223～ 232、doi : 10.1145/41958.41982、ISBN 0-89791-231-4、S2CID  18490297
4. Chin, Francis; Wang, Cao An (1999)、「単純な多角形の制約付きドロネー三角形分割と制約付きボロノイ図の線形時間での検出」、SIAM Journal on Computing、28 (2): 471– 486、doi : 10.1137/S0097539795285916、hdl : 10722/47094、MR 1634357、S2CID 28966377  

外部リンク

• CDTオープンソース実装。
• 計算幾何学アルゴリズムライブラリCGALにおける2D 三角測量
• 計算幾何学アルゴリズムライブラリCGALにおける3D 制約三角形分割