Earcut
Ear-clipping polygon triangulator — a Kotlin port of mapbox/earcut (ISC licence). It is the triangulator MVT renderers (Mapbox GL, MapLibre, deck.gl) use for polygon fills: far cheaper than a GLU-style sweep-line tessellator because it builds only a small doubly-linked node list (no half-edge mesh), and it stays robust on real-world rings (holes, near-collinear / self-touching edges) via its hole-bridging and cureLocalIntersections / splitEarcut fallbacks.
Struct-of-arrays arena. The reference port allocates one Node object per polygon vertex (plus two per hole bridge / split) — millions of short-lived objects across a pan session, the dominant GC source. This implementation stores node state in parallel primitive arrays indexed by an Int node id (NULL = -1 for the absent link), reused across triangulate calls on the same instance. The algorithm and the emitted triangles are identical to the object port — only the memory layout differs. Hold one instance per assembler (it is not thread-safe; the arena is shared mutable state) and reuse it across all of a tile's features; per-tile allocation drops from O(vertices) to O(1).
Functions
Free the arena's backing arrays after a batch of triangulations, keeping the instance reusable. Next triangulate regrows on demand — call once an assembler is done to avoid retaining the largest feature's node arrays for the tile's whole lifetime.
Triangulate a polygon. data holds flat vertex coordinates, dim components per vertex (data[i*dim], data[i*dim+1], …). holeIndices gives the vertex index where each hole ring starts; the outer ring is the vertices before the first hole. Triangle vertex indices are appended to out in groups of three (each index is a vertex ordinal i, i.e. into the per-vertex data[i*dim] layout). Rings need not be a particular winding — earcut normalises the outer ring CCW and holes CW. out is cleared first and returned.