Algorithme de Douglas-Peuker
Un article de Wikipédia, l'encyclopédie libre.
 |
Aidez à ajouter des liens dans les articles relatifs au sujet. (mars 2008)
|
L'algorithme de 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.
[modifier] 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.
[modifier] Algorithme
L'algorithme travaille de manière récursif 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é de la droite formée par les bornes :
- s'il n'y a aucun nœud entre les bornes l'algorithme se termine,
- si cette distance est inférieure à un certain seuil on supprime tous les nœuds 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 nœud distant, et du nœud distant à la borne finale.
[modifier] 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és par un nœud (cas 1).
La complexité est en 
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.
