“Polygon triangulation”的意思、由来-开放百科全书

In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles,^[1] i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

Triangulations may be viewed as special cases of planar straight-line graphs. When there are no holes or added points, triangulations form maximal outerplanar graphs.

Polygon triangulation without extra vertices

Special cases

It is trivial to triangulate any convex polygon in linear time into a fan triangulation, by adding diagonals from one vertex to all other vertices.

The total number of ways to triangulate a convex n-gon by non-intersecting diagonals is the (n − 2)-th Catalan number, which equals

, a solution found by Leonhard Euler.^[2]

A monotone polygon can be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno,^[3] or the algorithm of Godfried Toussaint.^[4]

Ear clipping method

One way to triangulate a simple polygon is based on the two ears theorem, as the fact that any simple polygon with at least 4 vertices without holes has at least two 'ears', which are triangles with two sides being the edges of the polygon and the third one completely inside it.^[5] The algorithm then consists of finding such an ear, removing it from the polygon (which results in a new polygon that still meets the conditions) and repeating until there is only one triangle left.

This algorithm is easy to implement, but slower than some other algorithms, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run in O(n²) time. This method is known as ear clipping and sometimes ear trimming. An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, and Godfried Toussaint.^[6]

Monotone Polygon Triangulation

A polygonal chain C is called monotone with respect to a straight line L, if every line orthogonal to L intersects C at most once. We call these chains monotone chains. A polygon P is monotone with respect to a line L if its boundary can be split into two chains, each being monotone with respect to L. We call these polygons monotone polygons. We say that a polygon P is horizontally monotone (or x-monotone

We can triangulate a monotone polygon in

time, where

is the number of vertices of the monotone polygon. The algorithm is described in section 3.3 of the book Computational Geometry: Algorithms and Applications (3rd edition), by Berg et al.

Decomposition of a Simple Polygon into Monotone Pieces

If a simple polygon is not monotone, it can be made monotone, in

time, using a sweep-line approach. To see it, read section 3.2 of the book Computational Geometry: Algorithms and Applications (3rd edition) by Berg et al.

Dual graph of a triangulation

A useful graph that is often associated with a triangulation of a polygon {{math|P}} is the dual graph. Given a triangulation {{math|T_P}} of {{math|P}}, one defines the graph {{math|G(T_P)}} as the graph whose vertex set are the triangles of {{math|T_P}}, two vertices (triangles) being adjacent if and only if they share a diagonal. It is easy to observe that {{math|G(T_P)}} is a tree with maximum degree 3.

Computational complexity

Until 1988, whether a simple polygon can be triangulated faster than {{math|O(n log n)}} time was an open problem in computational geometry.^[1] Then, {{harvtxt|Tarjan|Van Wyk|1988}} discovered an {{math|O(n log log n)}}-time algorithm for triangulation,^[7] later simplified by {{harvtxt|Kirkpatrick|Klawe|Tarjan|1992}}.^[8] Several improved methods with complexity {{math|O(n log^* n)}} (in practice, indistinguishable from linear time) followed.^[9]^[10]^[11]

Seidel's decomposition algorithm and Chazelle's triangulation method are discussed in detail in {{harvtxt|Li|Klette|2011}}.

The time complexity of triangulation of an {{math|n}}-vertex polygon with holes has an {{math|Ω(n log n)}} lower bound.^[1]

See also

References

1. ^¹²{{Citation|author = Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf | year = 2000 | title = Computational Geometry | publisher = Springer-Verlag | edition = 2nd revised | isbn = 3-540-65620-0}} Chapter 3: Polygon Triangulation: pp.45–61.
2. ^Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
3. ^{{Citation |last1=Fournier |first1=A. |author1-link=Alain Fournier |last2=Montuno |first2=D. Y. |author2-link= |title=Triangulating simple polygons and equivalent problems |journal=ACM Transactions on Graphics |volume=3 |issue=2 | year=1984 |pages=153–174 |issn=0730-0301 |doi=10.1145/357337.357341}}
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." American Mathematical Monthly 82 (1975). 648–651
6. ^{{cite journal | last1 = ElGindy | first1 = H. | last2 = Everett | first2 = H. | last3 = Toussaint | first3 = G. T. | year = 1993 | title = Slicing an ear using prune-and-search | url = | journal = Pattern Recognition Letters | volume = 14 | issue = 9| pages = 719–722 | doi=10.1016/0167-8655(93)90141-y}}
7. ^{{citation | last1 = Tarjan | first1 = Robert E. | author1-link = Robert Tarjan | last2 = Van Wyk | first2 = Christopher J. | doi = 10.1137/0217010 | issue = 1 | journal = SIAM Journal on Computing | mr = 925194 | pages = 143–178 | title = An O(n log log n)-time algorithm for triangulating a simple polygon | volume = 17 | year = 1988| citeseerx = 10.1.1.186.5949}}.
8. ^{{citation | last1 = Kirkpatrick | first1 = David G. | author1-link = David G. Kirkpatrick | last2 = Klawe | first2 = Maria M. | author2-link = Maria Klawe | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan | doi = 10.1007/BF02187846 | issue = 4 | journal = Discrete and Computational Geometry | mr = 1148949 | pages = 329–346 | title = Polygon triangulation in O(n log log n) time with simple data structures | volume = 7 | year = 1992}}.
9. ^{{citation | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson | last2 = Tarjan | first2 = Robert | author2-link = Robert Tarjan | last3 = van Wyk | first3 = Christopher J. | doi = 10.1007/BF02187741 | journal = Discrete and Computational Geometry | pages = 423–432 | title = A fast Las Vegas algorithm for triangulating a simple polygon | volume = 4 | year = 1989}}.
10. ^{{Citation |last=Seidel|first=Raimund |author-link= Raimund Seidel| title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=Computational Geometry: Theory and Applications |volume=1 |year=1991 |pages=51–64 |doi=10.1016/0925-7721(91)90012-4}}
11. ^{{citation | last1 = Clarkson | first1 = Kenneth L. | author1-link = Kenneth L. Clarkson | last2 = Cole | first2 = Richard | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan | doi = 10.1142/S0218195992000081 | issue = 2 | journal = International Journal of Computational Geometry & Applications | mr = 1168952 | pages = 117–133 | title = Randomized parallel algorithms for trapezoidal diagrams | volume = 2 | year = 1992}}.
12. ^{{Citation |last=Chazelle |first=Bernard |author-link=Bernard Chazelle | title=Triangulating a Simple Polygon in Linear Time |journal=Discrete & Computational Geometry |volume=6 |year=1991|pages=485–524 |issn=0179-5376 |doi=10.1007/BF02574703}}
13. ^{{Citation |last1=Amato |first1=Nancy M. | author1-link = Nancy M. Amato |last2=Goodrich |first2=Michael T. |author2-link=Michael T. Goodrich|last3=Ramos |first3=Edgar A. |title=A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time |journal=Discrete & Computational Geometry |volume=26 |year=2001 |pages=245–265 |issn=0179-5376 |doi=10.1007/s00454-001-0027-x |url=http://parasol.tamu.edu/publications/abstract.php?pub_id=185 |issue=2}}
14. ^{{citation | last1 = Li | first1 = Fajie | last2 = Klette | first2 = Reinhard | title = Euclidean Shortest Paths | publisher = Springer | doi = 10.1007/978-1-4471-2256-2 | ISBN = 978-1-4471-2255-5 | year = 2011}}.