Présentation

Le moteur cartographique de Globus Software a publié earstrip, une bibliothèque de triangulation de polygones sous licence ISC. Elle se compose d’un seul en‑tête C++ et d’une version WebAssembly distribuée via npm, compatible avec l’API d’earcut. En C++, earstrip est 14 % plus rapide que earcut.hpp, et dans le navigateur il gagne entre 1,4 et 2,1 fois sur earcut.js.

Méthode de triangulation

Le code initial utilisait un triangulateur Delaunay contraint. Cette approche insère chaque sommet, parcourt les triangles existants, puis effectue des retournements d’arêtes jusqu’à ce que la règle du cercle de Delaunay soit satisfaite. Bien que mathématiquement robuste, elle consomme 2,93 s pour 3 740 425 polygones (M4 Pro, un cœur) et 419 ms uniquement sur les 1,8 M polygones à quatre sommets ou moins, où le travail est superflu.

Earstrip adopte l’algorithme d’ear clipping. Un « oreille » est un coin convexe a‑b‑c dont le triangle ne contient aucun autre sommet du contour. Le processus supprime itérativement ces oreilles jusqu’à obtenir n‑2 triangles pour un polygone à n sommets. Le texte fournit le test d’oreille suivant :

static double cross(double ax, double ay, double bx,
    double by, double cx, double cy)
{
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

bool isEar(uint32_t v) const
{
    const Node &b = _nodes[v];
    const Node &a = _nodes[b.prev], &c = _nodes[b.next];
    if (cross(a, b, c) <= 0)
        return false;
    for (uint32_t w = c.next; w != b.prev; w = _nodes[w].next) {
        const Node &p = _nodes[w];
        if (cross(a.x, a.y, b.x, b.y, p.x, p.y) < 0 ||
            cross(b.x, b.y, c.x, c.y, p.x, p.y) < 0 ||
            cross(c.x, c.y, a.x, a.y, p.x, p.y) < 0)
            continue;
        if (!samePos(p, a) && !samePos(p, b) && !samePos(p, c))
            return false;
    }
    return true;
}

Cette implémentation évite les calculs géométriques lourds du Delaunay et se montre adaptée aux cartes où la qualité des triangles n’influence pas le rendu GPU.

Gestion des trous

Sur le jeu de données masovien, 11 345 polygones comportent des trous. Earstrip les traite en créant un « pont » entre le sommet le plus à droite du trou (m) et un sommet du contour extérieur (P) trouvé par lancer d’un rayon horizontal. Le pont doit rester hors de toute autre géométrie ; la méthode de David Eberly garantit cette propriété en vérifiant que le triangle m‑I‑P ne contient aucun autre sommet. Des cas particuliers liés aux coordonnées entières (rayons alignés sur la grille) et aux vertices partagés sont explicitement corrigés.

Performances et comparaison

Après une série d’optimisations (réduction des allocations, itérations en‑place, élimination des tests redondants), la version finale d’earstrip triangule les 3,7 M polygones en 489 ms sur le même cœur M4 Pro, soit un gain de ≈5,7× par rapport au Delaunay initial et ≈2,3× sur la version naïve ear‑clipper (1,12 s). Le facteur de vitesse varie entre 1,4 et 2,1 selon le navigateur, confirmant la portabilité du code C++ vers WebAssembly sans perte de performance.

Ces résultats démontrent que, pour les applications cartographiques où le remplissage GPU ne dépend pas de la forme des triangles, l’ear clipping optimisé constitue une solution nettement plus efficace que les algorithmes Delaunay contraints.