earstrip: la librería que triangula 3.7M polígonos en 489 ms

Globus libera earstrip, el triangulador que corta 3,7 millones de polígonos en 489 ms

489 milisegundos para cortar 3,74 millones de polígonos de mapa en un solo núcleo. Ese es el número que reporta Globus Software al publicar earstrip, el triangulador de su motor de mapas, bajo la licencia ISC (la misma que usa earcut), con un solo header de C++ y un build de WebAssembly en npm que acepta los mismos argumentos que earcut.

El dato le importa a cualquier equipo que construya producto sobre mapas, y por una razón poco vistosa: la GPU solo rellena triángulos. Edificios, parques, estacionamientos, la franja de césped entre dos vías del tranvía llegan como polígonos. Cada contorno hay que partirlo antes de que se pinte el primer píxel.

¿Por qué un triangulador define el rendimiento de tu mapa?

Un bloque de Śródmieście, en Varsovia, que Globus usa como caso de prueba, contiene 331 polígonos con 5.151 vértices que se convierten en 4.514 triángulos. El zoom 13 de su mapa offline de Mazovia, la región alrededor de Varsovia, tiene 3.740.425 polígonos.

Ahí aparece el problema de escala. El motor resolvía esos 3,74 millones de polígonos con un triangulador de Delaunay con restricciones que tardaba 2,93 segundos en un solo núcleo de un M4 Pro. Al reemplazarlo por ear clipping, el mismo trabajo bajó a 489 ms: 6,0 veces menos. En la comparación directa contra earcut.hpp 3.2.4, la versión C++ de la librería que corre detrás de MapLibre y Mapbox GL, earstrip es 14% más rápida.

De Delaunay a ear clipping: el cambio de algoritmo

Una triangulación es Delaunay cuando ningún punto cae dentro del círculo que pasa por las tres esquinas de cualquier triángulo. El apellido con restricciones significa que las aristas del propio polígono deben seguir siendo aristas de la triangulación, aunque la regla del círculo quiera girarlas. El motor insertaba los vértices uno por uno, caminaba los triángulos ya construidos, partía el que contenía el punto y corregía las aristas a su alrededor.

Es un método pensado para triángulos bien formados, algo que importa cuando interpolas valores sobre ellos o corres una simulación. Un relleno plano no lo necesita: una GPU pinta igual de bien un triángulo aguja que uno gordo.

El costo de esa precisión innecesaria se ve en los datos de Mazovia: 1,8 millones de polígonos tienen cuatro vértices o menos. Un triángulo no necesita ningún corte y un cuadrilátero convexo son dos triángulos, pero el código de Delaunay gastaba 419 ms en ellos, construyendo cada triangulación desde cero.

El ear clipping ataca justo eso. Un ear (oreja) es un vértice convexo cuyo triángulo no contiene ninguna otra parte del polígono. En 1975, Gary Meisters demostró que todo polígono simple de más de tres vértices tiene al menos dos orejas que no se solapan, así que siempre hay una para cortar y un polígono de n vértices se desarma en n − 2 triángulos.

La primera versión completa, con los agujeros ya puenteados, tardaba 1,12 segundos: 2,6 veces más rápida que Delaunay. Pero el promedio esconde el problema. Los 1.123 polígonos más grandes, con 257 vértices o más, tardaban 199 ms en recortarse contra 90 ms con Delaunay. Cada test de oreja recorre cientos de vértices y un polígono necesita cientos de tests: el costo crece con el cuadrado de su tamaño.

Las optimizaciones: de 1,12 segundos a 489 milisegundos

Globus reconstruyó el recortador idea por idea, un commit por idea, cronometrando cada uno sobre los mismos 3,7 millones de polígonos. De ahí salen los números:

• Testear solo los dents (−237 ms). Únicamente un vértice reflexivo puede bloquear una oreja, así que basta revisar los dents en vez de todo el contorno. Los 28,1 millones de tests pasaron a mirar 185 millones de puntos en lugar de 353 millones. El efecto secundario: los polígonos pequeños empeoraron, de 34 a 54 ms, porque clasificar las esquinas cuesta más que el recorrido que ahorra.
• Atajo para polígonos convexos (−2 ms). Un anillo sin dents es convexo y todas sus esquinas son orejas. La comprobación barata no es que todo gire a la izquierda (una estrella también lo hace), sino contar cuántas veces cambia la dirección en x: exactamente dos en un anillo convexo. Elimina 4,4 millones de los 28,1 millones de tests, pero son los más baratos y apenas mueve el total.
• Escribir triangle strips (−118 ms). En vez de tres índices por triángulo, una tira donde cada índice nuevo agrega un triángulo con los dos anteriores. Los 21,5 millones de triángulos pasaron de 64,5 a 35,8 millones de índices, y los polígonos más grandes bajaron de 146 a 103 ms.
• Buckets para los dents (−65 ms). Con más de 32 dents, el motor los ordena en cubetas a lo largo del lado mayor de su bounding box, unos dos dents por cubeta, y cada test mira solo las cubetas que su triángulo abarca. Los puntos escaneados cayeron de 181 a 101 millones y los polígonos de 257 vértices o más, de 103 a 57 ms.
• Contar sin ramas (−178 ms). La mayoría de los tests terminan en un sí, así que la salida temprana no compra nada y las comparaciones se pagan en predicción de ramas. El motor hace primero una pasada sin ramas que solo cuenta dents dentro del triángulo, y corre el test exacto únicamente cuando el conteo no es cero. Los tamaños medios, de 33 a 256 vértices, bajaron de 327 a 216 ms.
• Testear solo los dents marcados (−30 ms). La primera pasada deja una máscara de bits y el test exacto revisa únicamente esos dents. Los puntos leídos caen de 128 a 120 millones.

El navegador es otro campo de juego

Ese es el punto que un equipo de producto no debería pasar por alto. Aunque earstrip y earcut compiten casi de igual a igual en C++ nativo (489 contra 557 ms), la brecha se abre al compilar a WebAssembly. En los 3,74 millones de polígonos del zoom 13, con el loop dentro del módulo:

Compilado a WebAssembly y corriendo en V8, earstrip pierde un 23% de rendimiento y earcut.hpp pierde un 67%. Globus descarta que sea el asignador de memoria: los builds con mimalloc y emmalloc dan el mismo tiempo. El resultado incómodo es que, en V8, earcut.hpp dentro de WebAssembly queda apenas un 19% más rápido que el earcut.js plano, y un 10% cuando cada polígono es una llamada separada desde JavaScript.

Para una página web, la fila que importa es la del paquete: 1,4 veces más rápido que earcut.js en V8 y 1,6 veces en JavaScriptCore con la API que reemplaza a earcut. Con llamadas directas, donde los polígonos entran a la memoria del módulo y vuelven como un solo buffer de índices para WebGL 2 o WebGPU, la ventaja sube a 1,7 y 2,1 veces. La mitad de lo que se pierde frente al loop interno se va en copiar coordenadas y convertir las tiras en listas.

Cuando la geometría no coopera

Dos casos rompen la elegancia del método. Los agujeros (hay 11.345 polígonos con agujeros en Mazovia, entre patios interiores y claros de bosque) se resuelven cortando el anillo interior y cosiéndolo al exterior con un puente que se recorre en los dos sentidos. Ese puente no puede cruzar nada, y Globus usa el método que David Eberly documentó para hallarlo.

El segundo caso es peor: los datos de mapa se redondean a una grilla, y el redondeo puede romper un polígono simple. La estación Warszawa Śródmieście, a menos de un kilómetro de los bloques del ejemplo, tiene 154 vértices; en la grilla que usan los archivos de mapa (pasos de 18 cm) 31 vértices se fusionan con un vecino y el contorno sobrevive. Con grillas más agresivas, casi la mitad se fusiona y el recortador sigue funcionando. Pero hay una configuración en la que el contorno se toca a sí mismo y no deja ninguna oreja.

La salida es pragmática: el recortador hace una segunda pasada descartando las esquinas sin área y, si tampoco encuentra orejas, delega ese polígono al código de Delaunay, que sigue existiendo dentro de la librería. En los datos de Mazovia terminan ahí 76 polígonos. Globus ya atacó el problema en la raíz: su generador de mapas ahora redondea cada polígono a la grilla final con el snap rounding de GEOS y verifica que el ear clipping pueda cortarlo. En una compilación nueva del mapa de Mazovia, esa reparación tocó 273 polígonos y el recortador pudo cortarlos todos.

Delaunay conserva una segunda tarea. Cada agujero necesita su propio puente y hallarlo recorre todo el contorno, así que un polígono con miles de agujeros paga miles de recorridos: en el mapa mundial hay uno con 11.675 agujeros, donde ear clipping tarda 606 ms y Delaunay 17 ms. Por eso el motor manda a Delaunay todo polígono con 128 agujeros o más; en los datos de Mazovia eso son dos polígonos.

En los 56.472 polígonos de los tiles del mapa mundial, earstrip tarda 459 ms y earcut.hpp 2.892 ms. Y en los polígonos del zoom 13 que las orejas no pueden cortar con exactitud, los triángulos de earcut difieren de un relleno even-odd de los anillos en un 31% de los píxeles en promedio, mientras que los de earstrip difieren en un 0,15%.

¿Qué significa esto para tu startup?

La lección central del post no es que uses earstrip, sino cómo se optimiza un hot path cuando ya no queda grasa.

Mide por tramos, no por promedio. El total de earstrip bajó de 1,12 segundos a 489 ms, pero casi ninguna optimización fue uniforme. La lista de dents aceleró los polígonos grandes y frenó los pequeños (de 34 a 54 ms); el atajo convexo devolvió parte de eso y ayudó sobre todo en el paso siguiente. Si tu benchmark es un solo número agregado, vas a elegir mal qué optimizar.

Presupuesta el fallback, no lo escondas. earstrip mantiene Delaunay adentro y expone run() en C++ y lastStatus() en JavaScript para saber por qué camino salió cada polígono. Diseñar una ruta rápida que delega en una ruta correcta, y poder auditar cuántos casos caen en ella, es más útil que perseguir el 100% del caso ideal.

Arregla el dato en la ingesta. Sanear la geometría una vez, al generar el mapa (redondeo con snap rounding y una verificación de que el polígono se puede cortar), resolvió 273 casos de una sola vez. Endurecer el algoritmo para tolerar datos sucios suele salir más caro que limpiar los datos.

Mide en el runtime real, no en el de tu máquina. El mismo código que gana por 14% en C++ queda 23% abajo al pasar a WebAssembly, y el competidor cae 67%. Si tu producto corre en el navegador, el benchmark nativo te puede estar mintiendo.

Vale la pena notar el formato de la liberación: licencia ISC, un solo header de C++ y paquete en npm. Es lo que hace viable que un equipo pequeño en Latinoamérica o España adopte la librería y la cronometre en su propio hardware, sin fricción de licencias ni de build.

No se encontraron datos adicionales verificables sobre esta librería fuera de la publicación original de Globus.

Fuentes

• Faster than earcut: triangulating 3.7M map polygons in 489 ms (fuente original)

Artículos relacionados:

Bisecto: geometría computacional que desafía la percepción Plan ‘Se busca dueño’: Chile subastará 234 inmuebles por US$73M Claude Opus 4.8 y Lean 4 verifican interseccion de poligonos Ryanair y sus escaleras: 489 caídas que cuestan menos que ganar