Algorithme de Douglas-Peucker

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L’algorithme de Ramer-Douglas-Peucker sert à simplifier un polygone ou une polyligne par la suppression de nœud. Il est beaucoup utilisé en compression de données vectorielles et en généralisation cartographique.

Principe[modifier | modifier le code]

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

Algorithme[modifier | modifier le code]

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

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 nœud (cas d'une polyligne), ou un nœud quelconque (cas d'un polygone). Ce sont les bornes.

À chaque étape on parcourt tous les nœuds entre les bornes et on sélectionne le nœud le plus éloigné du segment formé par les bornes :

  1. s'il n'y a aucun nœud entre les bornes l'algorithme se termine,
  2. si cette distance est inférieure à un certain seuil on supprime tous les nœuds 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 nœud distant, et du nœud distant à la borne finale.

Pseudocode[modifier | modifier le code]

function DouglasPeucker(PointList[], epsilon)
  // Trouve le point le plus éloigné du segment
  dmax = 0
  index = 0
  for i = 2 to (length(PointList) - 1)
    d = DistancePointSegment(PointList[i], Segment(PointList[1], PointList[end])) 
    if d > dmax
      index = i
      dmax = d
    end
  end
 
  // Si la distance dmax est supérieure au seuil, on simplifie
  if dmax >= epsilon
    // Appel récursif de la fonction
    recResults1[] = DouglasPeucker(PointList[1…index], epsilon)
    recResults2[] = DouglasPeucker(PointList[index…end], epsilon)
  
    // Construit la liste des résultats à partir des résultats partiels
    ResultList[] = {recResults1[1…end-1] recResults2[1…end]}

  else
    // Tous les points sont proches → renvoie un segment avec les extrémités
    ResultList[] = {PointList[1], PointList[end]}
  end
 
  // Renvoie le nouveau résultat
  return ResultList[]
end

Complexité[modifier | modifier le code]

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).

La complexité est en O(n\times ln(n)) puisqu'à chaque itération le nombre de branches de récursion est multiplié par deux et tous les nœuds 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...