Algorithme de Douglas-Peucker

En informatique, plus précisément en algorithmique, plus précisément en algorithmique géométrique, l’algorithme de Douglas-Peucker, aussi connu sous le nom d'algorithme de Ramer-Douglas-Peucker, sert à simplifier un polygone ou une ligne brisée en supprimant des 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.

L'algorithme part du principe suivant. Considérons une ligne brisée (aussi appelée polyligne dans le jargon de l'algorithmique géométrique). On décide de simplifier la ligne brisée et de la remplacer par une ligne simple (deux points), si la distance de son point le plus éloigné de la droite formée par les extrémités de la ligne brisée 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