The Central Idea
A triangulation of a planar region is a collection of triangles that exactly covers the region without interior overlap. Neighboring triangles may share an edge or a vertex, but their interiors remain disjoint.
If the triangles are \(T_1,T_2,\ldots,T_k\), then a valid triangulation satisfies
\[ \boxed{ R=T_1\cup T_2\cup\cdots\cup T_k }. \]Why Triangles?
A triangle is the simplest polygon that encloses area. Three noncollinear points determine a unique triangle, and many geometric computations become straightforward on triangular pieces.
Triangles support:
- area computation;
- barycentric coordinates;
- linear interpolation;
- surface rendering;
- finite-element approximation;
- mesh-based geometric analysis.
Polygon Triangulation
A polygon triangulation divides a polygon into triangles using polygon vertices and noncrossing diagonals. The added diagonals lie inside the polygon except at their endpoints.
The boundary of the original polygon is preserved. Triangulation adds internal structure without changing the region itself.
What Is a Diagonal?
A diagonal connects two nonadjacent polygon vertices.
For vertices
\[ V_0,V_1,\ldots,V_{n-1}, \]an edge joins adjacent vertices such as \(V_iV_{i+1}\), while a diagonal joins vertices that are not consecutive along the boundary.
Convex Polygons Are Easy to Triangulate
Every diagonal of a convex polygon lies inside the polygon. Therefore, choose one vertex \(V_0\) and connect it to every nonadjacent vertex:
\[ V_0V_2,\quad V_0V_3,\quad \ldots,\quad V_0V_{n-2}. \]This creates a fan triangulation.
Number of Triangles
Every triangulation of a simple polygon with \(n\ge3\) vertices contains
\[ \boxed{n-2} \]triangles.
This is true for both convex and concave simple polygons.
Number of Added Diagonals
A triangulation of a simple \(n\)-vertex polygon uses
\[ \boxed{n-3} \]noncrossing diagonals.
Thus a pentagon contains three triangles and requires two triangulation diagonals.
Area Is Preserved
If a polygon is decomposed into triangles
\[ T_1,T_2,\ldots,T_{n-2}, \]then
\[ \boxed{ \operatorname{Area}(P) = \sum_i \operatorname{Area}(T_i) }. \]This makes triangulation useful for measurement as well as structural decomposition.
Concave Polygons Need More Care
In a concave polygon, not every segment joining nonadjacent vertices lies inside the region. A candidate diagonal can cross the boundary or pass through an exterior indentation.
General polygon triangulation must therefore distinguish valid internal diagonals from invalid ones.
Convex and Reflex Vertices
Assume polygon vertices are listed counterclockwise. A vertex \(V_i\) is locally convex when
\[ \operatorname{orient} (V_{i-1},V_i,V_{i+1})>0. \]It is a reflex vertex when
\[ \boxed{ \operatorname{orient} (V_{i-1},V_i,V_{i+1})<0 }. \]Reflex vertices create the inward turns of a concave polygon.
Polygon Orientation Matters
If the polygon is listed clockwise instead of counterclockwise, the orientation signs reverse.
A robust algorithm should either determine the polygon orientation first or write its turn tests so that either ordering is handled consistently.
Ear Clipping
One of the most intuitive algorithms for triangulating a simple polygon is ear clipping.
The method repeatedly identifies a boundary triangle that can be removed safely. That triangle is called an ear.
What Is an Ear?
For three consecutive polygon vertices
\[ A,\ B,\ C, \]the triangle \(ABC\) is an ear when:
- \(B\) is a convex vertex;
- the diagonal \(AC\) lies inside the polygon;
- no other polygon vertex lies strictly inside triangle \(ABC\).
Clipping an Ear
Once \(A,B,C\) form an ear, record
\[ \triangle ABC \]as one triangle of the triangulation.
Then remove vertex \(B\) from the active polygon boundary and replace edges \(AB\) and \(BC\) with diagonal \(AC\).
Ear Clipping Reduces the Problem
Clipping one ear reduces an \(n\)-vertex polygon to an \((n-1)\)-vertex polygon.
Repeating the process eventually leaves three vertices. Those three form the final triangle.
The Two-Ears Principle
Every simple polygon with at least four vertices has at least two ears.
This guarantees that the clipping process can continue for a valid simple polygon until only one triangle remains.
Testing Convexity of an Ear Candidate
For a counterclockwise polygon, candidate vertex \(B\) in \(A,B,C\) must satisfy
\[ \boxed{ \operatorname{orient}(A,B,C)>0 }. \]If the result is negative, \(B\) is reflex and cannot be the tip of an ordinary ear.
Testing Whether the Ear Is Empty
For every nonadjacent polygon vertex \(P\), perform a point-in-triangle test against
\[ \triangle ABC. \]If another polygon vertex lies strictly inside the triangle, the candidate is not an ear.
Point-in-Triangle Testing
For a counterclockwise triangle \(ABC\), a point \(P\) lies inside or on the triangle when
\[ \operatorname{orient}(A,B,P)\ge0, \] \[ \operatorname{orient}(B,C,P)\ge0, \] \[ \operatorname{orient}(C,A,P)\ge0. \]Thus triangulation reuses the same orientation machinery introduced in earlier computational-geometry lessons.
Valid Diagonals
A valid polygon diagonal must remain within the polygon except at its endpoints.
It must not:
- cross a boundary edge;
- pass through an exterior portion of the polygon;
- create an invalid overlap with the boundary.
Example: A Convex Pentagon
Let a convex pentagon have vertices
\[ V_0,V_1,V_2,V_3,V_4. \]A fan from \(V_0\) uses diagonals \(V_0V_2\) and \(V_0V_3\), creating
\[ \triangle V_0V_1V_2, \] \[ \triangle V_0V_2V_3, \] \[ \triangle V_0V_3V_4. \]Triangulation Is Usually Not Unique
A polygon may admit many different valid triangulations.
For a convex quadrilateral, either diagonal produces a correct triangulation.
Therefore, different algorithms can return different yet equally valid triangle decompositions.
Ear-Clipping Complexity
In a straightforward implementation, many candidate ears may require tests against many remaining vertices.
This leads to the common worst-case running time
\[ \boxed{ O(n^2) }. \]More sophisticated triangulation algorithms can improve on this for some settings.
Triangulating Point Sets
Triangulation also applies to an unstructured set of points.
A planar point-set triangulation connects the points with noncrossing straight edges so that every bounded face is a triangle and the union of those faces covers the convex hull of the point set.
Planar Straight-Line Graphs
A triangulated point set forms a planar straight-line graph.
Vertices are the input points, and edges meet only at shared endpoints. Adding enough noncrossing edges makes every bounded face triangular.
Delaunay Triangulation
Among the many possible point-set triangulations, the Delaunay triangulation is especially important.
It is closely connected to nearest-neighbor structure and Voronoi diagrams, and it tends to avoid unnecessarily thin triangles.
The Empty-Circumcircle Property
For each Delaunay triangle, the open disk inside its circumcircle contains no other input point.
This can be summarized as
\[ \boxed{ \text{no input point lies strictly inside a Delaunay triangle's circumcircle} }. \]Circumcircles
Three noncollinear points determine a unique circle called the circumcircle of their triangle.
Its center is the intersection of the perpendicular bisectors of the three sides.
The In-Circle Predicate
Delaunay algorithms repeatedly ask whether another point lies inside, on, or outside a triangle's circumcircle.
This classification can be computed from a determinant called the in-circle predicate.
Like orientation, it is a sign test whose numerical reliability matters.
Why Delaunay Triangulation Is Useful
Delaunay triangulations appear in:
- terrain modeling;
- geographic information systems;
- interpolation;
- mesh generation;
- scientific computing;
- nearest-neighbor structures.
Delaunay Triangulation Need Not Be Unique
If four or more points are cocircular, more than one triangulation may satisfy the Delaunay condition.
A cyclic quadrilateral, for example, can admit either diagonal.
Local Edge Flipping
Two neighboring triangles in a convex quadrilateral share one diagonal.
Replacing that diagonal with the other diagonal is called an edge flip.
Delaunay algorithms can use edge flips to improve local triangulation structure.
Constrained Triangulation
Some applications require specified line segments to remain present.
Constraints may represent:
- polygon boundaries;
- roads and rivers;
- survey lines;
- material interfaces;
- structural edges.
A constrained triangulation preserves these required segments.
Constrained Delaunay Triangulation
A constrained Delaunay triangulation combines required edges with a Delaunay-like triangulation of the remaining visible geometry.
Constraints can prevent some ordinary Delaunay edge choices, so the criterion is adapted to respect the prescribed geometry.
Polygons with Holes
A region may contain an outer boundary and one or more holes.
A valid triangulation covers the filled portion of the region while leaving each hole uncovered.
Constrained triangulation is a natural framework for such domains.
Triangulation and Barycentric Coordinates
If \(P\) lies in triangle \(ABC\), then
\[ P=\alpha A+\beta B+\gamma C, \]where
\[ \alpha+\beta+\gamma=1. \]These barycentric coordinates are especially useful once a larger region has been triangulated.
Interpolating Data over a Triangle
Suppose values are known at triangle vertices:
\[ f(A),\quad f(B),\quad f(C). \]For
\[ P=\alpha A+\beta B+\gamma C, \]linear interpolation gives
\[ \boxed{ f(P)= \alpha f(A)+ \beta f(B)+ \gamma f(C) }. \]Triangulation in Computer Graphics
Graphics hardware is especially well suited to processing triangles.
Complex surfaces are therefore commonly represented as triangular meshes. Color, depth, texture coordinates, normals, and other quantities can be interpolated across each face.
Triangulation in Numerical Simulation
Finite-element methods divide complicated domains into simple elements.
In two dimensions, triangular elements allow differential equations to be approximated locally and then assembled into a global computational model.
Triangle Quality Matters
Not every valid triangulation is equally useful.
Extremely thin triangles can degrade:
- numerical conditioning;
- interpolation quality;
- simulation accuracy;
- mesh stability.
Delaunay and Angle Quality
A Delaunay triangulation tends to avoid unnecessarily small angles.
More precisely, among triangulations of a planar point set in general position, the Delaunay triangulation maximizes the minimum angle in a lexicographic sense.
This helps explain its importance in mesh generation.
Degenerate Triangles
Three collinear points produce zero area:
\[ \operatorname{orient}(A,B,C)=0. \]Such a triangle is degenerate and should not ordinarily appear as a positive-area face in a planar triangulation.
Repeated Vertices and Zero-Length Edges
Duplicate coordinates can produce zero-length edges, degenerate triangle candidates, and ambiguous adjacency.
Input preprocessing often removes exact duplicate vertices before triangulation begins.
Self-Intersecting Polygon Boundaries
Standard polygon triangulation assumes a well-defined region.
A self-intersecting polygonal path may require a filling rule and boundary decomposition before ordinary triangulation can be applied.
Ear clipping should not simply treat such input as a simple polygon.
Numerical Robustness
Triangulation depends on discrete geometric predicates including:
- orientation;
- point-in-triangle;
- segment intersection;
- in-circle classification.
Small numerical errors can change mesh connectivity and create invalid topology.
Near-Collinear Vertices
If
\[ |\operatorname{orient}(A,B,C)| \]is extremely small, floating-point arithmetic may not classify the turn reliably.
Scale-aware tolerances, higher precision, or exact predicates may be needed.
Near-Cocircular Points
Delaunay triangulation becomes delicate when four points are nearly cocircular.
A tiny numerical change in the in-circle predicate can determine which diagonal is selected.
Verifying a Polygon Triangulation
A candidate triangulation should satisfy all of the following:
- every triangle lies inside the polygon;
- triangle interiors do not overlap;
- shared boundaries match along full edges or vertices;
- the union of the triangles equals the polygon;
- every triangle has positive area unless degeneracy is intentionally allowed.
Verifying the Triangle Count
For a simple \(n\)-vertex polygon without holes, a complete triangulation contains
\[ \boxed{n-2} \]triangles.
A different count is a strong warning that the decomposition is incomplete or structurally incorrect.
Verifying Area
Compare polygon area with the total triangle area:
\[ \boxed{ A_P=\sum_i A_{T_i} }. \]Matching area does not by itself prove topological correctness, but a mismatch proves that the proposed triangulation is wrong.
Common Error: Drawing a Diagonal outside a Concave Polygon
Two nonadjacent polygon vertices do not automatically define a valid internal diagonal.
In a concave polygon, the segment may leave the region or cross the boundary.
Common Error: Treating a Reflex Vertex as an Ear
For a counterclockwise polygon, a reflex vertex satisfies
\[ \operatorname{orient}(A,B,C)<0. \]It forms an inward turn and cannot be the tip of an ordinary ear.
Common Error: Checking Only Local Convexity
A convex vertex does not automatically define an ear.
Another polygon vertex may lie inside the candidate triangle, so the empty-ear condition must also be checked.
Common Error: Allowing Crossing Diagonals
Triangulation is a planar decomposition.
Internal diagonals may share endpoints, but they may not cross in their interiors.
Common Error: Assuming Triangulation Is Unique
Many polygons and point sets admit multiple valid triangulations.
A triangulation should be judged by geometric validity and any requested quality criterion, not by whether it matches one particular edge pattern.
Common Error: Ignoring Triangle Quality
A triangulation can be valid yet poorly suited to numerical modeling if it contains extreme aspect ratios or very small angles.
Mesh quality is a separate requirement from basic triangulation validity.
Common Error: Using Approximate Predicates Inconsistently
If one part of an algorithm treats a nearly collinear configuration as collinear while another treats it as a turn, connectivity can become inconsistent.
The numerical policy should be coherent across all geometric predicates.
A Reliable Procedure for Convex Polygon Triangulation
- Confirm that the polygon is convex.
- Choose one vertex as a fan origin.
- Connect it to every nonadjacent vertex.
- Record the resulting \(n-2\) triangles.
- Verify that the internal diagonals do not cross.
A Reliable Procedure for Ear Clipping
- Confirm that the input is a simple polygon.
- Determine clockwise or counterclockwise vertex order.
- Identify convex candidate vertices.
- Test whether another polygon vertex lies inside each candidate ear.
- Confirm the ear diagonal is valid.
- Record the ear triangle and remove its middle vertex.
- Update neighboring ear status.
- Repeat until three vertices remain.
- Add the final triangle.
- Verify count, area, nonoverlap, and coverage.
A Reliable Procedure for Point-Set Triangulation
- Remove duplicate points if appropriate.
- Determine the convex hull.
- Add noncrossing edges among boundary and interior points.
- Continue until every bounded face is triangular.
- Reject zero-area faces.
- Verify planarity and coverage of the convex hull.
A Reliable Procedure for Delaunay-Oriented Workflows
- Normalize or deduplicate the input point set.
- Use robust orientation and in-circle predicates.
- Construct an initial triangulation or insert points incrementally.
- Test local edges for the Delaunay condition.
- Flip eligible non-Delaunay edges when required.
- Handle cocircular degeneracies consistently.
- Verify the final planar triangulation.
Practice 1: Triangle Count
How many triangles appear in any triangulation of a simple polygon with \(8\) vertices?
Practice 2: Diagonal Count
How many triangulation diagonals are needed for a simple polygon with \(8\) vertices?
Practice 3: Convex Pentagon
How many triangles are produced by a fan triangulation of a convex pentagon?
Practice 4: Reflex Vertex
A counterclockwise polygon has consecutive vertices \(A,B,C\) with
\[ \operatorname{orient}(A,B,C)=-7. \]Is \(B\) convex or reflex?
Practice 5: Ear Candidate
A candidate vertex is locally convex, but another polygon vertex lies strictly inside its adjacent triangle. Is it an ear?
Practice 6: Area Check
A polygon has area \(30\). A proposed triangulation contains triangle areas
\[ 8,\quad7,\quad6,\quad9. \]Does the total area pass the area verification?
Practice 7: Delaunay Circumcircle
In a Delaunay triangulation, may another input point lie strictly inside the circumcircle of one of the triangles?
Practice 8: Collinear Triple
What is the area of a triangle formed by three collinear points?
Practice 9: Constrained Triangulation
What distinguishes a constrained triangulation from an unconstrained point-set triangulation?
Practice 10: Why Triangulate?
Give two reasons that triangulation is useful in computation.
Practice Answers
Practice 1
\[ 8-2=\boxed{6}. \]Practice 2
\[ 8-3=\boxed{5}. \]Practice 3
\[ 5-2=\boxed{3}. \]Practice 4
The orientation is negative, so the vertex makes an inward turn in a counterclockwise polygon.
\[ \boxed{B\text{ is reflex}.} \]Practice 5
No. Local convexity is necessary but not sufficient.
\[ \boxed{\text{The candidate is not an ear}.} \]Practice 6
\[ 8+7+6+9=30. \]Therefore,
\[ \boxed{\text{the area total passes the check}.} \]Additional topological checks are still required.
Practice 7
No. The empty-circumcircle property excludes another input point from the open circumdisk.
\[ \boxed{\text{No}.} \]Practice 8
Three collinear points form a zero-area degenerate triangle.
\[ \boxed{0}. \]Practice 9
A constrained triangulation must preserve specified segments or boundaries as triangulation edges.
Practice 10
Valid reasons include:
- triangles are easy to render;
- triangles support barycentric interpolation;
- areas can be accumulated triangle by triangle;
- finite-element methods can approximate equations locally;
- complex regions become easier to analyze;
- meshes support graphics, GIS, and simulation.
What to Remember
Triangulation decomposes geometric regions into simple triangular pieces.
- a simple \(n\)-vertex polygon triangulates into \(n-2\) triangles;
- such a triangulation uses \(n-3\) diagonals;
- convex polygons admit simple fan triangulations;
- concave polygons require valid internal diagonals;
- ear clipping repeatedly removes safe boundary triangles;
- orientation distinguishes convex and reflex vertices;
- point-in-triangle tests help verify ear candidates;
- Delaunay triangulation uses the empty-circumcircle condition;
- constrained triangulations preserve required segments;
- triangle quality matters in numerical applications;
- robust predicates are essential near collinear and cocircular degeneracies.
The larger computational lesson is that complicated geometry often becomes manageable when it is decomposed into simple local pieces with clear adjacency and well-understood formulas.
Where We Go Next
Triangulation divides space into simple connected pieces. The next lesson studies another fundamental way to partition space, this time according to proximity to a collection of sites.
Voronoi Diagrams and Spatial Partitions develops regions defined by nearest-site relationships and connects directly to Delaunay triangulation, geographic analysis, facility placement, and spatial organization.