平面上の外接円で示されたドロネー三角形分割 計算幾何学 では、平面上の点の集合のデローネ三角形分割 またはデローン三角形分割は、それらの 凸包 [ 1 ] を、外接円に 点を含まない三角形に分割します。つまり、各外接円は生成点を円周上に持ちますが、集合内の他のすべての点は外接円の外側にあります。これにより、どの三角形においても最小の角度の大きさが最大化され、細長い三角形 を避ける傾向があります。
この三角測量は、1934年にこの研究を行ったボリス・ドローネーにちなんで名付けられました 。[ 2 ]
点がすべて一直線上にある場合、三角形分割の概念は退化 し、ドロネー三角形分割は存在しません。同じ円上にある4つ以上の点（例えば、長方形の頂点）の場合、ドロネー三角形分割は一意ではありません。四角形を 2つの三角形に分割する2つの可能な三角形分割のそれぞれが、「ドロネー条件」、つまりすべての三角形の外接円の内部が空であるという条件を満たします。
外接球を考慮することで、ドロネー三角形分割の概念は3次元以上の次元に拡張されます。ユークリッド距離 以外の距離尺度 への一般化も可能ですが、これらの場合、ドロネー三角形分割が存在することや一意であることは保証されません。
ボロノイ図との関係 ドロネー三角形分割図。すべての外接円とその中心（赤色で表示）が示されている。
外接円の中心を結ぶと、
ボロノイ図 （赤色）が生成されます。
一般位置にある離散 点集合P 三角形分割は、 P ボロノイ図 の双対グラフ に対応します。デローネ三角形の外心は 、ボロノイ図の頂点です。2 次元の場合、ボロノイの頂点は、デローネ三角形の隣接関係から導き出せる辺で接続されます。デローネ三角形分割で 2 つの三角形が辺を共有する場合、それらの外心はボロノイ分割で辺で接続されます。
この関係が成り立たない、あるいは曖昧な特殊なケースとしては、次のようなものがある。
3つ以上の同一直線上の 点があり、外接円の半径 は無限大である。 完全な円周上に4つ以上の点があり、三角形分割が曖昧で、すべての外心は自明に同一である。この場合、ボロノイ図には次数が4以上の頂点が含まれ、その双対グラフには4辺以上の多角形の面が含まれる。これらの面の様々な三角形分割によって、可能なすべてのドロネー三角形分割が完成する。 有限集合P 三角形分割を Bowyer–Watson アルゴリズム で計算する場合、「スーパー」三角形と共通の頂点を持つ三角形の外心は無視する必要があります。無限遠に伸びる辺は外心から始まり、保持される三角形と無視される三角形の共通辺に垂直です。
d 次元ドロネー( d 次元)ユークリッド空間 内の点の集合P ドロネー三角形分割 とは、DT( P ) 内のどのd 単体の 周超球 内にもP 内 三角形分割 DT( P ) のことである。Pが一般の位置にある点の集合である場合、つまり、 P d 次元であり、P 内の d + 2 個の点の集合が、内部が P と 交差 ない Pに対して 一意 のドロネー三角形分割が存在することが知られている[2 ]
d 次元ユークリッド空間 における点の集合のデローネ三角形分割を求める問題は、 ( d + 1 ) 次元空間における点の集合の凸包を 求める問題に変換できます。これは、各点pに | p | 2 d 次元空間にマッピングし直すことで実現できます。凸包は一意であるため、凸包のすべての面が単体であると仮定すると、三角形分割も一意になります。非単体面は、元の点の d + 2 個 が同じd 次元超球面 上にある場合、つまり点が一般位置にない場合にのみ発生します。 [ 3 ]
物件 手順例 アニメーションの各フレームは、4つの点のドロネー三角形分割を示しています。途中で三角形分割の辺が反転し、ドロネー三角形分割は三角形の辺の長さではなく、最小角度を最大化することを示しています。 n を点の数、d を次元の数とする。
三角形分割におけるすべての単体の和集合は、点の凸包である。 ドロネー三角形分割には、 O （ n ⌈ d / 2 ⌉ ） {\displaystyle \textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}} 。 [ 4 ] 平面 ( d = 2b 個 の頂点がある場合、点の任意の三角形分割には、最大で2 n – 2 – b 個の三角形と 1 つの外面が含まれます (オイラー標数を 参照)。 点が一定の強度を持つ平面上でポアソン過程 に従って分布する場合、各頂点は平均して 6 つの周囲三角形を持ちます。より一般的には、同じ過程をd 次元で行った場合、平均近傍数はd のみに依存する定数となります。[ 5 ] 平面上では、ドロネー三角形分割は最小角度を最大化します。点の他のどの三角形分割と比較しても、ドロネー三角形分割の最小角度は、他のどの三角形分割の最小角度よりも少なくとも大きくなります。ただし、ドロネー三角形分割は必ずしも最大角度を最小化するとは限りません。[ 6 ] 任意のドロネー三角形を外接する円は、その内部に他の入力点を含まない。 入力点のうち2点を通る円の内部に他の入力点が含まれていない場合、その2点を結ぶ線分は、与えられた点のドロネー三角形分割の辺となる。 d 次元空間内の点の集合のデローネ三角形分割の各三角形は、点を ( d + 1 ) 次元放物面に投影した 凸包 のファセットに対応し、その逆もまた同様である。任意の点p に最も近い隣接点bは、 最近傍グラフ がデローネ三角形分割の部分グラフであるため、デローネ三角形分割の辺bp 上にあります。 デローネ三角形分割は幾何学的スパナー です。平面（d = 2[ 7 ]
ビジュアル・ドロネーの定義：反転 上記の性質から重要な特徴が浮かび上がります。共通の辺BD を持つ2つの三角形△ ABD 、△ BCD （図を参照）を見ると、角度の和α + γ ≤ 180° であれば、これらの三角形はドロネー条件を満たします。
これは、反転 技法を用いることができるため、重要な性質です。2つの三角形がドロネー条件を満たさない場合、共通辺BDを AC
この三角分割はドロネー条件（ α とγ の合計が180°より大きい）を満たしていません。
この2つの三角形は、ドロネー条件（外接円の内部に点が存在する）を満たしていません。
を反転させると、 4つの点に対して有効なドロネー三角形分割が得られる。
この操作は反転 と呼ばれ、3次元以上の次元に一般化できる。[ 8 ]
アルゴリズム 点Dが A、B、C の外接円内にあるかどうかを、堅牢かつ高速に検出する方法が必要です。デローネイ三角形分割を計算する多くのアルゴリズムは、点が三角形の外接円内にあるかどうかを検出する高速な操作と、三角形と辺を格納するための効率的なデータ構造に依存しています。2 次元では、点Dが A、B、C の外接円内にあるかどうかを検出する 1 つの方法は、行列式 を評価することです。[ 9 ]
| A x A y A x 2 + A y 2 1 B x B y B x 2 + B y 2 1 C x C y C x 2 + C y 2 1 D x D y D x 2 + D y 2 1 | = | A x − D x A y − D y （ A x − D x ） 2 + （ A y − D y ） 2 B x − D x B y − D y （ B x − D x ） 2 + （ B y − D y ） 2 C x − D x C y − D y （ C x − D x ） 2 + （ C y − D y ） 2 | > 0 {\displaystyle {\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{ x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix} A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}} A、B、Cを 反時計 回りに並べた場合、この行列式はDが 外接円の内側にある場合にのみ正となる。
フリップアルゴリズム 前述のように、三角形がデローネ三角形でない場合は、その辺の 1 つを反転できます。これにより、単純なアルゴリズムが導き出されます。点の任意の三角形分割を構築し、デローネ三角形でなくなるまで辺を反転します。残念ながら、これにはΩ( n 2 ) 回の辺の反転が必要になる場合があります。[ 10 ] このアルゴリズムは 3 次元以上の次元に一般化できますが、基となる反転グラフ の連結性に依存するため、これらの場合の収束は保証されません。このグラフは 2 次元の点の集合では連結ですが、高次元では非連結になる可能性があります。[ 8 ]
再三角形分割後にドロネー特性を維持するために使用される外接円テストとエッジ反転を示すために、増分アルゴリズム中に2つの点を挿入します。
増分 デローネイ三角形分割を効率的に計算する最も簡単な方法は、頂点を一度に 1 つずつ繰り返し追加し、影響を受けるグラフの部分を再三角形分割することです。頂点vが追加されると、 v を含む三角形を 3 つに分割し、フリップ アルゴリズムを適用します。単純に実行すると、O( n ) の 時間が必要になります。すべての三角形を検索してv を含む三角形を見つけ、次にすべての三角形をフリップして取り除く可能性があります。すると、全体の実行時間はO( n 2 ) になります。
頂点をランダムな順序で挿入すると、(やや複雑な証明により) 挿入ごとに平均してO(1) 個の三角形だけが反転することがわかりますが、場合によってはもっと多くの三角形が反転します。[ 11 ] 、ルート三角形から開始し、 v を含む三角形を指すポインタをたどり、まだ置き換えられていない三角形が見つかるまで続けます。平均すると、これもO(log n ) の 時間がかかります。したがって、すべての頂点に対して、これにはO( n log n ) の時間がかかります。[ 12 ]この手法は高次元にも拡張できますが (Edelsbrunner と Shah [ 13 ]
Bowyer –Watsonアルゴリズムは、 増分構築のための別の手法を提供する。これは、新たに挿入された頂点を含むドロネー三角形を計算する際に、辺の反転に代わる方法を提供する。
残念ながら、反転ベースのアルゴリズムは、特定の点（例えば、荷車の車輪の中心点）を追加すると、最大でO( n ) 回の連続反転が発生する可能性があるため、一般的に並列化が困難です。Blelloch ら[ 14 ] は 、実用的で多対数スパン で高度に並列化された、リップアンドテントに基づくインクリメンタルアルゴリズムの別のバージョンを提案しました。
分割統治 2 次元の三角形分割のための分割統治アルゴリズム はLee と Schachter によって開発され、Guibas とStolfi [ 9 ] [ 15 ] [ 16 ] O( n ) の時間で実行できるため、全体の実行時間はO( n log n ) になります。[ 17 ]
一様ランダム分布などの特定のタイプの点集合の場合、分割線を賢く選択することで、最悪の場合のパフォーマンスを維持しながら、期待時間をO( n log log n )に短縮できます。
d 次元での三角形分割を実行するための分割統治パラダイムは、 P. Cignoni、C. Montani、R. Scopigno による「DeWall: E d [ 18 ]
分割統治アルゴリズムは、逐次的に最も高速なDT生成手法であることが示されています。[ 19 ] [ 20 ]
スイープハル Sweephull [ 21 ]
アプリケーション 点集合のユークリッド最小全域木は、同じ点のドロネー三角形分割の部分集合であり、[ 22 ] これを
点群から 地形 やその他のオブジェクトをモデリングする場合、ドロネー三角形分割は、モデルのポリゴンとして使用できる適切な三角形のセットを提供します。特に、ドロネー三角形分割は、狭い三角形（面積に比べて外接円が大きいため）を回避します。三角形分割された不規則ネットワーク を参照してください。
デローネ三角形分割は、デローネ分割フィールド推定器（DTFE） によって点サンプリングの密度または強度を決定するために使用できます。
平面上のランダムな100点の集合に対するドロネー三角形分割。 ドロネー三角形分割は、角度が保証されていること、および高速な三角形分割アルゴリズムが開発されていることから、物理シミュレーションの有限要素法 や有限体積法 などの空間離散化ソルバーのメッシュ生成 によく使用されます。通常、メッシュ化される領域は粗い単体複体 として指定されます。メッシュが数値的に安定するためには、例えばルパートのアルゴリズム を使用してメッシュを細分化する必要があります。
有限要素法 や境界要素 法の普及に伴い、自動メッシュ生成アルゴリズムの改良への意欲が高まっている。しかし、これらのアルゴリズムはいずれも、歪んだ、あるいは使用不可能なグリッド要素を生成する可能性がある。幸いなことに、既存のメッシュの品質を向上させる手法がいくつか存在する。例えば、平滑化（メッシュ細分化とも呼ばれる）は、要素の歪みを最小限に抑えるためにノードの位置を調整する手法の一つである。また、ストレッチグリッド法を 用いることで、デローネ基準を満たす擬似正則メッシュを、ワンステップで容易かつ迅速に生成できる。
制約付きデローネ三角形分割は、自動運転における 経路計画 や地形測量に応用されている。 [ 23 ]
参考文献 ↑ 大まかに言えば、その点の周りにゴムバンドを張ったときに囲まれる領域。 1 2 ボリス、ドロネー （1934 年）。"Sur la sphere vide" [ 空の球体上で] 。Bulletin de l'Académie des Sciences de l'URSS、Classe des Sciences Mathématiques et Naturelles (フランス語)。6 : 793–800 .↑ 福田光明 。「多面体計算に関するよくある質問」。www.cs.mcgill.ca 。 2018 年 10 月29日 取得 。 ↑ Seidel, Raimund (1995). "多面体の上限定理：漸近バージョンの簡単な証明". Computational Geometry . 5 (2): 115–116 . doi : 10.1016/0925-7721(95)00013-Y . ↑ Meijering, JL (1953). "ランダム核生成を伴う結晶凝集体の界面面積、辺長、および頂点数" (PDF) . Philips Research Reports . 8 : 270– 290. 2017-03-08 に オリジナル (PDF) からアーカイブされました。 Dwyer, Rex A. (1991). "Higher-dimensional Voronoĭ diagrams in linear expected time". Discrete and Computational Geometry . 6 (4): 343– 367. doi : 10.1007/BF02574694 . MR 1098813 による引用 。 ↑ Edelsbrunner, Herbert ; Tan, Tiow Seng; Waupotitsch, Roman (1992). "An O ( n 2 log n ) time algorithm for the minmax angle triangulation" (PDF) . SIAM Journal on Scientific and Statistical Computing . 13 (4): 994– 1008. CiteSeerX 10.1.1.66.2895 . doi : 10.1137/0913058 . MR 1166172 . 2017-02-09 の オリジナル (PDF) からアーカイブ済み。2017-10-24 に 取得 。 ↑ Xia, Ge ( 2013). " Delaunay三角形分割のストレッチ係数は1.998未満です". SIAM Journal on Computing . 42 (4): 1620–1659 . arXiv : 1103.4361 . doi : 10.1137/110832458 . MR 3082502. S2CID 6646528 . 1 2 De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications . Algorithms and Computation in Mathematics. Vol. 25. Springer. 1 2 Guibas, Leonidas ; Stolfi, Jorge (1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi" . ACM Transactions on Graphics . 4 (2): 74– 123. doi : 10.1145/282918.282923 . S2CID 52852815 . ↑ Hurtado, F. ; Noy, M.; Urrutia, J. (1999). "Flipping Edges in Triangulations" . Discrete & Computational Geometry . 22 (3): 333– 346. doi : 10.1007/PL00009464 . ↑ Guibas, Leonidas J. ; Knuth, Donald E. ; Sharir, Micha (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica . 7 ( 1– 6): 381– 413. doi : 10.1007/BF01758770 . S2CID 3770886 . ↑ デ・バーグ、マーク; オトフリード・チョン ;マルク・ヴァン・クレベルド。 マーク・オーヴァーマーズ (2008)。 計算幾何学: アルゴリズムとアプリケーション (PDF) 。スプリンガー・フェルラーク。 ISBN 978-3-540-77973-5 2009年10月28日にオリジナル（PDF） からアーカイブされました。2010年2月23日 に取得 。↑ Edelsbrunner, Herbert ; Shah, Nimish (1996). "Incremental Topological Flipping Works for Regular Triangulations". Algorithmica . 15 (3): 223– 241. doi : 10.1007/BF01975867 . S2CID 12976796 . ↑ Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms Archived 2018-04-25 at the Wayback Machine ↑ Peterson, Samuel. "平面における制約付きデローネ三角形分割の計算" . www.geom.uiuc.edu . 2017年9月22日の オリジナルからアーカイブ済み 。 2018年 4月25日 取得。 ↑ Dwyer, Rex A. (1987年11月). 「デローネ三角形分割を構築するためのより高速な分割統治アルゴリズム」. Algorithmica . 2 ( 1–4 ): 137–151 . doi : 10.1007/BF01840356 . S2CID 10828441 . ↑ Leach, G. (1992年6月). 「最悪ケース最適デローネ三角形分割アルゴリズムの改善」. 第4回カナダ計算幾何学会議 . CiteSeerX 10.1.1.56.2323 . ↑ Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: E d における高速分割統治デローネ三角形分割アルゴリズム ". Computer-Aided Design . 30 (5): 333– 341. doi : 10.1016/S0010-4485(97)00082-1 . ↑ 逐次デローネ三角形分割アルゴリズムの比較「アーカイブコピー」 (PDF) 。 2012年3月8日に オリジナル (PDF)からアーカイブされました。 2010年8月18日 に取得 。 {{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク) ↑ 「三角測量アルゴリズムとデータ構造」 。www.cs.cmu.edu 。 2017 年10月10日のオリジナルから アーカイブ済み。 2018年 4月25日 取得 。 ↑ 「S-hull」 （PDF） 。s -hull.org 。 2013年10月27日のオリジナルから アーカイブ （PDF） 。 2018年 4月25日 取得 。 ↑ Franz Aurenhammer; Rolf Klein; Der-tsai Lee (2013年6月26日). Voronoi Diagrams And Delaunay Triangulations . World Scientific Publishing Company. pp. 197–. ISBN 978-981-4447-65-2 。↑ Sterling J Anderson; Sisir B. Karumanchi; Karl Iagnemma (2012年7月5日)。 「車両の安全な半自律運転のための制約ベースの計画と制御」 (PDF) 。2012 IEEE Intelligent Vehicles Symposium。IEEE。doi : 10.1109 /IVS.2012.6232153 。 2019年2月28日に オリジナル (PDF)からアーカイブ 。 2019年 2月27日 に取得。
外部リンク ヘンリー、イアン（2022年7月11日）。「デローネ三角形分割の可視化」。デローネ三角形分割のアルゴリズムを詳述したブログ記事。 CGAL（ 計算幾何学アルゴリズムライブラリ） におけるドロネー三角形分割：マリエット・イヴィネック 。「2D三角測量」。2010年4月取得。Pion, Sylvain; Teillaud, Monique . 3D Triangulations . 2010年4月取得。 ホルナス、サミュエル。デブラーズ、オリヴィエ。ジャミン、クレマン。dD 三角形分割。 Hert, Susan; Seel, Michael. dD 凸包とドロネー三角形分割。2010年4月取得。 「Poly2Tri: 増分制約付きデローネ三角形分割。オープンソースのC++実装。2019年4月取得。」 「分割統治法によるドロネー三角形分割の構築」。オープンソースのC99実装。2019年4月取得。 「CDT: C++による制約付きデローネ三角形分割」。オープンソースのC++実装。2022年8月取得。 
![{\displaystyle {\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{ x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix} A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b63c387d3c5b4685e33284bb7a941d897583aa4)