Polygon Triangulation

Almost every 3D game, engineering simulation, and GIS system relies on decomposing regions into triangles. The triangle is the minimal building block: any surface, any polygon can be represented as a set of triangles. But the quality of those triangles directly affects computation accuracy and rendering speed.

• **Finite element methods (FEM)** - in ANSYS, Abaqus: mesh quality directly affects stress calculation accuracy
• **Navigation meshes** - in games (Unity, Unreal): agents move through triangulated polygons
• **GIS** - terrain (TIN - Triangulated Irregular Network) is built by triangulation algorithms
• **Computer graphics** - any polygon mesh is a triangulation of a surface

Ear Clipping Algorithm

Any simple polygon without holes can be decomposed into triangles. In 1975, Meisters proved: every simple polygon with n > 3 vertices has at least two 'ears' - vertices whose triangle lies entirely inside the polygon. Clip an ear, repeat - the result is n-2 triangles.

**Meisters' Two Ears Theorem:** every simple polygon with n >= 4 vertices has at least two ears. Exception: a triangle (n=3), where all vertices are ears. This guarantees the algorithm always finds an ear and terminates.

Monotone Polygon Triangulation in O(n log n)

Ear clipping runs in O(n^2). A faster approach: decompose an arbitrary polygon into monotone parts, then triangulate each monotone part in O(n). The Lee-Preparata algorithm from 1977 achieves O(n log n) for any simple polygon.

**O(n log n) is optimal** for general-case triangulation: a lower bound via sorting shows no faster algorithm exists (without additional structural constraints). Chazelle's 1991 algorithm runs in O(n) but is so complex to implement that O(n log n) is universally used in practice.

Constrained Delaunay Triangulation

Plain Delaunay triangulation maximizes the minimum angle - best quality for numerical methods. But what if there are constraints: building walls, riverbanks, domain boundaries? Constrained Delaunay Triangulation (CDT) respects these constraints while staying as close to Delaunay as possible.

**CDT applications:** finite element modeling (FEM), computer graphics (navigation meshes), GIS (terrain with roads and rivers). Constraints ensure the domain boundary is exactly represented in the mesh - without a constraint edge, a triangulator could 'cut a corner' across a boundary.

Quality Triangulation and Ruppert's Algorithm

For numerical methods (finite elements, PDEs), triangle quality matters: very obtuse or very acute triangles degrade computational accuracy. Ruppert's algorithm (1995) builds a triangulation with a guaranteed minimum angle - classically 20.7 degrees.

**Ruppert's termination theorem:** if no constraint edge is shorter than a certain threshold, the algorithm terminates and produces a triangulation with minimum angle >= 20.7 deg. The bound 20.7 deg is not arbitrary - with a larger threshold the algorithm may loop due to conflicts between Steiner points near constraint edges.

Polygon Triangulation

• Ear Clipping: O(n^2), Meisters' theorem guarantees >= 2 ears in any simple polygon
• Any simple n-vertex polygon triangulates into exactly n-2 triangles
• Monotone triangulation: O(n log n) - decompose into monotone parts + O(n) stack algorithm
• CDT adds constraint edges to Delaunay triangulation, preserving quality elsewhere
• Quality triangulation (Ruppert): Steiner points guarantee minimum angle >= 20.7 deg
• Quality metrics: minimum angle, radius-edge ratio R/l, aspect ratio

Related Topics

Polygon triangulation connects computational geometry algorithms with practical modeling tasks.

• Delaunay Triangulation — Optimal triangulation by angle criterion
• Voronoi Diagrams — Dual structure to Delaunay triangulation
• 3D Computational Geometry — Extending triangulation to the three-dimensional case

Вопросы для размышления

• Why do degenerate (very acute) triangles degrade the accuracy of finite element methods?
• Ear clipping is simple to implement but O(n^2). In which real tasks is this acceptable, and when is O(n log n) necessary?
• Chazelle's 1991 algorithm triangulates in O(n) but is so complex it is never used in practice. What does this say about the relationship between theory and practice in algorithmics?

Связанные уроки

• alg-22-backtracking