Polygon Decomposition, Triangulation, and Convex Decomposition Algorithms

Polygon

A polygon is a closed polyline. Each point Pi is called a vertex, and each line segment is called an edge.

If non‑adjacent edges do not intersect, the polygon is a simple polygon .

If for any two points inside the polygon the segment connecting them also lies inside, the polygon is a convex polygon .

A non‑convex polygon is called a concave polygon .

Polygon Decomposition

Vertex Visibility

A key concept is the visibility between vertices.

Two vertices Vi and Vj are mutually visible if the open segment joining them lies strictly inside the polygon, i.e., there is an unobstructed line of sight.

When two vertices are mutually visible, the segment joining them is called a diagonal .

If the interior angle at a vertex (measured inside the polygon) is less than π, the vertex is a convex vertex . This interior angle is the vertex’s internal angle.

If the two incident edges are collinear, the vertex is a collinear vertex .

If the interior angle exceeds π, the vertex is a reflex vertex .

Visibility of Vi‑1 and Vi+1

If Vi is a reflex vertex, Vi‑1 and Vi+1 are not mutually visible.

If Vi is a convex vertex and no other polygon vertex lies inside triangle (Vi‑1, Vi, Vi+1), then Vi‑1 and Vi+1 are mutually visible. The naive algorithm runs in O(n²), where n is the number of vertices.

In fact, checking the containment of the triangle for reflex vertices is sufficient; this yields an O(n·r) algorithm, where r is the number of reflex vertices.

Ears and Ear Tips

If (Vi‑1, Vi+1) forms a diagonal, the triple (Vi‑1, Vi, Vi+1) constitutes an ear , and Vi is the ear tip .

Visibility Between Arbitrary Vertices

Testing whether (Vi, Vj) (|i‑j|≥2) is a diagonal is straightforward: iterate over all polygon edges and check for any intersection with segment (Vi, Vj), ignoring edges adjacent to the segment (special handling is needed for collinear adjacent edges).

If any non‑adjacent edge intersects the segment, the segment is not a diagonal.

If no such intersections exist, the segment is either a diagonal or lies outside the polygon. It suffices to examine the local configuration at one endpoint (e.g., Vi) and ensure the segment lies within the cone defined by Vi‑1–Vi and Vi–Vi+1.

Triangulation (Decomposing a Polygon into Triangles)

Given a simple polygon with vertices Vi (0 ≤ i < n), a triangulation partitions the polygon into triangles whose vertices are original polygon vertices. Any two resulting triangles intersect only at shared vertices or edges.

The edges of these triangles must lie inside the polygon, so they are diagonals.

All diagonals used in a triangulation must be non‑intersecting.

Any triangulation of an n‑vertex polygon uses exactly n‑3 diagonals and produces n‑2 triangles.

Triangulation via Ear Clipping

Because triangulation is closely related to diagonals, a divide‑and‑conquer approach can be used: find a diagonal, split the polygon into two sub‑polygons, and recursively triangulate each. This naive method has O(n³) time complexity.

The ear‑clipping method avoids searching all diagonals; it repeatedly finds an ear, adds the corresponding triangle to the list, removes the ear, and recurses on the reduced polygon, also O(n³).

A refined ear‑clipping algorithm achieves O(n²) time by scanning the polygon once, tracking ear tips, and updating only the two neighboring vertices after each ear removal.

More efficient triangulation algorithms exist, but they are complex and not discussed here.

Effect

Convex Decomposition (Decomposing a Concave Polygon into Convex Sub‑Polygons)

Triangulation is a special case of decomposing a polygon into convex sub‑polygons. For an n‑vertex polygon, triangulation yields n‑2 convex sub‑polygons. The more general problem seeks a decomposition into the minimum number of convex pieces, possibly requiring additional points and segments, though the discussed method uses only diagonals.

Effect

https://roombox.xdf.cn/blog/img/2021-04-02-convex-decomposition-of-simple-polygon/convexDecomposition01.gif

A Fast Sub‑Optimal Convex Decomposition

Hertel and Mehlhorn (1983) proposed a simple, fast, sub‑optimal convex decomposition algorithm.

Given a diagonal‑based convex decomposition, a diagonal incident to vertex V is a basic diagonal if removing it makes the polygon non‑convex at V; otherwise it is a non‑basic diagonal . A diagonal connecting two convex vertices is non‑basic. A basic diagonal implies V is a reflex vertex, though a reflex vertex may also be an endpoint of a non‑basic diagonal.

The algorithm first triangulates the polygon, then repeatedly removes all non‑basic diagonals, one at a time. Its time complexity is dominated by the triangulation step.

Optimized Convex Decomposition

Keil and Snoeyink (1998) introduced an optimized convex decomposition algorithm that works only with diagonals and runs in O(n·r²) time, where n is the number of vertices and r is the number of reflex vertices. It is based on dynamic programming (Bellman 1987). The algorithm is complex and not detailed here.

References

【1】 Zhou Changfa. Detailed Algorithms of Geometric Tools in Computer Graphics. Electronic Industry Press, 2005.

【2】 Philip J. Schneider, David H. Eberly. Geometric Tools for Computer Graphics.