Comparaison des algorithmes de Douglas-Peucker et de Visvalingam-Whyatt

Pour comparer les algorithmes de Douglas-Peucker et de Visvalingam-Whyatt dans le cadre de leur utilisation pour simplifier une trace de randonnée au format GPX, j'ai utilisé celle d'une randonnée qui m'est chère en effectuant une simple observation, sans utiliser un quelconque outil de mesure : le tronçon du E4 reliant Sougia à Agia-Roumeli en Crète.
Ces résultats obtenus sur une seule trace doivent être confirmés par d'autre observations, testis unus, testis nullus.
Pour que les traces réduites puissent être comparables, j'ai fixé à 500 le nombre de points de la trace, ce qui est facilement obtenu avec l'algorithme de Visvalingam-Whyatt et en tâtonnant avec l'algorithme de Douglas-Peucker, j'ai obtenu 499 points de trace en utilisant une résolution de 13m.
Par rapport au fichier original qui contient 2286 points, on obtient un coefficient de réduction de 0,218 soit une réduction de 78% du fichier original.
J'ai choisi le nombre 500 car c'est le nombre maximal de points de traces pour pouvoir importer un fichier dans un Garmin 60 Csx.

Première observation

Le temps de traitement de l'algorithme de Visvalingam-Whyatt est beaucoup plus long que celui de Douglas-Peucker : sur le serveur abritant cette page, un fichier de 24856 points de trace (taille : 6,4 Mo) réduit à 750 points par l'algorithme de Visvalingam-Whyatt a nécessité 32 secondes ; en revanche, seulement 1 seconde a suffit pour le réduire à 768 points avec l'algorithme de Douglas-Peucker.
N.B. Il est certain que l'implémentation de ces algorithmes joue sur les temps d'éxecution : j'ai réalisé celle de Douglas-Peucker alors que celle de Visvalingam-Whyatt provient de https://github.com/Hjok/VisvaPHP

Deuxième observation

L'algorithme de Visvalingam-Whyatt répartit beaucoup plus régulièrement les 500 points sur le parcours en restant assez fidèle à ses méandres alors que celui de Douglas-Peucker en agglutine certains par endroits en laissant par ailleurs de grands espaces : il y a un rabotage des méandres au profit d'un segment de droite, ce qui est cohérent avec la méthode de simplification employée.

Troisième observation

Lorsque le parcours comporte un écart pour revenir ensuite sur le tracé principal par le même chemin, l'algorithme de Visvalingam-Whyatt en supprime la majeure partie. L'avantage va cette fois-ci à l'algorithme de Douglas-Peucker. Simplifier une trace en aller retour sur le même chemin avec l'algorithme de Visvalingam-Whyatt est donc déconseillé.

On peut l'expliquer par le fait que l'algorithme de Visvalingam-Whyatt supprime les triangles ayant une aire presque nulle ce qui est le cas de tous les triplets de points consécutifs d'un trajet en aller retour.
En revanche l'algorithme de Douglas-Peucker va éliminer les triangles ayant une hauteur inférieure à la résolution donnée et selon la façon dont on observe un triangle par sa base, la hauteur peut dépasser la résolution et par conséquent son sommet ne sera pas éliminé par l'algorithme. J'espère me faire comprendre...

Affichage de la trace originale et des traces simplifiées dans une carte

Zoomer et passer la souris sur la trace pour une information sur la trace