Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Polygon triangulation
Summary
In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) P into a set of triangles, 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.
Over time, a number of algorithms have been proposed to triangulate a polygon.
It is trivial to triangulate any convex polygon in linear time into a fan triangulation, by adding diagonals from one vertex to all other non-nearest neighbor vertices.
The total number of ways to triangulate a convex n-gon by non-intersecting diagonals is the (n−2)nd Catalan number, which equals
a formula found by Leonhard Euler.
A monotone polygon can be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno, or the algorithm of Godfried Toussaint.
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. 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(n2) 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.
A simple polygon is monotone with respect to a line L, if any line orthogonal to L intersects the polygon at most twice. A monotone polygon can be split into two monotone chains.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.