多角形の三角形分割のソースを表示

'''多角形の三角形分割'''（たかっけいのさんかっけいぶんかつ）は[[計算幾何学]]の分野で用いられる、（[[単連結]]な）[[多角形]]の[[領域 (解析学)|領域]]'''P'''の三角形の集合への分割である<ref name="bkos">{{Citation|title=Computational Geometry|year=2000|author=[[Mark de Berg]], [[Marc van Kreveld]], [[Mark Overmars]], and [[Otfried Schwarzkopf]]|edition=2nd revised|publisher=[[Springer-Verlag]]|isbn=3-540-65620-0|ISBN=3-540-65620-0}}</ref>。つまり、和集合が'''P'''である互いに重なり合わない三角形の集合の発見法である。

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

== 追加点を用いない多角形の三角形分割 ==
多角形の三角形分割アルゴリズムは多数提案されている。

=== 特別な場合 ===
[[ファイル:Polygon_Triangulations_(heptagon).svg|サムネイル|凸[[七角形]]の42通りの三角形分割。この数字は5番目の[[カタラン数]]である。]]
ある[[頂点]]から伸びる全ての[[対角線]]により[[凸多角形]]は[[扇形分割]]され、これは三角形分割であるため、[[線形時間]]で三角形分割が可能である。

[[レオンハルト・オイラー]]によって、凸n角形の三角形分割の組合せの数は、交差しない対角線の数であり、(''n''&#x20;&#x2212;&#x20;2)番目の[[カタラン数]]、つまり<ref>[[:en:Clifford_Pickover|Pickover, Clifford A.]], ''The Math Book'', Sterling, 2009: p. 184.</ref>。

[[アラン・フルニエ|アラン=フルニエ]]とD.Y. Montunoによって、[[単調多角形]]は、線形時間で三角形分割可能であることが示された<ref>{{Citation|title=Triangulating simple polygons and equivalent problems|year=1984 <!--<nowiki>|</nowiki>month=April-->|last1=Fournier|last2=Montuno|first1=A.|first2=D. Y.|author1-link=Alain Fournier|journal=[[ACM Transactions on Graphics]]|volume=3|issue=2|pages=153–174|doi=10.1145/357337.357341|DOI=10.1145/357337.357341|issn=0730-0301|ISSN=0730-0301}}</ref>。Godfried Toussaintのアルゴリズムによっても線形時間で三角形分割可能である<ref>Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons," ''Pattern Recognition Letters'', '''2''' (March):155–158.</ref>。

=== 耳刈り取り法 ===
[[ファイル:Polygon-ear.png|サムネイル|多角形の「耳」]]
単調多角形を三角形分割する手法はtwo ears theoremに基づくものである。この定理は、4本以上の辺を持つ穴のない単純多角形は少なくとも2つの「耳（2辺が多角形の辺であり、残り1辺が多角形の内部に存在する三角形）」を持つという定理である<ref>Meisters, G. H., "Polygons have ears." </ref>。このアルゴリズムはこの「耳」を見つけ、その三角形を多角形から順に取り除くことで三角形分割を行う。

このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量は''O''(''n''<sup>2</sup>)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、Godfried Toussaintにより発見された<ref>{{Cite journal|last=ElGindy|first=H.|year=1993|title=Slicing an ear using prune-and-search|journal=Pattern Recognition Letters|volume=14|issue=9|pages=719–722|doi=10.1016/0167-8655(93)90141-y}}</ref>。

=== 単調多角形による三角形分割 ===
[[ファイル:Polygon-to-monotone.png|サムネイル|多角形の、単調多角形分割]]
[[単純多角形]]の場合は以下のように単調多角形に分割できる。

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

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

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

=== 三角形分割の双対グラフ ===
多角形Pの三角形分割関連で有用なグラフに、三角形分割の双対グラフがある。Pの三角形分割T<sub>P</sub>が与えられたとき、T<sub>P</sub>の三角形を頂点として持ち隣接を辺として表す[[グラフ理論|グラフ]]G(T<sub>P</sub>)が定義できる。G(T<sub>P</sub>)は[[木構造 (データ構造)|木]]であり、その最大次数は3である。

=== 計算量 ===
長きに渡って、単純多角形を<math>O(n\log n)</math>時間より高速に三角形分割するアルゴリズムが未発見であった。その後、{{Harvtxt|Tarjan|Van Wyk|1988}}は<math>O(n\log\log n)</math>時間で三角化を行うアルゴリズムを発見し<ref>{{Citation|title=An O(''n'' log log ''n'')-time algorithm for triangulating a simple polygon|year=1988|last1=Tarjan|last2=Van Wyk|first1=Robert E.|first2=Christopher J.|author1-link=Robert Tarjan|journal=[[SIAM Journal on Computing]]|volume=17|issue=1|pages=143–178|doi=10.1137/0217010|DOI=10.1137/0217010|mr=925194|MR=925194}}.</ref>、後にKirkpatrick Klaweと[[ロバート・タージャン]]により簡単化された<ref>{{Citation|title=Polygon triangulation in O(''n'' log log ''n'') time with simple data structures|year=1992|last1=Kirkpatrick|last2=Klawe|last3=Tarjan|first1=David G.|first2=Maria M.|first3=Robert E.|author1-link=David G. Kirkpatrick|author2-link=Maria Klawe|author3-link=Robert Tarjan|journal=[[Discrete and Computational Geometry]]|volume=7|issue=4|pages=329–346|doi=10.1007/BF02187846|DOI=10.1007/BF02187846|mr=1148949|MR=1148949}}.</ref>。複数の改善により、<math>O(n\log^{\ast} n)</math>（実用上ほぼ線形時間）を実現している<ref>{{Citation|title=A fast Las Vegas algorithm for triangulating a simple polygon|year=1989|last1=Clarkson|last2=Tarjan|last3=van Wyk|first1=Kenneth L.|first2=Robert|first3=Christopher J.|author1-link=Kenneth L. Clarkson|author2-link=Robert Tarjan|journal=[[Discrete and Computational Geometry]]|volume=4|pages=423–432|doi=10.1007/BF02187741|DOI=10.1007/BF02187741}}.</ref><ref>{{Citation|title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons|year=1991|last=Seidel|first=Raimund|author-link=Raimund Seidel|journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|volume=1|pages=51–64|doi=10.1016/0925-7721(91)90012-4|DOI=10.1016/0925-7721(91)90012-4}}</ref><ref>{{Citation|title=Randomized parallel algorithms for trapezoidal diagrams|year=1992|last1=Clarkson|last2=Cole|last3=Tarjan|first1=Kenneth L.|first2=Richard|first3=Robert E.|author1-link=Kenneth L. Clarkson|author3-link=Robert Tarjan|journal=International Journal of Computational Geometry & Applications|volume=2|issue=2|pages=117–133|doi=10.1142/S0218195992000081|DOI=10.1142/S0218195992000081|mr=1168952|MR=1168952}}.</ref>。

1991年にバーナード・チャゼルは非常な複雑なアルゴリズムではあるが、任意の単純多角形を線形時間で三角形分割するアルゴリズムを示した<ref>{{Citation|title=Triangulating a Simple Polygon in Linear Time|year=1991|last=Chazelle|first=Bernard|author-link=Bernard Chazelle|journal=Discrete & Computational Geometry|volume=6|pages=485–524|doi=10.1007/BF02574703|DOI=10.1007/BF02574703|issn=0179-5376|ISSN=0179-5376}}</ref>。また、乱択アルゴリズムを用いることで、平均計算時間が線形時間であるアルゴリズムも存在する<ref>{{Citation|title=A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time|year=2001 <!--<nowiki>|</nowiki>month=May-->|last1=Amato|last2=Goodrich|last3=Ramos|first1=Nancy M.|first2=Michael T.|first3=Edgar A.|author2-link=Michael T. Goodrich|url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185|journal=Discrete & Computational Geometry|volume=26|issue=2|pages=245–265|doi=10.1007/s00454-001-0027-x|DOI=10.1007/s00454-001-0027-x|issn=0179-5376|ISSN=0179-5376}}</ref>。

ザイデルの分割アルゴリズムとチャゼルの三角形分割については、 {{Harvtxt|Li|Klette|2011}} が詳しい<ref>{{Citation|title=Euclidean Shortest Paths|year=2011|last1=Li|last2=Klette|first1=Fajie|first2=Reinhard|publisher=[[Springer (publisher)|Springer]]|doi=10.1007/978-1-4471-2256-2|DOI=10.1007/978-1-4471-2256-2|isbn=978-1-4471-2255-5|ISBN=978-1-4471-2255-5}}.</ref>。

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

== 関連する問題 ==
[[最小重み三角形分割]]は辺の長さの和が最小となるような三角形分割を求める問題である（三角形の数ではない）。

内部に頂点を追加する三角形分割は頂点の凸包における多角形の三角形分割である。[[ドロネー図]]は点を用いて三角形分割する別の手法である。

多角形の三角形被覆問題は、重複を許す条件での三角形で多角形を被覆する問題である。また、無限平面を多角形で敷き詰める、[[平面充填]]問題も関連する。

== 出典 ==
{{Reflist}}

== 関連項目 ==
* [[カタラン数]]
* [[非ゼロ回転数ルール]]
* [[平面充填]]
* [[平面グラフ]]
* [[三角測量]]
* [[三斜法]]

== 外部リンク ==
* [http://computacion.cs.cinvestav.mx/~anzures/geom/triangulation.php Demo as Flash swf],  A Sweep Line algorithm.
* [http://www.songho.ca/opengl/gl_tessellation.html Song Ho's explanation of the OpenGL GLU tesselator]

{{デフォルトソート:たかくけいのさんかくけいふんかつ}}
[[Category:初等幾何学]]
[[Category:数学に関する記事]]