Fan triangulation

A fan triangulation is a simple way to triangulate a polygon by choosing a vertex and drawing diagonals 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.[1]

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

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 vertices uses diagonals, and generates triangles.[2]
  • 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.[3]
  • 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.
gollark: They might *not* pay you if they run out of money, but otherwise they will.
gollark: Bonds are just a promise by some organization to pay back your money + interest in some amount of time.
gollark: If the company implodes or something you can lose the value of your shares, but not more because limited liability.
gollark: Shares are just partial ownership in a company - you get that amount of their profits and that amount of control of it (by voting for the board of directors).
gollark: Though it's shares, not bonds. They're different.

See also

References
  1. Loera, Jesus; Rambau, Joerg; Santos, Francisco (2010). Triangulations: Structures for Algorithms and Applications. Springer Science & Business Media. pp. 103. ISBN 9783642129711.
  2. O'Rourke, Joseph (1998). Computational geometry in C (2nd ed.). Cambridge, UK: Cambridge University Press. ISBN 9780521649766. OCLC 38542796.
  3. Segal, Mark (24 October 2016). "The OpenGL Graphics System: A Specification" (PDF). Retrieved 2 March 2017.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.