Toutes les cartes (Lines ou Points), les images (PNG ou SVG) et les fichiers vectoriels (GeoJSON ou DXF) de TopoLines, qu’ils viennent de la grille mondiale à 30 m ou des modèles lidar nationaux à 5 m, sont produits par le même moteur. Jusqu’à ce mois-ci, il n’avait pas de nom. On l’appelait « le traceur ». Peu de gens le remettaient en question : il fonctionnait suffisamment bien. Nous, si.
Il s’appelle désormais Karst Engine. Cet article explique ce que nous avons changé, comment nous l’avons vérifié, ce qu’il vaut face aux outils de référence du domaine, et ce qu’il fait encore mal.
Pourquoi nous l’avons changé
Une courbe de niveau est une mesure : chaque sommet affirme que le sol, à cet endroit, se trouve à cette altitude exacte. Ces courbes servent en design, sur des affiches et des plaques découpées au laser, et en SIG, dans QGIS, AutoCAD ou Rhino. Dans les deux cas, on leur fait confiance. En novembre, nous avons donc arrêté d’ajouter des fonctionnalités et relu le traceur ligne par ligne, pour trouver les endroits où ses courbes disent quelque chose que la donnée ne dit pas.
Nous avons trouvé 8 défauts, dont 4 importants.
La simplification dépendait de la direction. La tolérance en mètres était convertie en degrés de longitude, puis appliquée aux deux axes. À 45° N, une courbe pouvait donc bouger 1,41 fois plus que prévu dans le sens nord–sud ; à 60° N, deux fois plus. En Alaska, une tolérance de 15 m déplaçait des courbes jusqu’à 30,6 m.
Des courbes qui se croisent. Chaque courbe était simplifiée seule, si bien qu’en pente raide un raccourci sur une courbe pouvait couper sa voisine. Sur les zones lidar les plus raides de notre jeu de test, jusqu’à 18 paires de courbes se croisaient. Deux courbes qui se croisent prétendent que le sol a deux altitudes au même point.
Les terres sous le niveau de la mer devenaient de la mer. Toute altitude inférieure ou égale à 0 m était traitée comme de la mer et écartée. Dans la Vallée de la Mort, cela représentait 51,9 % de la zone de Badwater Basin : les courbes de −25, −50 et −75 m n’étaient jamais tracées.
Une donnée lissée deux fois. La grille par défaut, GEDTM30, est déjà filtrée par ses auteurs avant d’être diffusée (Ho et al., 2025). Notre flou fixe la lissait une seconde fois et abaissait ses crêtes de 15 à 31 m en moyenne.
Aucun de ces défauts ne se voit sur une belle carte. Tous se voient dans une mesure.
Comment nous l’avons amélioré
Avant de toucher une seule ligne du moteur, nous avons construit l’instrument pour le juger.
Des terrains dont on connaît la réponse. Une colline gaussienne, un col, une crête, une vallée, un plan incliné à plusieurs latitudes, une pente raide bruitée et un terrain sous zéro. Sur chacun, les courbes exactes sont connues d’avance, donc l’erreur se mesure au millimètre. Ces tests tournent dans notre intégration continue à chaque modification.
Des tests qui échouent pour chaque défaut connu. Chaque défaut connu est devenu un test censé échouer, qui lève une alerte s’il passe un jour par accident. Une phase de travail était terminée quand ses tests passaient au vert.
6 zones réelles, 2 continents, 3 sources de données. Les Calanques (falaises sur la mer près de Marseille), la Barre des Écrins (un sommet à 4 000 m et son glacier), la Camargue (étangs au niveau de la mer), Badwater Basin dans la Vallée de la Mort (−85 m), le Zuidplaspolder (terres gagnées sur la mer sous le niveau de la mer, Pays-Bas) et Girdwood, en Alaska (60,96° N). Chaque zone a été tracée depuis GEDTM30 et, quand il existe, depuis le lidar à 5 m de l’IGN (RGE ALTI) ou de l’USGS (3DEP). Chacune a été mesurée de la même façon avant et après chaque phase : courbes qui se croisent, auto-intersections, plus grand déplacement sur chaque axe, erreur verticale, nombre de sommets, temps et mémoire.
Le travail s’est fait en 4 phases, chacune sur sa propre branche, chacune comparée avant et après sur les mêmes zones.
Ce que Karst fait différemment
Une tolérance en mètres au sol, la même dans toutes les directions. Toutes les distances sont calculées sur une échelle métrique locale, à la latitude de la zone. À Girdwood, Medium déplace désormais une courbe de 15,0 m au plus, comme prévu. Cette borne est garantie par l’algorithme de Douglas–Peucker (Douglas & Peucker, 1973), et le benchmark l’a mesurée à toutes les latitudes de 36° N à 61° N.
Toutes les courbes simplifiées d’un seul coup. Toutes les courbes d’une zone, ainsi que le trait de côte, sont passées comme une seule géométrie au simplificateur à préservation de topologie de GEOS. Un raccourci est refusé s’il couperait n’importe quelle autre courbe de l’ensemble, pas seulement la sienne. C’est la contrainte de Saalfeld (1999), appliquée à toute la carte. Sur nos 6 zones, à chaque cran : 0 croisement et 0 auto-intersection, pour 0 à 3 % de points en plus.
Un lissage adapté à la donnée. La largeur du lissage est fixée en mètres au sol, la même dans les deux directions, et suit la taille de cellule de la grille réellement servie. GEDTM30 est lissé d’une fraction de cellule ; le lidar brut, davantage. Sur GEDTM30, les crêtes perdent maintenant 1,0 à 2,6 m en moyenne (15 à 31 m avant). Girdwood garde 37 de ses 75 petites cuvettes (3 avant). Au sommet de la Barre des Écrins, le traceur coûte désormais 1,4 m, alors que GEDTM30 se situe lui-même 75 m sous le lidar à cet endroit. La donnée, et non le moteur, redevient la principale source d’erreur. Comme il se doit.
Sous le niveau de la mer, c’est de la terre. La mer est maintenant identifiée d’après ce qu’elle est réellement dans la donnée, et tout le reste est tracé. Badwater Basin a ses courbes jusqu’à −75 m ; le polder, les siennes jusqu’à −10 m.
Une simplification guidée. Un nouveau cran Fine · 2 m supprime le zigzag maille par maille du lidar. Sur du lidar à 5 m, il retire 85 à 93 % des points, et aucune courbe ne bouge de plus de 2,0 m. Une grille à 5 m ne contient pas de détail aussi fin : rien de réel n’est perdu. Une mention Recommended indique le cran adapté à chaque zone, d’après la taille de cellule, l’écartement médian entre courbes (Bayer et al., 2023 ; Miller, 2024) et le nombre de points. La longueur minimale Auto fait disparaître la nuée de petites boucles en terrain plat (de 1 294 à 360 sur le polder) et conserve 99 % des courbes ou plus en montagne.
Ce que nous avons appris
Une partie de ce que les mesures ont montré, nous ne l’attendions pas.
La mer n’est pas vide. Nous pensions que la mer arriverait sous forme de cellules manquantes. Dans GEDTM30, chez l’IGN comme chez l’USGS, elle arrive sous la forme d’une surface parfaitement plate à 0,0 m. Une terre sous zéro a du relief ; l’eau n’en a pas. C’est cette différence qui permet maintenant à Karst de trouver la mer.
Un garde-fou ligne par ligne ne garde rien. Activer l’option habituelle de « préservation de la topologie » courbe par courbe n’a supprimé aucun des 123 croisements d’un test synthétique. Une courbe ne peut pas éviter une voisine qu’elle ne voit pas.
C’est en terrain plat que les courbes sont fragiles. Une erreur d’altitude h déplace une courbe latéralement de h / tan θ. Une erreur de 5 m déplace la courbe de 9 m sur une pente de 30°, et de 95 m sur une pente de 3°. La montagne est le cas facile ; dans les plaines, les deltas et les polders, les courbes sont délicates.
Deux méthodes publiées n’ont pas fait mieux que la plus simple. Nous avons implémenté et testé le lissage adaptatif de Kettunen et al. (2017) et le filtre préservant les formes de Lindsay et al. (2019). Aucun n’a fait mieux qu’une gaussienne bien dimensionnée sur nos critères, donc aucun n’a été retenu. Le détail est dans What the tracer does to a contour line (en anglais).
Karst face à GDAL et GRASS
Faire mieux que notre propre version précédente ne prouve pas grand-chose. Nous voulons
savoir où se situe Karst face aux outils auxquels le monde du SIG fait déjà confiance :
gdal_contour de GDAL et r.contour de GRASS GIS. Nous avons donc construit l’Open
Contour Benchmark, et nous l’avons construit pour qu’il soit dur avec nous.
Des règles fixées à l’avance. Le protocole a été écrit et figé avant le premier résultat. Il s’ouvre sur un conflit d’intérêts : nous développons l’un des 3 moteurs mesurés, donc le benchmark est ouvert et reproductible, pas indépendant. Nous avons aussi lu le code source de chaque moteur et écrit 8 prédictions sur leurs différences, avant de mesurer quoi que ce soit.
Une évaluation à l’aveugle. Chaque sortie a reçu un identifiant anonyme. La table reliant les identifiants aux moteurs a été scellée, et son empreinte SHA-256 commitée. Les métriques ont été commitées avant la levée de l’aveugle. Quand GRASS a échoué sur une entrée lors du premier passage, la modification du script a été consignée comme un amendement a posteriori, et l’échec enregistré comme un résultat.
Le passage pilote. 244 sorties, 20 cas : des terrains synthétiques à 30 m et 5 m à l’équateur et à 60° N, et 2 grilles réelles, les Écrins en lidar IGN et le Zuidplaspolder en GEDTM30.
L’extraction. Sur un terrain régulier, Karst trace les mêmes courbes que GDAL et GRASS, à 3,4·10⁻⁵ cellule près. Aucun moteur n’a produit de croisement à l’étape d’extraction. C’était attendu : la base est standard et correcte.
La simplification. C’est là que les moteurs se séparent. Paires de courbes qui se croisent entre niveaux :
| Zone et réglage | GDAL | GRASS GIS | Karst |
|---|---|---|---|
| Écrins, lidar IGN 5 m, tous les 10 m, simplifié à 15 m | 1 765 | 1 650 | 0 |
| Écrins, tous les 10 m, simplifié à 2 m | 95 | 80 | 0 |
| Zuidplaspolder, GEDTM30, tous les 1 m, simplifié à 15 m | 5 079 | pas de sortie | 6 |
Sur les Écrins, Karst reste à 0 à toutes les tolérances, là où la simplification courbe par courbe des deux autres produit des centaines, voire des milliers de croisements.
Sur nos 8 prédictions, 3 se sont vérifiées, 2 en partie, 2 ont échoué, et 1 était une simple mesure. Toutes sont publiées.
Les résultats qui ne sont pas en faveur de TopoLines
Le protocole impose de lister d’abord les résultats défavorables à TopoLines. Les voici.
Zéro croisement est une mesure, pas une loi. Sur le polder néerlandais, tracé tous les 1 m et simplifié à 15 m, 6 paires de courbes se croisent encore (3 dès 6 m). Bien moins que les 5 079 de GDAL, mais pas le 0 que nous avions prédit.
Les valeurs égales divisent les moteurs. Quand des points de la grille tombent exactement sur un niveau de courbe, ils forment une bande, et les moteurs en tracent des bords opposés. Prenons la rangée 0 · 5 · 5 · 5 · 10 au niveau 5 : GDAL trace la courbe entre 0 et 5, Karst entre 5 et 10. Sur des grilles stockées par paliers ronds, comme les décimètres de GEDTM30 sur un polder plat, l’écart peut atteindre un kilomètre. Nous avions prédit que GDAL serait l’exception. C’était nous.
Karst n’est pas le plus rapide. GDAL extrait les mêmes courbes bien plus vite et avec moins de mémoire : 0,56 s et 70 Mo, contre 3,99 s et 384 Mo pour Karst, sur les Écrins tous les 10 m. GRASS a mis 66 s. Karst tourne en Python et paie environ 0,4 s de démarrage à chaque appel : imperceptible sur une carte, mesurable dans un benchmark.
Éviter les croisements coûte parfois des points. Dans 17 groupes sur 60, Karst a gardé plus de sommets que les deux autres moteurs, jusqu’à 51 % de plus sur un relief dense à une tolérance de 15 m. Nous l’avions prédit pour tous les groupes.
Nous aurions pu les passer sous silence. Mais un benchmark qui ne montre que des victoires est une publicité, et une publicité ne vaut rien pour qui doit faire confiance aux courbes.
La suite
Karst est le moteur qui trace aujourd’hui chaque carte TopoLines. C’est aussi la première version d’un moteur que nous savons mesurer, et c’est ce qui fixe le travail à venir.
Deux nouveaux chantiers, issus du benchmark : les bandes de valeurs égales, et les derniers croisements sur les grilles plates et quantifiées.
Le benchmark va s’étendre. La prochaine version du protocole teste la mer et le trait de côte, les données manquantes et les hautes latitudes. Le dépôt sera publié avec ses entrées, ses sorties et ses scripts, pour que chacun puisse le relancer.
À plus long terme : filtrer les courbes selon la proéminence du relief qu’elles décrivent, indiquer le degré de confiance de chaque courbe à partir de l’incertitude de la donnée, et une meilleure règle aux cols.
Il reste des terrains sur lesquels nous n’avons pas testé Karst : les dunes, les volcans, les centres-villes denses, les calottes glaciaires, tout ce qui est au-delà de 61° N. Et oui, le karst. Le moteur porte le nom du seul terrain sur lequel il n’a pas été testé : ce sera notre prochaine zone.
Pour aller plus loin
- How contours are traced : la méthode, étape par étape, avec les chiffres du benchmark et les articles scientifiques sur lesquels elle s’appuie (en anglais).
- What the tracer does to a contour line : l’avant/après complet, zone par zone (en anglais).
Ou tracez une zone, tout simplement. Chaque courbe que vous exportez, en PNG, SVG, GeoJSON ou DXF, sort désormais de Karst.
