Algorithme de Douglas-Peucker
# 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.

## Principe

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 points 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 :

* s'il n'y a aucun point entre les bornes l'algorithme se termine,
* si cette distance est inférieure à un certain seuil on supprime tous les point entre les bornes,
* 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.

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

