Hemos publicado earstrip, el triangulador de polígonos de nuestro motor de mapas, como una pequeña biblioteca de código abierto bajo la licencia ISC, la misma licencia que usa earcut. Consiste en un único encabezado de C++ y una compilación de WebAssembly publicada en npm que acepta los mismos argumentos que earcut. En C++ funciona un 14 % más rápido que earcut.hpp, y en el navegador funciona entre 1,4 y 2,1 veces más rápido que earcut.js.
Una GPU solo puede rellenar triángulos, mientras que un mapa está compuesto en su mayor parte por polígonos: edificios, parques, aparcamientos y las franjas de hierba entre las vías del tranvía. Antes de que cualquier polígono pueda rellenarse, su contorno debe dividirse en triángulos. Nuestro mapa offline de la provincia de Masovia, la región alrededor de Varsovia, tiene 3.740.425 polígonos en el nivel de zoom 13. En un núcleo de un M4 Pro, el triangulador de Delaunay restringido de nuestro motor necesitó 2,93 segundos para procesarlos todos.
En octubre lo sustituimos por recorte de orejas. La triangulación de Delaunay evita los triángulos alargados y es útil para la interpolación y la simulación, pero un relleno plano no necesita esa calidad, y la mayor parte del trabajo se empleaba en formas sencillas. Casi la mitad de los polígonos de Masovia, 1,8 millones, tienen cuatro vértices o menos, pero el código de Delaunay gastaba 419 ms en construir sus triangulaciones desde cero. El recorte de orejas elimina una esquina cada vez, y todo polígono simple con más de tres vértices tiene al menos dos orejas que no se superponen, por lo que siempre hay otro corte que hacer.
Para documentar el trabajo, reconstruimos el recortador de orejas con una idea por commit y medimos cada paso con los mismos 3,7 millones de polígonos. La versión final procesa el conjunto completo en 489 ms, que es la cifra del titular.
Fuente: Hacker News · Resumido por HeadlinesBriefing