computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, a fan triangulation is a simple way to

triangulate In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle me ...

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

by choosing a

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

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 polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...

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 The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: In the geometric version of the problem, the layout of the art gallery is represente ...

, 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

n

vertices uses

n - 3

diagonals, and generates

n - 2

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 In computer graphics, rasterisation (British English) or rasterization (American English) is the task of taking an image described in a vector graphics format (shapes) and converting it into a raster image (a series of pixels, dots or lines, whic ...

, or

collision detection Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...

, it may be unfit for other tasks because the origin vertex accumulates a high number of neighbors, and the

internal angle In geometry, an angle of a polygon is formed by two sides of the polygon that share an endpoint. For a simple (non-self-intersecting) polygon, regardless of whether it is convex or non-convex, this angle is called an interior angle (or ) if ...

s of the triangulation are unevenly distributed.

References

{{Reflist Triangulation (geometry) Geometric algorithms

Properties

See also

References