CALCUL DE L'ENVELOPPE CONVEXE D'UN NUAGE DE POINTS DANS UN PLAN
pgl10
Messages postés
380
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
29 octobre 2023
-
15 déc. 2008 à 18:01
cs_Lucky92 Messages postés 180 Date d'inscription mercredi 22 décembre 2004 Statut Membre Dernière intervention 16 août 2012 - 16 déc. 2008 à 19:02
cs_Lucky92 Messages postés 180 Date d'inscription mercredi 22 décembre 2004 Statut Membre Dernière intervention 16 août 2012 - 16 déc. 2008 à 19:02
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
https://codes-sources.commentcamarche.net/source/48713-calcul-de-l-enveloppe-convexe-d-un-nuage-de-points-dans-un-plan
16 déc. 2008 à 19:02
16 déc. 2008 à 11:45
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+
15 déc. 2008 à 23:26
Merci pour le lien PGL10.
15 déc. 2008 à 23:11
15 déc. 2008 à 23:03
15 déc. 2008 à 22:17
Cependant, cela semble bien être un algo en o(nlogn), à confirmer.
Quel est le nom de la méthode utilisé?
A+
15 déc. 2008 à 19:54
- J'ai mis à jour le lien de la vidéo, merci PLG10.
- l'algorithme a une complexité en O(N) ; ce qui est une bonne nouvelle !
15 déc. 2008 à 18:17
J'ai pas encore regardé ni le lien ni le code mais quelle est la complexité de cet algorithme?
A+
15 déc. 2008 à 18:01