Fan triangulation

Short description: Method of triangulating complex polygons

Fan triangulation of a convex polygon

Fan triangulation of a concave polygon with a unique concave vertex.

In computational geometry, a fan triangulation is a simple way to triangulate a polygon by choosing a vertex and drawing edges to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usually only used for convex polygons.

Properties

Aside from the properties of all triangulations, fan triangulations have the following properties:

• All convex polygons, but not all polygons, can be fan triangulated.
• Polygons with only one concave vertex can always be fan triangulated, as long as the diagonals are drawn from the concave vertex.
• It can be known if a polygon can be fan triangulated by solving the Art gallery problem, in order to determine whether there is at least one vertex that is visible from every point in the polygon.
• The triangulation of a polygon with [math]\displaystyle{ n }[/math] vertices uses [math]\displaystyle{ n - 3 }[/math] diagonals, and generates [math]\displaystyle{ n - 2 }[/math] triangles.
• Generating the list of triangles is trivial if an ordered list of vertices is available, and can be computed in linear time. As such, it is unnecessary to explicitly store the list of triangles, and therefore, many graphical libraries implement primitives to represent polygons based on this triangulation.
• Although this triangulation is fit for solving certain problems, such as Rasterisation, or collision detection, it may be unfit for other tasks because the origin vertex accumulates a high number of neighbors, and the internal angles of the triangulation are unevenly distributed.

See also

• Triangle fan