Algorithme de Douglas-Peuker

L’algorithme de Ramer-Douglas-Peuker 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.

Sommaire

Principe

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

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

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é

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 n\times ln(n) puisque dans le pire des cas aucune simplification n'est effectuée et chaque branche de la récursion se termine par le cas 1. À chaque étape le nombre de branches de récursion est multiplié par deux et tous les nœuds sont visités.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Douglas-Peuker de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Compression de données — La compression de données ou codage de source est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s agit d… …   Wikipédia en Français

  • Compression De Données — La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La décompression est l… …   Wikipédia en Français

  • Compression de donnees — Compression de données La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La… …   Wikipédia en Français

  • Compression informatique — Compression de données La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La… …   Wikipédia en Français

  • Compression D'image — La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper beaucoup d espace ou… …   Wikipédia en Français

  • Compression d'images — Compression d image La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper… …   Wikipédia en Français

  • Compression d'image — La compression d image est une application de la compression de données sur des images numériques. Cette compression a pour utilité de réduire la redondance des données d une image afin de pouvoir l emmagasiner sans occuper beaucoup d espace ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”