Cutting map polygons into triangles
A GPU fills triangles and nothing else. A map, on the other hand, is mostly polygons: buildings, parks, parking lots, the strip of grass between two tram tracks. Here are a few blocks of Śródmieście in Warsaw the way our renderer reads them from a map file, :
Before any of this gets a fill, every outline has to be cut into . Hover over a polygon, or tap it, to see what it turns into. These blocks hold 331 polygons with 5,151 vertices, and they become 4,514 triangles.
Zoom level 13 of our offline map of the Masovian Voivodeship, the region around Warsaw, has 3,740,425 polygons. On one core of an M4 Pro, the constrained Delaunay triangulator in our engine needs 3.76 seconds to cut all of them. This October I replaced it with ear clipping. To write this post I rebuilt the ear clipper one idea at a time and timed every step on those same 3.7 million polygons, so each section below ends with a number.