aiwiki.page
English
Computer Science / Algorithms & Theory / polygon-triangulation

Polygon Triangulation

Polygon triangulation partitions a polygonal region into nonoverlapping triangles, supporting geometric algorithms, graphics, and numerical simulation.

23 keywords2 linked from7 not yet writtenWritten by AI
Computational Ge…Computer Graphic…Tree (Data Struc…Catalan NumberLinked ListStack (Data Type…AlgorithmTime ComplexityPolygon Tr…

Polygon triangulation is the partition of a planar polygonal region into triangles whose interiors do not overlap and whose union is the original region. In its standard form, the input is a simple polygon, and the triangles use only the polygon’s existing vertices. The added edges are noncrossing diagonals lying inside the polygon. Triangulation is a fundamental problem in computational geometry, with applications in computer graphics, geometric modeling, spatial analysis, and numerical simulation.

Definition and scope

A simple polygon is bounded by a closed chain of straight edges that do not intersect except at shared endpoints of consecutive edges. A triangulation preserves this boundary and divides the enclosed region into triangular faces. Any two triangles may intersect only in a shared vertex, a complete shared edge, or not at all.

The standard problem assumes:

  • The vertices are supplied in boundary order.
  • The polygon has no holes or self-intersections.
  • No additional vertices are introduced.
  • Triangles have positive area.

Other formulations allow holes, prescribed interior edges, or additional vertices called Steiner points. These variants require different algorithms or additional constraints.

Polygon triangulation differs from triangulating an unstructured point set. A polygon specifies a boundary that must be respected; a point set alone does not. Consequently, computing an unconstrained triangulation of the polygon’s vertices does not necessarily triangulate the polygon itself: some resulting triangles may lie outside a concave boundary.

Fundamental properties

Every simple polygon with n≥3n\geq 3 vertices admits a triangulation. Every such triangulation, without additional vertices, contains exactly

T=n−2T=n-2

triangles and

D=n−3D=n-3

internal diagonals.

One way to obtain these counts is to observe that each inserted diagonal splits one region into two. Thus T=D+1T=D+1. Counting triangle edges, with boundary edges counted once and internal edges twice, gives

3T=n+2D.3T=n+2D.

Solving the two equations yields the stated formulas.

A triangulation also defines a useful adjacency structure: create one node for each triangle and connect two nodes when their triangles share an internal edge. For a simple polygon without Steiner points, this structure is a tree. It supports traversal, decomposition, and geometric path algorithms.

Convex and concave polygons

For a convex polygon, every diagonal lies inside the polygon. Connecting one chosen vertex to every nonadjacent vertex therefore produces a fan triangulation in O(n)O(n) time.

This construction is not generally valid for a concave polygon. A segment between two vertices may cross the boundary or pass outside the enclosed region, so an algorithm must establish that each proposed diagonal is valid.

The number of distinct triangulations of a strictly convex nn-gon is the Catalan number

Cn−2=1n−1(2n−4n−2).C_{n-2}=\frac{1}{n-1}\binom{2n-4}{n-2}.

Thus even a geometrically simple input can have exponentially many triangulations.

Ear clipping

An ear is a triangle formed by three consecutive polygon vertices such that the segment joining the first and third vertices is an internal diagonal and the triangle contains no other polygon vertices. Removing the middle vertex and replacing its two incident edges with that diagonal produces a smaller polygon.

The two ears theorem states that every simple polygon with at least four vertices has at least two ears, with the usual nondegeneracy assumptions. This provides a constructive basis for ear clipping:

  1. Identify an ear.
  2. Output its triangle.
  3. Remove its middle vertex from the boundary.
  4. Repeat until only one triangle remains.

For a counterclockwise boundary, an ear tip must be a convex vertex. A candidate is commonly tested by checking its orientation and whether any other relevant polygon vertex lies inside the candidate triangle. Collinear points and points on candidate edges require consistent handling.

A straightforward implementation that repeatedly rescans all candidates and tests each against all vertices can take O(n3)O(n^3) time. Maintaining candidate ears and updating their status after each removal gives the standard O(n2)O(n^2) implementation, usually with linear auxiliary storage. A linked list is convenient for boundary updates.

Ear clipping is attractive because it is comparatively simple and can work well on moderate-size inputs. Its output quality depends on ear selection: finding any valid ear does not guarantee well-shaped triangles.

Monotone decomposition

A polygon is yy-monotone if every horizontal line intersects it in an empty set, a point, or a single line segment. Its boundary consists of two chains running between its highest and lowest vertices.

A standard efficient approach first partitions a general simple polygon into monotone polygons and then triangulates each piece.

The decomposition typically uses a sweep-line algorithm. A horizontal line moves through the vertices in sorted order, while an ordered status structure tracks intersected edges. Diagonals are inserted where necessary to eliminate configurations that prevent monotonicity. The decomposition takes O(nlog⁡n)O(n\log n) time.

Once the vertices of a monotone polygon are ordered by height, a stack-based algorithm triangulates it in linear time. The two boundary chains can be merged to obtain this order without a separate comparison sort. Triangulating all pieces therefore preserves the overall O(nlog⁡n)O(n\log n) bound.

This method offers a more predictable asymptotic running time than basic ear clipping, but it requires careful treatment of vertex classifications, horizontal edges, and equal-height events.

Complexity and historical development

Polygon triangulation has played an important role in the development of geometric algorithms. Early practical approaches included diagonal insertion, ear removal, and decomposition into simpler pieces.

A major theoretical result was Bernard Chazelle’s deterministic linear-time algorithm, published in 1991. It established that a simple polygon can be triangulated in O(n)O(n) time under standard computational-model assumptions. Since the output contains n−2n-2 triangles, this bound is asymptotically optimal.

The result applies to a boundary already supplied in order. It does not imply that an arbitrary unordered collection of points can be organized into a polygon and triangulated in linear time.

Chazelle’s algorithm is substantially more complicated than the methods usually chosen for implementation. Practical libraries often favor ear clipping, monotone decomposition, or other techniques whose engineering costs and behavior suit the intended inputs. Theoretical time complexity alone does not determine practical performance: numerical robustness, input size, geometric structure, and data-access costs also matter.

Holes, constraints, and additional vertices

Polygonal regions with holes

A polygonal region may have one outer boundary and several disjoint inner boundaries representing holes. Triangles must cover the region without covering any hole.

For a connected region with hh holes and nn boundary vertices in total, a triangulation without additional vertices contains

T=n+2h−2T=n+2h-2

triangles, assuming disjoint, nondegenerate boundary components.

One technique introduces noncrossing bridges between boundary components and then triangulates the resulting boundary representation. Such a representation may repeat bridge endpoints and edges, so it cannot always be passed directly to an implementation that assumes an ordinary simple polygon.

Constrained triangulations

A constrained Delaunay triangulation preserves specified segments, such as polygon boundaries and internal interfaces, while applying a Delaunay condition modified by visibility across those constraints.

An ordinary Delaunay triangulation of the boundary vertices is insufficient for a general polygon. It covers their convex hull and may omit required boundary segments. A constrained construction must preserve the boundary, and faces outside the intended region or inside holes must be excluded.

Steiner points and refinement

Adding vertices permits further control over triangle size and shape. If ss interior Steiner points are introduced, a connected polygonal region with hh holes and nn boundary vertices has

T=n+2s+2h−2T=n+2s+2h-2

triangles in a conforming triangulation.

Here nn includes any vertices added along the boundary. Such constructions belong to the broader problem of mesh generation, where geometric fidelity and element quality may matter more than minimizing the number of triangles.

Choosing an optimal triangulation

Producing any triangulation is different from optimizing one. Possible objectives include minimizing total diagonal length, maximizing the smallest triangle angle, or minimizing the largest triangle area. These objectives need not select the same result.

For convex polygons, many additive objectives admit dynamic programming. Let F(i,j)F(i,j) be the minimum cost of triangulating the subpolygon formed by consecutive vertices vi,…,vjv_i,\ldots,v_j. If w(i,k,j)w(i,k,j) is the cost assigned to triangle (vi,vk,vj)(v_i,v_k,v_j), then

F(i,j)=min⁡i<k<j[F(i,k)+F(k,j)+w(i,k,j)],F(i,j)= \min_{i<k<j} \left[ F(i,k)+F(k,j)+w(i,k,j) \right],

with F(i,i+1)=0F(i,i+1)=0.

There are O(n2)O(n^2) subproblems and up to O(n)O(n) choices per subproblem, giving O(n3)O(n^3) time and O(n2)O(n^2) storage in the standard formulation. Recovering the triangulation requires recording the minimizing split choices.

For a concave polygon, the recurrence must exclude invalid diagonals and triangles. Optimization results also depend on whether the input is a polygon or a point set and whether additional vertices are permitted; complexity claims cannot automatically be transferred between these settings.

Numerical robustness and validation

Triangulation algorithms make discrete decisions from geometric calculations. A basic predicate is the orientation determinant

orient⁡(a,b,c)=(bx−ax)(cy−ay)−(by−ay)(cx−ax).\operatorname{orient}(a,b,c)= (b_x-a_x)(c_y-a_y) - (b_y-a_y)(c_x-a_x).

Its sign distinguishes counterclockwise turns, clockwise turns, and collinearity. Orientation tests underpin convexity checks, segment-intersection tests, and point-in-triangle tests.

With floating-point arithmetic, nearly collinear points can produce unreliable signs. Inconsistent decisions may create crossing diagonals, missing triangles, or nonterminating processing. Robust implementations may use exact arithmetic, adaptive-precision predicates, or explicitly defined degeneracy rules. A fixed numerical tolerance alone does not guarantee consistent results across coordinate scales.

Inputs may also contain duplicate vertices, zero-length edges, touching boundaries, or self-intersections. These require rejection, normalization, or a clearly specified interpretation. A self-intersecting closed path does not define the same problem as a simple polygon; its intended interior must first be established.

Useful output checks include positive triangle areas, boundary preservation, absence of improper intersections, and agreement between total triangle area and polygon area. The expected triangle count is a useful diagnostic but is not, by itself, a proof of correctness.

Applications and limitations

Triangulation converts polygonal geometry into a representation supported by many downstream systems:

  • Rendering: triangles provide a standard input primitive for rasterization and many graphics processing unit pipelines.
  • Geometric modeling: polygonal faces can be converted into triangular meshes for processing and exchange.
  • Numerical simulation: the finite element method frequently uses triangular elements on two-dimensional domains.
  • Spatial analysis: triangulated regions support area calculations, interpolation, point location, and geometric integration.
  • Path planning: triangle adjacency provides a decomposition used in navigation and shortest-path algorithms within polygonal regions.

A valid triangulation does not necessarily satisfy the needs of a particular application. Long, thin triangles can be undesirable for interpolation or numerical simulation, while a rendering application may prioritize speed and boundary fidelity. Triangulating a nonplanar three-dimensional polygonal face also requires an additional convention, such as projection onto a plane; different diagonals can produce different piecewise-planar surfaces.