Lunes, 16 de noviembre de 2026
Portada de las 21:50
Todos los periódicos y la radio, en unoEscrito por IA a partir de Hacker News · Cómo se hace
Hacker News
Programación · globus.software

Más rápido que earcut: triangular 3,7 millones de polígonos de mapa en 489 ms

Los autores de un motor de mapas han publicado earstrip, una librería de triangulación por ear clipping, en un único header de C++ y con build en WebAssembly. Según sus pruebas es un 14 % más rápida que earcut.hpp y entre 1,4 y 2,1 veces más que earcut.js.

Foto: vía globus.software

Leer el artículo aquíArtículo original (globus.software) 40 comentarios en Hacker News

Escucha la noticia3 min

Globus ha publicado como librería el triangulador de polígonos de su motor de mapas. Se llama earstrip, tiene licencia ISC (la misma que earcut), es un único header de C++ y cuenta con una build en WebAssembly en npm que acepta los mismos argumentos que earcut. El artículo explica cómo llegaron a ese resultado, y para ello reconstruyeron el algoritmo idea a idea, con un commit por idea y cronometrando cada uno sobre los mismos polígonos.

El punto de partida es el nivel de zoom 13 de su mapa offline del voivodato de Mazovia, con 3.740.425 polígonos. El triangulador anterior, un Delaunay con restricciones, tardaba 2,93 segundos en un núcleo de un M4 Pro. Los autores argumentan que, para un relleno plano en GPU, la calidad de los triángulos que da Delaunay no importa, y que casi la mitad de los polígonos (1,8 millones) tiene cuatro vértices o menos, justo donde Delaunay malgasta tiempo (419 ms).

El artículo repasa el ear clipping: una «oreja» es una esquina convexa cuyo triángulo no contiene otra parte del polígono, y cortarla deja un polígono con un vértice menos. Para los huecos (11.345 polígonos de Mazovia los tienen) se usa el método de Eberly: se une cada hueco al anillo exterior con un puente, y se tratan aparte los casos propios de datos de mapa, como vértices sobre líneas de la rejilla o huecos que tocan el exterior en un punto.

La versión ingenua del clipper tarda 1,12 s, 2,6 veces menos que Delaunay, pero es más lenta en los 1.123 polígonos más grandes (199 ms frente a 90 ms), porque el coste crece con el cuadrado del tamaño. La primera mejora consiste en comprobar solo los vértices cóncavos («dents»), ya que si algo cae dentro del triángulo, uno de ellos también lo hace; eso baja a 882 ms. Las mejoras siguientes (atajo para convexos, tiras en zigzag, buckets, código sin ramas y aciertos marcados) llevan el total hasta 489 ms.

En Hacker News

«Faster than earcut: triangulating 3.7M map polygons in 489 ms» · puesto 27 · 212 puntos · enviado por molind

Lo que dicen los comentarios

El autor de earcut, mourner, aparece para felicitar y explica que rechazó optimizaciones para no inflar el bundle (4,1 kB min/gz) y que Mapbox usa ahora un enfoque híbrido: earcut.hpp para polígonos pequeños y descomposición en monótonos para los grandes, que escala mejor. Se discute por qué no se usa Seidel (constantes altas y poca robustez con datos reales) y se proponen otros triangulizadores, como Triangle o Delaunay32, con una comparativa de números. Otra rama pregunta si los triángulos largos y finos perjudican a la GPU: un comentarista responde que depende del caso y que aquí, con polígonos pequeños, sumar vértices costaría más. También se especula sobre cuánto del texto y de las optimizaciones viene de un LLM.

  • Soy el autor de earcut. Rechacé a propósito algunas optimizaciones para que la librería fuera pequeña; para la mayoría de usos ya es suficientemente rápida. Mapbox usa ahora earcut.hpp para polígonos pequeños y monotone decomposition para los grandes, que escala mucho mejor.
    — mourner, leer el comentario
  • Mirad el recuento de vértices cóncavos sin ramas: es lo que nos permitió superar a earcut y buena parte de por qué el build wasm es tan rápido. El módulo pesa 27 KB comprimido con gzip.
    — molind, leer el comentario
  • Seidel tiene constantes muy altas y una implementación compleja; lo intenté y lo dejé antes de llegar a earcut, porque era más lento y menos robusto con datos de mapas típicos.
    — mourner, leer el comentario
  • Depende del caso de uso. Triángulos más equilibrados solo aumentarían el número de vértices, con más memoria en la GPU y más trabajo en el pipeline de vértices; y al ser polígonos pequeños no se gana nada descartándolos antes.
    — dan00, leer el comentario
  • Tengo la impresión de que el texto es muy de Claude. Mi experiencia es que Claude Opus 5 y 5.5 implementan muy bien optimizaciones y sugieren enfoques, pero no identifican por sí solos que el tiempo de ejecución sea un problema.
    — entrope, leer el comentario

Pregunta sobre esta noticia

Respuestas automáticas a partir de las noticias de El Autómata, sus fuentes y la radio. Pueden contener errores: comprueba los enlaces.

Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.