Algorithme de Douglas-Peucker

L’algorithme de Ramer-Douglas-Peucker sert à simplifier un polygone ou une polyligne par la suppression de points. L'algorithme a été publié par David H. Douglas et Thomas K. Peucker en 1973. Il est utilisé en compression de données vectorielles et en généralisation cartographique^{[réf. nécessaire]}.

Principe

Réduction des points d'une courbe par l'algorithme de Ramer-Douglas-Peucker.

Une polyligne (n points) est simplifiable et remplacée par une ligne simple (deux points) si la distance de son points le plus éloigné de la droite formée par les extrémités de la polyligne est inférieure à un certain seuil.

L'algorithme travaille de manière récursive par la méthode « diviser pour régner ».

À l'initialisation on sélectionne le premier et le dernier point (cas d'une polyligne), ou un point quelconque (cas d'un polygone). Ce sont les bornes initiales.

À chaque étape on parcourt tous les points entre les bornes et on sélectionne le point le plus éloigné du segment formé par les bornes :

1. s'il n'y a aucun point entre les bornes l'algorithme se termine,
2. si cette distance est inférieure à un certain seuil on supprime tous les point entre les bornes,
3. si elle est supérieure la polyligne n'est pas directement simplifiable. On appelle de manière récursive l'algorithme sur deux sous-parties de la polyligne : de la première borne au point distant, et du point distant à la borne finale.

Pseudo-code

fonction DouglasPeucker(points[1..n], ε)
   // Trouve l'indice du point le plus éloigné du segment
   dmax = 0
   index = 0
   pour i = 2 à n - 1
         d = distance du points[i] au segment [points[1], points[n])
         si d > dmax
              index = i
              dmax = d
 
  // Si la distance dmax est supérieure au seuil, appels récursifs
  si dmax > ε
         // Appel récursif de la fonction
         recPoints1[1..k] = DouglasPeucker(points[1…index], ε)
         recPoints2[1..m] = DouglasPeucker(points[index…n], ε)
  
         // Construit la liste des résultats à partir des résultats partiels
         renvoie la concaténation de recPoints1[1…k-1] et recResults2[1…m]

  sinon // Tous les points sont proches → renvoie un segment avec les extrémités
         renvoie [points[1], points[n]]

Complexité

On remarquera que l'algorithme se finit forcément puisque dans le pire des cas la polyligne (ou le polygone) n'est pas simplifiable et chaque branche formée par la récursion s'achèvera lorsque les bornes ne seront pas séparées par un nœud (cas 1).

Dans le meilleur des cas, la complexité est en $O(n\log(n))$ puisqu'à chaque itération le nombre de branches de récursion est multiplié par deux et tous les points sont visités. Le pire des cas est en $O(n^{2})$ car il correspond au cas où chaque segment est coupé au niveau du deuxième point. On parcourt donc n-2 points à la première itération, n-3 à la seconde, etc.

En utilisant une structure de données dynamique pour représenter une enveloppe convexe, l'algorithme peut s'implémenter en $O(n\log(n))$ dans le pire cas.

Voir aussi

L'algorithme de Visvalingam (1992) donne aussi de très bons résultats, voire meilleurs^{[pas clair][réf. nécessaire]}

cf cette description simple

ou cet article complet