CALCUL DE L'ENVELOPPE CONVEXE D'UN NUAGE DE POINTS DANS UN PLAN

Signaler
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
-
Messages postés
180
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
16 août 2012
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/48713-calcul-de-l-enveloppe-convexe-d-un-nuage-de-points-dans-un-plan

Messages postés
180
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
16 août 2012
2
Pistol_Pete , merci pour ta note. Je vais essayer de dégager un peu de temps pour prendre en compte tes deux excellentes suggestions.
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
Effectivement, j'ai testé l'algo et il est bien en n log(n). Il s'agit en fait de l'algo de Graham.

C'est un très bon algorithme mais c'est peu être pas le meilleur. Matlab implémente le Quick Hull par exemple. Le principe est très attractif et je pense que tu peux amélioré la vitesse de ton algo avec cette méthode.

Le principe: tu calcules les 4 points extrémaux de ton nuage de point (le point le plus à gauche, le plus à droite ,le plus en haut, et le plus en bas). Il forment donc un quadrilatère. Et tu supprimes tous les points qui sont dans ce quadrilatère par ce que tu es sure qu'ils ne font pas partie de l'enveloppe convexe.

Là tu as déjà supprimé une bonne partie des points...
Il doit y avoir beaucoup de doc sur cet algo.

Très bonne source 9/10. Je pense que tu aurais pu faire une petite interface graphique. Cela aurait été plus ludique.
A+
Messages postés
180
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
16 août 2012
2
Damned ! J'avais oublié le tri !
Merci pour le lien PGL10.
Messages postés
326
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 janvier 2021
2
Afficher les 9 commentaires