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

pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 - 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
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

cs_Lucky92 Messages postés 180 Date d'inscription mercredi 22 décembre 2004 Statut Membre Dernière intervention 16 août 2012 2
16 déc. 2008 à 19:02
Pistol_Pete , merci pour ta note. Je vais essayer de dégager un peu de temps pour prendre en compte tes deux excellentes suggestions.
Pistol_Pete Messages postés 1053 Date d'inscription samedi 2 octobre 2004 Statut Membre Dernière intervention 9 juillet 2013 7
16 déc. 2008 à 11:45
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+
cs_Lucky92 Messages postés 180 Date d'inscription mercredi 22 décembre 2004 Statut Membre Dernière intervention 16 août 2012 2
15 déc. 2008 à 23:26
Damned ! J'avais oublié le tri !
Merci pour le lien PGL10.
pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 11
15 déc. 2008 à 23:11
pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 11
15 déc. 2008 à 23:03
Le cours de Gérard Berry identifie une partie en o(nlogn) et deux autres en o(n). Globalement cet algorithme est donc bien en o(nlogn) comme signalé. Mais c'est déjà bien !
Pistol_Pete Messages postés 1053 Date d'inscription samedi 2 octobre 2004 Statut Membre Dernière intervention 9 juillet 2013 7
15 déc. 2008 à 22:17
Houla o(N)!!! Quoi qu'il arrive tu utilises un algo de tri donc c'est déjà o(nlogn). Pour moi il est impossible de faire ce problème en o(n).
Cependant, cela semble bien être un algo en o(nlogn), à confirmer.

Quel est le nom de la méthode utilisé?

A+
cs_Lucky92 Messages postés 180 Date d'inscription mercredi 22 décembre 2004 Statut Membre Dernière intervention 16 août 2012 2
15 déc. 2008 à 19:54
Bonjour et merci pour l'intérêt que vous portez à cette source.

- 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 !
Pistol_Pete Messages postés 1053 Date d'inscription samedi 2 octobre 2004 Statut Membre Dernière intervention 9 juillet 2013 7
15 déc. 2008 à 18:17
Salut

J'ai pas encore regardé ni le lien ni le code mais quelle est la complexité de cet algorithme?

A+
pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 11
15 déc. 2008 à 18:01
L'adresse Internet de la conférence de Gérard Berry au Collège de France vient de changer. On peut la retrouver parmi l'ensemble des conférences référencées à : http://www.college-de-france.fr/default/EN/all/inn_tec2007/index.htm
Rejoignez-nous