Triangulation of Vector Graphics: Polygon Decomposition and Monotone Polygon Algorithms

This article continues the discussion from the previous post on converting a vector‑graphics path description into GPU‑readable triangle vertex data. The overall pipeline consists of path poly‑line approximation, simplification of complex polygons, monotone polygon decomposition, and finally triangulation.

Key concepts introduced:

Simple polygon : a polygon whose edges do not intersect.

Complex polygon : any polygon that is not simple.

Monotone polygon : a polygon that can be split into two monotone chains (x‑monotone or y‑monotone).

Poly‑line approximation (折线化)

The article explains how to approximate quadratic, cubic and rational Bézier curves by recursively subdividing them using a binary search until the distance between the curve midpoint and the line‑segment midpoint is less than a threshold τ. For rational Bézier curves, a fixed number of quadratic Bézier approximations are generated (as described in [1]), then each quadratic Bézier is poly‑lined using the same binary subdivision.

// Pseudo‑code for Bézier subdivision for each Bézier segment: while distance(curve_mid, line_mid) > τ: split segment into two halves process each half

Complex polygon simplification

After poly‑lining, the resulting shape may contain self‑intersections. The article describes a two‑step approach: first compute all intersection points by checking bounding‑box overlap, then split intersecting edges at those points to obtain a set of simple polygons.

Bentley‑Ottmann algorithm

The classic sweep‑line algorithm is presented for efficiently finding all intersections among n line segments in O((n + k) log n) time, where k is the number of intersections. The algorithm maintains an X‑structure (event queue) sorted by x‑coordinate and a Y‑structure (active set) sorted by the y‑coordinate of the intersection with the sweep line. The article details handling of left endpoints, right endpoints, and intersection events, as well as the update rules for the active set.

Monotone polygon decomposition

Simple polygons are further decomposed into monotone polygons. The article defines x‑monotone chains, monotone mountains (one chain is a straight line), and explains how to classify vertices (split, merge, regular). It introduces the concept of Left_mPoly and Right_mPoly for each edge and vertex, and describes how to insert edges into monotone mountains while preserving the alternating pattern of left‑side and right‑side mountains.

Winding numbers are used to decide fill rules. The winding number of a newly created monotone polygon is computed as the sum of the winding number of its left neighbour and the winding contribution of the separating edge.

Triangulation of monotone polygons

Finally, each monotone polygon (or monotone mountain) is triangulated by iteratively examining triples of consecutive vertices (a, b, c) and using the cross product to determine convexity. Convex triples are emitted as triangles; concave triples are deferred until the polygon is reduced to three vertices.

The article concludes with a brief preview of the next chapter, which will discuss how to extend the triangulation pipeline for stroking, gradient fills, and other visual effects.