AccueilCodesTutorielsForumsEmploiLivresConnexion

  • PHP CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2008 09 08 13:23:23
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

ALGORITHME DE DOUGLAS-PEUKER


Information sur la source

Catégorie :Graphique Classé sous : Douglas-Peuker, cartographie, graphique, compression, ajax Niveau : Initié Date de création : 13/04/2008 Date de mise à jour : 18/04/2008 01:06:48 Vu / téléchargé: 3 097 / 86
Auteur : opossum_farceur Ecrire un message privé
Note :
9,25 / 10 - par 4 personnes
9,25 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Commentaire sur cette source (11)
Ajouter un commentaire et/ou une note

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

 

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

18 avril 2008 01:06:51 :
mise à jour v1.1 : optimisation du code d'Anthony Cartmell par suppression des calculs redondants et "dégraissage" de la POO.

Commentaires et avis

signaler à un administrateur
Commentaire de yoman64 le 13/04/2008 03:55:37

Source très intéressante, je ne connaissais pas cet algorythme. Il est très simple à comprendre (même pour moi qui n'est pas trop callé en maths :P).
Le résultat sur le démo est très réussis.  En plus tu as laissé les copyrights d'origine, enfin quelqu'un qui respecte les copyrights , chapeau :)

signaler à un administrateur
Commentaire de pj27 le 13/04/2008 09:46:44 8/10

Cet algorithme est juste très interessant et sa gestion dans ce code est aussi intéressant... Franchement, chapeau, c'est assez propre je trouve ;)
8/10

signaler à un administrateur
Commentaire de webdeb le 13/04/2008 11:48:44 10/10

Que dire si ce n'est bravo !!!

10/10 pour moi ;)

signaler à un administrateur
Commentaire de opossum_farceur le 13/04/2008 18:18:18

Salut,

Merci pour les compliments!
Cet algorithme est certes facile à comprendre, mais peut-être pas si facile que çà à implémenter. Trop content d'en trouver le code sur internet, je me suis contenté d'en vérifier le fonctionnement. Il serait cependant utile de l'étudier à la loupe afin d'essayer d'en améliorer les performances; en effet, avant de l'expérimenter sur les départements (constitués d'à peu près 1000 points chacun), j'ai commencé par le faire sur un contour de la France constitué de 20000 points, et là la moindre réduction s'effectuait, sur mon modeste PC, en une dizaine de secondes!
A noter que dans l'appli la tolérance 0 n'effectue aucune réduction et est donc la plus rapide.

A++

signaler à un administrateur
Commentaire de codefalse le 14/04/2008 10:11:44 administrateur CS 9/10

Vraiment bon travail :)
Quelques remarques :
Tu force le passage en text/html dans ta classe, ce que je te déconseille.
En effet on peux l'utiliser dans un autre usage (traitement xml qui doit travailler avec ta classe par exemple).

Par ailleur tu met tes variables de classe en publique, ce qui est déconseillé, car si durant le traitement, je modifie les valeurs de tes variables, je peux faire planter ton code. Privilégie un acces private ou protected avec les méthodes magiques __get et __set comme ca tu controle l'usage de ta classe :)

Ca mérite un 9/10

signaler à un administrateur
Commentaire de opossum_farceur le 14/04/2008 16:35:19

@CODEFALSE,

"Tu force le passage en text/html dans ta classe"
Ok, je ferai le nécessaire.

"Privilégie un acces private ou protected avec les méthodes magiques __get et __set"
Tu parles là du code d'Anthony Cartmell que je n'ai pas voulu trop chambouler; cependant, ne crois-tu pas qu'en faisant de la sorte, on va rajouter une couche logicielle supplémentaire pour accéder aux données? Comme je le mentionnais dans mon précédent commentaire, un vrai challenge serait d'améliorer les performances de ce code, ce qui passe par un réexamen de l'algo, la suppression des calculs redondants, et aussi un dégraissage au niveau de la POO (et là, je sens que je ne vais pas me faire que des amis!).

A++

signaler à un administrateur
Commentaire de opossum_farceur le 18/04/2008 01:09:23

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++