CodeS-SourceS est hébergé par Frontier.fr

Cliquez ici pour mettre ce site au démarrage de votre navigateur

AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

begin process at 2009 07 05 05:12:21

SILVERLIGHT 3 : COMMUNICATION ET MULTICAST par KooKiz

[PERSO] DéCOUVERTES ESTIVALES : LINUX (PART I) par FREMYCOMPANY

[REFACTORING] RESHARPER POUR VISUAL STUDIO 2010 (PREVIEW) par tja

[REFACTORING] ANALYSER VOS EXCEPTIONS AVEC RESHARPER EXCEPTIONAL par tja

SHAREPOINT 2007 : PATTERNS & PRACTICES SHAREPOINT GUIDANCE par phil

RE : FILTRER UNE TABLE POUR NE PAS AVOIR DE DOUBLURE par jzeel

RE : COMMENT SECURIRISé UNE BD? par syndrael

RE : COMMENT SECURIRISé UNE BD? par lionceau79

RE : COMMENT SECURIRISé UNE BD? par syndrael

RE : COMMENT SECURIRISé UNE BD? par lionceau79

+ de logiciels à télécharger

1 464 546 membres
54 nouveaux aujourd'hui
15 045 membres club

Trouver une ressource

Trouvez une ressource parmi 40 096 codes, 1 302 921 messages d'aide etc...

Recherche: dans [ Dernières recherches ]

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é: 4 461 / 133

Auteur : opossum_farceur

Ecrire un message privé

Note :

9,25 / 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

Source

voir->zip

voir->zip

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 !

douglas_peuker
- data
  - 01-AIN.TXT 8 200 octets
  - 02-AISNE.TXT 11 198 octets
  - 03-ALLIER.TXT 8 206 octets
  - 04-ALPES DE HAUTE PROVENCE.TXT 7 823 octets
  - 05-HAUTES ALPES.TXT 7 956 octets
  - 06-ALPES MARITIMES.TXT 5 687 octets
  - 07-ARDECHE.TXT 7 178 octets
  - 08-ARDENNES.TXT 7 206 octets
  - 09-ARIEGE.TXT 7 656 octets
  - 10-AUBE.TXT 7 294 octets
  - 11-AUDE.TXT 7 800 octets
  - 12-AVEYRON.TXT 9 098 octets
  - 13-BOUCHES DU RHONE.TXT 6 236 octets
  - 14-CALVADOS.TXT 8 282 octets
  - 15-CANTAL.TXT 8 130 octets
  - 16-CHARENTE.TXT 8 606 octets
  - 17-CHARENTE MARITIME.TXT 11 410 octets
  - 18-CHER.TXT 7 450 octets
  - 19-CORREZE.TXT 7 432 octets
  - 21-COTE D'OR.TXT 9 730 octets
  - 22-COTES D'ARMOR.TXT 9 930 octets
  - 23-CREUSE.TXT 6 894 octets
  - 24-DORDOGNE.TXT 9 560 octets
  - 25-DOUBS.TXT 9 003 octets
  - 26-DROME.TXT 10 192 octets
  - 27-EURE.TXT 9 602 octets
  - 28-EURE ET LOIR.TXT 7 746 octets
  - 29-FINISTERE.TXT 15 145 octets
  - 2A-CORSE SUD.TXT 7 470 octets
  - 2B-HAUTE CORSE.TXT 5 677 octets
  - 30-GARD.TXT 8 448 octets
  - 31-HAUTE GARONNE.TXT 13 762 octets
  - 32-GERS.TXT 8 952 octets
  - 33-GIRONDE.TXT 8 486 octets
  - 34-HERAULT.TXT 6 672 octets
  - 35-ILLE ET VILAINE.TXT 8 620 octets
  - 36-INDRE.TXT 6 928 octets
  - 37-INDRE ET LOIRE.TXT 6 796 octets
  - 38-ISERE.TXT 9 288 octets
  - 39-JURA.TXT 8 532 octets
  - 40-LANDES.TXT 6 700 octets
  - 41-LOIR ET CHER.TXT 7 928 octets
  - 42-LOIRE.TXT 8 892 octets
  - 43-HAUTE LOIRE.TXT 7 410 octets
  - 44-LOIRE ATLANTIQUE.TXT 8 056 octets
  - 45-LOIRET.TXT 7 886 octets
  - 46-LOT.TXT 7 376 octets
  - 47-LOT ET GARONNE.TXT 7 748 octets
  - 48-LOZERE.TXT 6 082 octets
  - 49-MAINE ET LOIRE.TXT 8 526 octets
  - 50-MANCHE.TXT 9 968 octets
  - 51-MARNE.TXT 9 492 octets
  - 52-HAUTE MARNE.TXT 8 876 octets
  - 53-MAYENNE.TXT 7 132 octets
  - 54-MEURTHE ET MOSELLE.TXT 12 742 octets
  - 55-MEUSE.TXT 9 050 octets
  - 56-MORBIHAN.TXT 12 890 octets
  - 57-MOSELLE.TXT 11 861 octets
  - 58-NIEVRE.TXT 7 226 octets
  - 59-NORD.TXT 12 260 octets
  - 60-OISE.TXT 11 438 octets
  - 61-ORNE.TXT 9 588 octets
  - 62-PAS DE CALAIS.TXT 11 464 octets
  - 63-PUY DE DOME.TXT 8 448 octets
  - 64-PYRENEES ATLANTIQUES.TXT 9 062 octets
  - 65-HAUTES PYRENEES.TXT 8 648 octets
  - 66-PYRENEES ORIENTALES.TXT 4 970 octets
  - 67-BAS RHIN.TXT 7 220 octets
  - 68-HAUT RHIN.TXT 5 419 octets
  - 69-RHONE.TXT 7 204 octets
  - 70-HAUTE SAONE.TXT 9 280 octets
  - 71-SAONE ET LOIRE.TXT 11 834 octets
  - 72-SARTHE.TXT 7 356 octets
  - 73-SAVOIE.TXT 7 336 octets
  - 74-HAUTE SAVOIE.TXT 5 906 octets
  - 75-PARIS.TXT 1 106 octets
  - 76-SEINE MARITIME.TXT 7 742 octets
  - 77-SEINE ET MARNE.TXT 8 578 octets
  - 78-YVELINES.TXT 5 738 octets
  - 79-DEUX SEVRES.TXT 8 812 octets
  - 80-SOMME.TXT 10 972 octets
  - 81-TARN.TXT 7 228 octets
  - 82-TARN ET GARONNE.TXT 8 558 octets
  - 83-VAR.TXT 7 612 octets
  - 84-VAUCLUSE.TXT 5 472 octets
  - 85-VENDEE.TXT 7 738 octets
  - 86-VIENNE.TXT 8 776 octets
  - 87-HAUTE VIENNE.TXT 7 928 octets
  - 88-VOSGES.TXT 9 707 octets
  - 89-YONNE.TXT 9 716 octets
  - 90-TERRITOIRE DE BELFORT.TXT 3 157 octets
  - 91-ESSONNE.TXT 4 604 octets
  - 92-HAUTS DE SEINE.TXT 1 792 octets
  - 93-SEINE SAINT-DENIS.TXT 2 060 octets
  - 94-VAL DE MARNE.TXT 2 072 octets
  - 95-VAL D'OISE.TXT 4 882 octets
  - 971-GUADELOUPE.TXT 12 653 octets
  - 972-MARTINIQUE.TXT 3 742 octets
  - 973-GUYANE.TXT 13 907 octets
  - 974-REUNION.TXT 2 536 octets
- index.php 6 784 octets
- loading.gif 10 847 octets
- map.php 11 020 octets

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.

Sources du même auteur

SVGMORPHING

DICTIONNAIRE DE RIMES

SOMMAIRE DÉROULANT

SMOOTH 3D CAMEMBERT

LES CAMEMBERTS 3D

Toutes les sources de opossum_farceur

Sources de la même categorie

CSS-GENERATOR par inwebo

GÉNÉRER UNE PROGRESSBAR (BARRE DE PROGRESSION) EN FORMAT IMA... par Tioneb

GÉNÉRATEUR HTML DE MAP POUR IMAGE CLIQUABLE par 8Tnerolf8

CLASSE : GÉNÉRATEUR DE MINIATURE STRICTE OPTIMISÉ par GauldoMagique

REDIMMENSIONNER UNE IMAGE : CRÉER UNE MINIATURE par adrien78

Toutes les sources de la catégorie Graphique

Sources en rapport avec celle ci

ORGANIGRAMME PHP DYNAMIQUE par megatom

UPLOAD IMAGES POUR FORUMS ET SITES MUTUALISÉS (AJAX + PHP + ... par hartley

PETIT CLIENT + AJAX + PHP par kiki67100

REDIMMENSIONNER UNE IMAGE : CRÉER UNE MINIATURE par adrien78

COMPTEUR DE VISITES (HIT) PARAMÉTRABLE - RELEASE 2.0.0.A par sneezy

Commentaires et avis

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

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

Commentaire de webdeb le 13/04/2008 11:48:44 10/10

Que dire si ce n'est bravo !!!

10/10 pour moi ;)

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

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

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

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

Commentaire de GillesWebmaster le 21/04/2008 07:07:22 10/10

ça c'est de l'algorithme!
Sur ta démo, j'aurais mis une valeur plus petite que 1000...
10/10 !!!

Commentaire de opossum_farceur le 21/04/2008 19:55:08

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

Commentaire de GillesWebmaster le 21/04/2008 21:58:56

Je me réjouis de voire vos améliorations!
Bonne soirée

Commentaire de opossum_farceur le 22/04/2008 00:47:29

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

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

mise a jour de graph via AJAX? [ par LaTatadu91 ] Bonjour a tous; voila  sur uen de mes pages php je créé un graphique(diagrmme en batons+courbes) a partir de données MYSQL ces d Différence ajax / iframe [ par ravery ] Bonjour.Alors, voilà je m'interresse à Ajax pour voir un peut les avantages / inconvénients de cette technologie et je ne comprend pas Pb de sécurité avec Ajax et XMLHttpRequest [ par cz1702 ] Bonjour à tous,est il possible d'ouvrir une page sur un autre domaine que celui du site en cours avec XMLHttpRequest (sans contraindre l'utilisat Anumation graphique entre 2 pages [ par kleos chaos ] Bonjour à tous Voyez vous , cela fait pas mal de temps que je cherche ce script et que je ne le trouve pas. J'ai essayer Javascript, php , CSS, r Fonctionnement AJAX et XMLHTTPRequest [ par stiml ] Bonjour,Voila j'ai récupérer une script sur un site qui explique très bien comment fonctionne AJAX et XMLHTTPRequest.voici l'adresse : Tuto d'Ajax sur phpcs [ par Evangun ] Salut tout le monde,je me suis mis à Ajax aujourd'hui et je voulais signaler que le tuto http://www.phpcs.com/ajax.aspxne marche pas sous firefox Je cherche un editeur php graphique sous linux, c'est urgent!!!!!!!!!! [ par sousou_one ] Bonjour tt le monde, Je cherche un editeur php graphique sous linux, j'ai une distribution SUSE 10.0 est ce que quelqu'un peut m'aider? Merci d'avance Aide pour RPG AJAX CREATOR [ par malalam ] Salut tout le monde,bon, j'ai commencé un projet, il y a quelques temps, qui me tient à coeur. J'ai fini par le baptiser RPG AJAX CREATOR.So Ajax....et javascript [ par chmod777 ] Bonjour à tous!mon problème est le suivant: lorsque je charge via une fonction AJAX le contenu d'une page html dans un div (genre mondiv.inn faire apparaitre un formulaire avec ajax [ par mnoussa ] Bonjour je debute avec ajax et je veux bienen cliquant sur un lien "ajouter utilisateur" faire apparaitre un formulaire de saisie pour inserer les don