Polygon triangulation

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygon into a set of triangles.

A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P. In the strictest sense, these triangles may have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serve as vertices of triangles.

Triangulations are special cases of planar straight-line graphs.

A convex polygon is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices. In fact, Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time. The proposed algorithm is very complex though, so Chazelle and others are still looking for easier algorithms.

ubtracting ears method

One way to triangulate a simple polygon is by using the assertion that any simple polygon without holes has at least two so called 'ears'. An ear is a triangle with two sides on the edge of the polygon and the other 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 suboptimal, and it only works on polygons without holes. An implementation that keeps separate lists of convex and reflex vertices will run in "O"("n"2) time. This method is also known as "ear clipping" and sometimes "ear trimming".

Using monotone polygons

A monotone polygon is one with a boundary that consists of two parts, each of which consists of points that have incrementing coordinates in one dimension. Such a polygon can easily be triangulated in linear time as described by A. Fournier and D.Y. Montuno.

To break up a simple polygon into monotone polygons, follow these steps:

For each point, check if the vertices are both on the same side of the 'sweep line', a horizontal or vertical line. If they are, check the next sweep line on the other side. Break the polygon on the line between the original point and one of the points on this one.

Note that if you are moving downwards, the points where both of the vertices are below the sweep line are 'split points'. They mark a split in the polygon. From there you have to consider both sides separately.

Using this algorithm to triangulate a simple polygon takes "O"("n" log "n") time.

ee also

*Catalan number

References

*
*
*
* Chapter 3: Polygon Triangulation: pp.45–61.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Triangulation (disambiguation) — Triangulation refers to measurement by using triangles. The term triangulation may also refer to:Mathematics and computer science*Subdivisions of spaces into triangles or higher dimensional simplices: **triangulation (advanced geometry), division …   Wikipedia

  • Triangulation d'un polygone — En géométrie algorithmique, la triangulation d un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles[1]. Une triangulation d un polygone P est une partition de P en un ensemble de triangles qui ne se recouvrent pas, et… …   Wikipédia en Français

  • Polygon — For other uses, see Polygon (disambiguation). Some polygons of different kinds In geometry a polygon (   …   Wikipedia

  • Polygon-Methode — Beispiel einer Dirichlet Zerlegung zu einer vorgegebenen Menge an Punkten. Die eingezeichneten Linien werden auch als Thiessen Polygone oder Voronoi Diagramm bezeichnet Mit Thiessen Polygonen bzw. Voronoi Diagramm oder Dirichlet Zerlegung wird… …   Deutsch Wikipedia

  • Polygon mesh — A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals or other simple… …   Wikipedia

  • Minimum-weight triangulation — In computational geometry and computer science, the minimum weight triangulation (MWT) problem is the problem of finding a triangulation of minimal weight. Of particular interest is the problem of finding a minimum weight point set triangulation …   Wikipedia

  • Monotone polygon — Green indicates one intersection, blue indicates two intersections, and red indicates three or more. The top two polygons are monotone with respect to L while the bottom two are not. In geometry, a polygon P in the plane is called monotone with… …   Wikipedia

  • Simple polygon — In geometry, a simple polygon is a polygon whose sides do not intersect. They are also called Jordan polygons, because the Jordan curve theorem can be used to prove that such a polygon divides the plane into two regions, the region inside it and… …   Wikipedia

  • Thiessen-Polygon — Beispiel einer Dirichlet Zerlegung zu einer vorgegebenen Menge an Punkten. Die eingezeichneten Linien werden auch als Thiessen Polygone oder Voronoi Diagramm bezeichnet Mit Thiessen Polygonen bzw. Voronoi Diagramm oder Dirichlet Zerlegung wird… …   Deutsch Wikipedia

  • Voronoi-Polygon — Beispiel einer Dirichlet Zerlegung zu einer vorgegebenen Menge an Punkten. Die eingezeichneten Linien werden auch als Thiessen Polygone oder Voronoi Diagramm bezeichnet Mit Thiessen Polygonen bzw. Voronoi Diagramm oder Dirichlet Zerlegung wird… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”