Algorithme de douglas-peuker

Soyez le premier à donner votre avis sur cette source.

Vue 12 026 fois - Téléchargée 717 fois

Description

En ces temps bénis où chaque brin d'herbe est référencé sur GoogleEarth et où la moindre trottinette est vendue avec le GPS, peut-être serait-il judicieux de s'intéresser à l'algorithme de Douglas-Peuker?

La définition de Wikipédia (http://fr.wikipedia.org/wiki/Algorithme_de_Douglas-Peuker) :
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.

La mienne :
Un contour est constitué d'un certain nombre de points reliés entre eux. Le travail de l'algorithme est de ne garder que les plus significatifs en fonction d'un paramètre appelé "tolérance".

Je suis parti de la classe écrite par Anthony Cartmell que l'on peut trouver à l'adresse suivante :
http://www.fonant.com/demos/douglas_peucker/algorithm
et l'ai adaptée à mon application de tracé des contours des départements exprimés en coordonnées Lambert 93.

La démo en ligne :
http://michel.vanthodiep.free.fr/douglas_peuker/

origine des données :
http://www.ign.fr/rubrique.asp?rbr_id=2749&lng_id=FR
L'algorithme expliqué "pas à pas" :
http://ljk.imag.fr/membres/Nicolas.Szafran/ENSEIGNEMENT/MASTER2/VISU/cours6.pdf

Source / Exemple :


voir->zip

Codes Sources

Ajouter un commentaire Commentaires
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009

J'ai indiqué ce lien au cas où quelques téméraires voudraient pousser plus loin la recherche; en ce qui me concerne, j'arrête là avec ce code, j'y ai passé trop de temps à mon avis, d'autant plus que ce sujet n'a pas l'air de passionner les foules (dommage!). Ceci dit, si le code existant recèle un bug malicieux, j'en assure la maintenance, il n'y a pas de soucis!

a++
Messages postés
496
Date d'inscription
mercredi 30 juin 2004
Statut
Membre
Dernière intervention
29 juillet 2009
1
Je me réjouis de voire vos améliorations!
Bonne soirée
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009

@GillesWebmaster,

Merci pour la note!

"j'aurais mis une valeur plus petite que 1000"
C'est noté, j'y penserai si une mise à jour s'avère nécessaire.

Depuis la publication de ce script, j'ai découvert qu'il existait 2 manières d'écrire (dont une forcément erronée!) le nom des auteurs de l'algorithme.
Le résultat des requêtes suivantes donne, sur Google :
"douglas-peuker" : 6980 pages
"douglas-peucker" : 17100 pages
et rares sont les pages présentes à la fois dans les 2 recherches, alors qu'elles traitent manifestement de la même chose! Celà m'a permis d'accéder à de nouvelles informations, notamment qu'il est possible d'améliorer l'algorithme :

http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm

A++
Messages postés
496
Date d'inscription
mercredi 30 juin 2004
Statut
Membre
Dernière intervention
29 juillet 2009
1
ça c'est de l'algorithme!
Sur ta démo, j'aurais mis une valeur plus petite que 1000...
10/10 !!!
Messages postés
147
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009

Salut,
J'ai donc étudié le code d'Anthony Cartmell à la loupe afin d'en améliorer les performances; résultat des courses : une "réduction" exécutée en un temps divisé par 3, l'occupation de la mémoire, divisée par 3 également (à vue de nez).
Moyens mis en oeuvre : passage des tableaux par références, suppression des calculs redondants et "dégraissage" de la POO (suppression de la classe "Vector" et création d'objets seulement quand c'est nécessaire).
A++
Afficher les 11 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.