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+
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 !
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.
- Messages postés
-
180
- Date d'inscription
- mercredi 22 décembre 2004
- Statut
- Membre
- Dernière intervention
- 16 août 2012
2- Messages postés
-
1054
- Date d'inscription
- samedi 2 octobre 2004
- Statut
- Membre
- Dernière intervention
- 9 juillet 2013
6C'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
2Merci 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