Triangular 3,7 millones de polígonos de mapas en 489 ms, más rápido que earcut
Faster than earcut: triangulating 3.7M map polygons in 489 ms
El equipo de un motor de mapas publicó earstrip, un triangulador de polígonos en un solo header de C++ y con build de WebAssembly en npm, bajo licencia ISC como earcut. En C++ es un 14% más rápido que earcut.hpp y en el navegador entre 1,4 y 2,1 veces más veloz que earcut.js. El artículo recorre la optimización paso a paso, desde el recorte de orejas ingenuo hasta técnicas como probar solo los vértices cóncavos y evitar ramas.
Casi la mitad de los polígonos de Masovia, 1,8 millones, tienen cuatro vértices o menos. Un triángulo no necesita ningún corte y un cuadrilátero convexo son dos triángulos, y aun así el código de Delaunay dedica 419 ms a ellos, construyendo cada triangulación desde cero.
- morishuz
increíble. ¡las mejoras de rendimiento se ven impresionantes!
soy el autor de Delaunay32, un triangulador de delaunay restringido con soporte para polígonos y agujeros. usa divide y vencerás en lugar de inserción incremental, así que tengo curiosidad por ver cómo se compararía con el baseline de delaunay aquí.
https://github.com/morishuz/delaunay32
todavía no he hecho benchmarks en tu corpus, y nuestra API actual de polígonos requiere anillos simples con agujeros que no se toquen. ¡gracias por publicar los datasets, parecen útiles para probar y comparar!
- amelius
Deberían mencionar a la madre de todos los trianguladores:
- mistercow
Durante mucho tiempo me he preguntado por qué el ear clipping + optimizaciones ha ganado en triangulación frente a cosas como el método trapezoidal de Seidel, que tiene una complejidad temporal O(nlog*n) y maneja agujeros de forma natural. Sé que la big-O no lo es todo, pero eso es esencialmente lineal versus cuadrático, y parece que nos importa triangular polígonos cada vez más complejos con el tiempo.
¿Es solo una cuestión de calidad de los triángulos? ¿Seidel lleva a demasiados slivers difíciles de manejar?
- mourner
Hola Evgen, aquí el autor de Earcut — ¡gracias por el artículo y por una librería realmente genial! Tengo que ver si hay algún truco que pueda tomar prestado para la versión JS de Earcut. :)
Una cosa a tener en cuenta es que deliberadamente tuve que rechazar algunas de las optimizaciones potenciales para mantener la librería pequeña, de modo que el tamaño del bundle no se dispare — para la mayoría de las aplicaciones prácticas (por ejemplo, Mapbox GL JS), ya es suficientemente rápida (y 4.1k min/gz). Tengo curiosidad por saber cuánto mide la build WASM de Earstrip.
En el lado de C++, Mapbox ahora usa un enfoque híbrido en el que los polígonos pequeños se procesan con earcut.hpp, mientras que los polígonos grandes y complejos cambian a un algoritmo diferente basado en descomposición monótona, porque aunque tiene constantes más altas en la complejidad algorítmica, escala mucho mejor con el tamaño de la entrada.
- stymaar
Veo que el resultado contiene muchos triángulos muy largos y muy delgados. ¿No son esos generalmente el peor caso para el rasterizador de la GPU?