多角形の三角形分割

多角形の三角形分割（たかっけいのさんかっけいぶんかつ）は計算幾何学の分野で用いられる、（単連結な）多角形の領域Pの三角形の集合への分割である^[1]。つまり、和集合がPである互いに重なり合わない三角形の集合の発見法である。

三角形分割は平面直線グラフの特殊な場合としてみなせる。穴のない図形の頂点のみを用いた三角形分割は、外平面的グラフである。

追加点を用いない多角形の三角形分割

多角形の三角形分割アルゴリズムは多数提案されている。

特別な場合

ある頂点から伸びる全ての対角線により凸多角形は扇形分割され、これは三角形分割であるため、線形時間で三角形分割が可能である。

レオンハルト・オイラーによって、凸n角形の三角形分割の組合せの数は、交差しない対角線の数であり、(n − 2)番目のカタラン数、つまり^[2]。

アラン=フルニエとD.Y. Montunoによって、単調多角形は、線形時間で三角形分割可能であることが示された^[3]。Godfried Toussaintのアルゴリズムによっても線形時間で三角形分割可能である^[4]。

耳刈り取り法

単調多角形を三角形分割する手法はtwo ears theoremに基づくものである。この定理は、4本以上の辺を持つ穴のない単純多角形は少なくとも2つの「耳（2辺が多角形の辺であり、残り1辺が多角形の内部に存在する三角形）」を持つという定理である^[5]。このアルゴリズムはこの「耳」を見つけ、その三角形を多角形から順に取り除くことで三角形分割を行う。

このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量はO(n²)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、Godfried Toussaintにより発見された^[6]。

単調多角形による三角形分割

単純多角形の場合は以下のように単調多角形に分割できる。

各点について、隣り合う点が掃引線の同じ側にあるか、つまり「水平線や鉛直線を引いた場合に同じ側にあるかどうか」を確認する。もし同じ側にあれば掃引線を延長し、多角形と交差した点の辺の端点の内「違う側」の点間の線分で分割する。この処理を繰り返す。

（水平な）掃引線を下へと動かす場合に、両方の頂点が掃引線の上側にあり、下の図形が分割される場合がある。この場合、これから探索する図形が分割され、三角形分割のためにはそれぞれの図形に対して上記の処理を繰り返す必要がある。

このアルゴリズムを用いることで、単純多角形の三角形分割は $O(n\log n)$ 時間で実行可能である。

三角形分割の双対グラフ

多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割T_Pが与えられたとき、T_Pの三角形を頂点として持ち隣接を辺として表すグラフG(T_P)が定義できる。G(T_P)は木であり、その最大次数は3である。

計算量

長きに渡って、単純多角形を $O(n\log n)$ 時間より高速に三角形分割するアルゴリズムが未発見であった。その後、Tarjan & Van Wyk (1988)は $O(n\log \log n)$ 時間で三角化を行うアルゴリズムを発見し^[7]、後にKirkpatrick Klaweとロバート・タージャンにより簡単化された^[8]。複数の改善により、 $O(n\log ^{\ast }n)$ （実用上ほぼ線形時間）を実現している^[9]^[10]^[11]。

1991年にバーナード・チャゼルは非常な複雑なアルゴリズムではあるが、任意の単純多角形を線形時間で三角形分割するアルゴリズムを示した^[12]。また、乱択アルゴリズムを用いることで、平均計算時間が線形時間であるアルゴリズムも存在する^[13]。

ザイデルの分割アルゴリズムとチャゼルの三角形分割については、 Li & Klette (2011) が詳しい^[14]。

穴を持つn頂点の多角形の三角形分割の時間計算量の下界は $\Omega (n\log n)$ 与えられている。

出典

^ Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0
^ Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
^ Fournier, A.; Montuno, D. Y. (1984), “Triangulating simple polygons and equivalent problems”, ACM Transactions on Graphics 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301
^ Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," Pattern Recognition Letters, 2 (March):155–158.
^ Meisters, G. H., "Polygons have ears."
^ ElGindy, H. (1993). “Slicing an ear using prune-and-search”. Pattern Recognition Letters 14 (9): 719–722. doi:10.1016/0167-8655(93)90141-y.
^ Tarjan, Robert E.; Van Wyk, Christopher J. (1988), “An O(n log log n)-time algorithm for triangulating a simple polygon”, SIAM Journal on Computing 17 (1): 143–178, doi:10.1137/0217010, MR925194 .
^ Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), “Polygon triangulation in O(n log log n) time with simple data structures”, Discrete and Computational Geometry 7 (4): 329–346, doi:10.1007/BF02187846, MR1148949 .
^ Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), “A fast Las Vegas algorithm for triangulating a simple polygon”, Discrete and Computational Geometry 4: 423–432, doi:10.1007/BF02187741 .
^ Seidel, Raimund (1991), “A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons”, Computational Geometry: Theory and Applications 1: 51–64, doi:10.1016/0925-7721(91)90012-4
^ Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), “Randomized parallel algorithms for trapezoidal diagrams”, International Journal of Computational Geometry & Applications 2 (2): 117–133, doi:10.1142/S0218195992000081, MR1168952 .
^ Chazelle, Bernard (1991), “Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry 6: 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
^ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), “A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376
^ Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5 .

外部リンク

Demo as Flash swf, A Sweep Line algorithm.
Song Ho's explanation of the OpenGL GLU tesselator

[bkos-1] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0

[2] Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.

[3] Fournier, A.; Montuno, D. Y. (1984), “Triangulating simple polygons and equivalent problems”, ACM Transactions on Graphics 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301

[4] Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," Pattern Recognition Letters, 2 (March):155–158.

[5] Meisters, G. H., "Polygons have ears."

[6] ElGindy, H. (1993). “Slicing an ear using prune-and-search”. Pattern Recognition Letters 14 (9): 719–722. doi:10.1016/0167-8655(93)90141-y.

[7] Tarjan, Robert E.; Van Wyk, Christopher J. (1988), “An O(n log log n)-time algorithm for triangulating a simple polygon”, SIAM Journal on Computing 17 (1): 143–178, doi:10.1137/0217010, MR925194 .

[8] Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), “Polygon triangulation in O(n log log n) time with simple data structures”, Discrete and Computational Geometry 7 (4): 329–346, doi:10.1007/BF02187846, MR1148949 .

[9] Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), “A fast Las Vegas algorithm for triangulating a simple polygon”, Discrete and Computational Geometry 4: 423–432, doi:10.1007/BF02187741 .

[10] Seidel, Raimund (1991), “A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons”, Computational Geometry: Theory and Applications 1: 51–64, doi:10.1016/0925-7721(91)90012-4

[11] Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), “Randomized parallel algorithms for trapezoidal diagrams”, International Journal of Computational Geometry & Applications 2 (2): 117–133, doi:10.1142/S0218195992000081, MR1168952 .

[12] Chazelle, Bernard (1991), “Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry 6: 485–524, doi:10.1007/BF02574703, ISSN 0179-5376

[13] Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), “A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time”, Discrete & Computational Geometry 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376

[14] Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]