earstrip : triangulation 3,7M polygones en 489 ms
Original : Faster than earcut: triangulating 3.7M map polygons in 489 ms
Pourquoi c'est important
Rend la triangulation temps réel viable côté navigateur pour les cartes vectorielles.
Globus Software publie earstrip, une bibliothèque C++ ISC open source qui triangule 3,7 millions de polygones cartographiques en 489 ms — 14 % plus rapide qu'earcut.hpp en C++, jusqu'à 2,1 fois en WebAssembly.
Les moteurs de rendu de cartes reposent sur la triangulation : un GPU ne sait remplir que des triangles, jamais des polygones. Pour la carte hors ligne de la Voïvodie de Mazovie (région de Varsovie), Globus Software devait découper 3 740 425 polygones avant tout affichage. Leur ancien triangulateur de Delaunay contrainte mettait 2,93 secondes sur un cœur M4 Pro. En octobre 2026, le CEO Evgen Bodunov l'a remplacé par un algorithme de « ear clipping » — la technique qui retire successivement les oreilles d'un polygone, ces sommets coupables d'aucun chevauchement. Résultat : 489 ms pour l'ensemble du jeu de données. La bibliothèque résultante, earstrip, tient en un seul header C++ et propose un build WebAssembly sur npm avec la même API qu'earcut. Le gain vient notamment d'une observation simple : près de la moitié des polygones (1,8 million) ont quatre sommets ou moins. L'ancien code Delaunay y consacrait quand même 419 ms, reconstruisant chaque triangulation from scratch. Le ear clipping traite ces cas triviaux sans overhead. Le code est publié sous licence ISC, identique à celle d'earcut.