In map rendering, complex shapes like buildings, parks, and roads are stored as polygons—closed outlines of vertices. However, Graphics Processing Units (GPUs) are designed to fill triangles, not arbitrary polygons. To bridge this gap, every polygon must be 'triangulated' or cut into a series of triangles. While several algorithms exist for this task, the developers of the GLOBUS map engine found that their previous method, a constrained Delaunay triangulator, was inefficient for large-scale data. Specifically, processing 3.7 million polygons from a region of Warsaw took nearly three seconds on a single core, a bottleneck they sought to eliminate by switching to an 'ear-clipping' method.

Ear-clipping works by identifying an 'ear'—a convex corner of a polygon where the line between its two neighbors doesn't intersect any other part of the shape. By repeatedly 'cutting off' these ears, a polygon eventually collapses into a set of triangles. The GLOBUS team developed 'earstrip' to refine this process. They implemented several optimizations to reduce the computational cost of the 'is-ear' test, which is the most frequent operation in the algorithm. Key improvements included identifying 'dents' (reflex vertices) to narrow the search area, skipping tests for already-convex polygons, and using a 'bucket' system to sort dents spatially. These refinements allowed them to process the same 3.7 million polygons in just 489 milliseconds, a significant speedup over the Delaunay method.

Beyond raw speed, the team optimized how the resulting triangles are stored to improve GPU efficiency. By identifying convex rings within the polygons, they could generate 'triangle strips'—a method where the GPU reuses two vertices from the previous triangle to form the next one. This reduced the total number of indices required for the 21.5 million triangles produced by their test set. While the ear-clipping method is faster for most map polygons, the team noted a trade-off: for very large, complex polygons (over 257 vertices), the Delaunay method remains slightly faster because ear-clipping's complexity grows with the square of the polygon's size. Despite this, 'earstrip' provides a high-performance, license-friendly alternative for general map rendering tasks.