Decomposes a simple polygon into convex sub-polygons using Bayazit's fast
approximate algorithm. Fast (~O(n²)) but may use more pieces than the
minimum; may introduce new (Steiner) vertices. Input winding is normalised
internally, so either winding is accepted.
Implemented iteratively with an explicit worklist of sub-polygons rather than
recursion.
Parameters
vertices: number[]
polygon vertices as a flat array [x0, y0, x1, y1, ...]
n: number
number of vertices to read from vertices
Returns number[][]
an array of convex sub-polygons, each a flat [x0, y0, ...] array (CCW)
Decomposes a simple polygon into convex sub-polygons using Bayazit's fast approximate algorithm. Fast (~O(n²)) but may use more pieces than the minimum; may introduce new (Steiner) vertices. Input winding is normalised internally, so either winding is accepted.
Implemented iteratively with an explicit worklist of sub-polygons rather than recursion.