Ear clipping
Ear = vertex whose triangle with neighbors is inside polygon + contains no other vertices. Repeatedly clip ears.
Advertisement
Complexity
Ear clipping: O(N²) with straightforward implementation. Sweep-line: O(N log N). Chazelle 1991: O(N) — impractical constants.
Advertisement
Convex polygon
Trivial: fan from any vertex. O(N). All triangulations of convex polygon have same triangle count = N - 2.
Applications
3D graphics (send triangles to GPU). Physics simulation. FEM meshing.