Editing Polygon triangulation (section)

=== Ear clipping method ===
[[Image:Polygon-ear.png|thumb|A polygon ear]]
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 "[[Ear (mathematics)|ear]]s", which are triangles with two sides being the edges of the polygon and the third one completely inside it.<ref>{{citation
| first1=Gary Hosler | last1=Meisters
| title=Polygons have ears
| journal=[[American Mathematical Monthly]]
| volume=82
| year=1975
| issue=6
| pages=648–651
| url=https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1053&context=mathfacpub
| doi=10.2307/2319703| jstor=2319703
}}</ref> 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 {{math|O(<var>n</var><sup>2</sup>)}} 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]].<ref>{{citation
| last1 = ElGindy | first1 = Hossam
| last2 = Everett | first2 = Hazel
| last3 = Toussaint | first3 = Godfried T.
| 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| bibcode = 1993PaReL..14..719E
}}</ref>