Polygon triangulation: Difference between revisions
No edit summary |
rm false statement: the article describes linear *average time* compexity algorithms; such ones have been known for a long time |
||
| Line 12: | Line 12: | ||
[[Bernard Chazelle]] showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.<ref>{{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}}</ref> |
[[Bernard Chazelle]] showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.<ref>{{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}}</ref> |
||
Finally, in 1998 the first practical ''O''(''n'') algorithms were discovered and published by Alexey V. Skvortsov and Yuri L. Kostyuk.<ref>{{Citation | author = Alexey V. Skvortsov, Yuri L. Kostyuk | title = Efficient algorithms for Delaunay triangulation | publisher = Tomsk State University | journal = Geoinformatics. Theory and practice | volume = 1 | year = 1998 | pages = 22–47 | url = http://www.inf.tsu.ru/Library/Publications/1999/Skvortsov_1999_1.pdf}} {{ru icon}}</ref> The fastest of these algorithms employs ''dynamic triangle caching''.{{Citation needed|date=April 2010}} |
|||
The [[time complexity]] of triangulation of a polygon with holes has an Ω(''n'' log ''n'') [[lower bound]].<ref name= bkos/> |
The [[time complexity]] of triangulation of a polygon with holes has an Ω(''n'' log ''n'') [[lower bound]].<ref name= bkos/> |
||
Revision as of 19:54, 19 April 2010
In computational geometry, polygon triangulation is the decomposition of a polygon into a set of triangles.[1]
A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P. In the strict sense, these triangles may have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serve as vertices of triangles.
Triangulations are special cases of planar straight-line graphs.
A convex polygon is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices.
A monotone polygon can easily be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno,[2] or the algorithm of Godfried Toussaint[3]
For a long time there was an open problem in computational geometry whether a simple polygon can be triangulated faster than O(n log n) time.[1] In 1990 David G. Kirkpatrick, Maria M. Klawe, Robert E. Tarjan discovered an O(n log log n) algorithm for triangulation. Simple randomised methods such as Seidel's [4] or Clarkson et al's, have O(n log* n) behaviour which, in practice, are indistinguishable from O(n).
Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time, though the proposed algorithm is very complex.[5]
The time complexity of triangulation of a polygon with holes has an Ω(n log n) lower bound.[1]
Algorithms
Over time a number of algorithms have been proposed to triangulate a polygon.
Subtracting ears method
One way to triangulate a simple polygon is by using the assertion that any simple polygon without holes has at least two so called 'ears'. An ear is a triangle with two sides on the edge of the polygon and the other one completely inside it. 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 suboptimal, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run in O(n2) time. This method is also 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]
Using monotone polygons
A simple polygon may be decomposed into monotone polygons as follows.[1]
For each point, check if the vertices are both on the same side of the 'sweep line', a horizontal or vertical line. If they are, check the next sweep line on the other side. Break the polygon on the line between the original point and one of the points on this one.
Note that if you are moving downwards, the points where both of the vertices are below the sweep line are 'split points'. They mark a split in the polygon. From there you have to consider both sides separately.
Using this algorithm to triangulate a simple polygon takes O(n log n) time.
See also
References
- ^ a b c d Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 3-540-65620-0.
{{cite book}}: CS1 maint: multiple names: authors list (link) Chapter 3: Polygon Triangulation: pp.45–61. - ^ 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.
- ^ 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
- ^ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6: 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
- ^ ElGindy, H., Everett, H., and Toussaint, G. T., (1993) "Slicing an ear using prune-and-search," Pattern Recognition Letters, 14, (9):719-722.
- 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