Fan triangulation

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 vertices uses diagonals, and generates 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.