ENVELOPPE CONVEXE D'UN NUAGE DE POINTS
Cacophrene
Messages postés
251
Date d'inscription
lundi 29 mars 2004
Statut
Membre
Dernière intervention
4 mars 2008
-
19 mars 2006 à 13:00
Cacophrene Messages postés 251 Date d'inscription lundi 29 mars 2004 Statut Membre Dernière intervention 4 mars 2008 - 29 mars 2010 à 16:21
Cacophrene Messages postés 251 Date d'inscription lundi 29 mars 2004 Statut Membre Dernière intervention 4 mars 2008 - 29 mars 2010 à 16:21
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/36614-enveloppe-convexe-d-un-nuage-de-points
https://codes-sources.commentcamarche.net/source/36614-enveloppe-convexe-d-un-nuage-de-points
29 mars 2010 à 16:21
De mon côté je je ne suis plus en mesure d'apporter de l'aide au sujet de VB.
29 mars 2010 à 16:18
PLZ help
29 mars 2010 à 15:26
J'ai fait des recherches, mais je n'ai pas trouvé ce composant pour le télécharger afin de l'intégrer pour que le programme marche enfin.
Any help is welcome thank you.
28 mars 2010 à 20:10
28 mars 2010 à 19:46
28 mars 2010 à 19:43
prjEnveloppeConvexe.exe
ce sont deux fichiers manquant, et j'en ai besoin !!
SOS help plz.
28 mai 2007 à 21:58
Voila a plus
Damien
28 mai 2007 à 21:48
Je suis en train de regardre ta source car c'est exactement ce qu'il me faut.
J'ai cependant noter une différence entre ce que fesait ton algo et ce que dit ton commentaire et je voulais savoir si ca avait une grande importande:
Tu as écrit :
'1. Recherche du point situé le plus en bas à gauche
For i = 0 To UBound(iAbscisses)
If i = 0 Then
'Pour faire des comparaisons, il faut bien assigner des valeurs au départ !
xMin = iAbscisses(0)
yMin = iOrdonnées(0)
Else
'L'abscisse est inférieure : le point est plus à gauche !
If iAbscisses(i) < xMin Then
xMin = iAbscisses(i)
yMin = iOrdonnées(i)
'L'abscisse est identique mais l'ordonnée est inférieure :
'le point est plus bas !
ElseIf iAbscisses(i) = xMin And iOrdonnées(i) < yMin Then
xMin = iAbscisses(i)
yMin = iOrdonnées(i)
End If
End If
Next
Or ce bout de code trouve en fait le point le plus a gauche mais pas le plus en bas. Pour le voir j'ai essayer cette suite de points : 3,2,4,4,4,1,1,4,2,1 et il me donne xMin=1 et yMin=4.
Puisque ton code marche, j'imagine que ce ne doit pas être important mais ca veut dire aussi qu'il est possible d'optimiser le programme en suprimant quelques lignes de la boucle cidessus :
'1. Recherche du point situé le plus à gauche
'Pour faire des comparaisons, il faut bien assigner des valeurs au départ !
xMin = iAbscisses(0)
yMin = iOrdonnées(0)
For i = 0 To UBound(iAbscisses)
'L'abscisse est inférieure : le point est plus à gauche !
If iAbscisses(i) < xMin Then
xMin = iAbscisses(i)
yMin = iOrdonnées(i)
End If
Next
Voila en gros ma question : l'algo marchera t'il toujours si je le modifi ainsi ?
Merci a plus
Damien
24 mars 2006 à 19:47
us_30 et les autres, merci pour vos commentaires et les suggestions qu'ils comportent (et, ne soyons pas ingrat,merci aussi pour les notes !). Le lien que propose Baka02 nous propose l'algorithme issu de la stratégie "diviser pour régner" (oui, on peut traduire divide and conquer en français !). De même que la marche de Graham, il est en O(nlog(n)) ce qui est meilleur que O(nh), je vous l'accorde. Alors maintenant il ne reste plus qu'à programmer l'un de ces algos en complexité logarithmique et non linéaire ! Avis aux amateurs, je doute d'avoir le temps de le faire, ou bien plus tard !
Cordialement,
Cacophrène
21 mars 2006 à 11:19
Je ne connais pas votre intérêt pour les algorithmes de calcul d'enveloppes convexes, mais si vous êtes intéressés, vous pouvez chercher (sur Google ou yahoo) des algorithmes de type "divide and conquer" qui ont donné naissance à des algo comme "quick hull". Bon maintenant de là à le coder en VB ...
C'est pas aussi simple que Jarvis mais très intéressant à comprendre et ça introduit des notions de compléxité des algorithmes.
J'ai trouvé ça qui est pas mal :
http://www-timc.imag.fr/Antoine.Leroy/tutoriaux/convexHull/CH.html
Bonne lecture.
19 mars 2006 à 20:30
En effet, le code est bien construit, très compréhensible et bien commenté; c'est un petit 10/10...
Maintenant la question que je me pose, c'est comment trouver l'algorithme le plus rapide, bien que l'utilisation du calcul du déterminant semble très correcte... Ces petits problèmes qui semblent simple en apparence, sont souvent de vrai casse-tête dès qu'on cherche à les optimiser...
Amicalement,
Us.
19 mars 2006 à 19:56
Je mets un 10/10, bien mérité.
19 mars 2006 à 14:51
19 mars 2006 à 14:41
Personnellement je suis arrivé a appliqué la méthode dont j'avais parlé sur le forum, a ce que j'ai vu c'est la méthode Jarvis, mais légerement modifié
Je prend le point le plus en bas et je tourne dans le sens trigo en prenant comme point suivant, celui qui m'offre le plus petit angle par rapport a un repère arbitraire
19 mars 2006 à 13:00
De façon imagée, la marche de Jarvis s'apparente à un emballage dans du papier cadeau : une fois le premier point trouvé, on tourne autour du nuage de sorte à l'emballer. Le déterminant vient à notre secours pour faire "comprendre" à l'ordinateur ce qu'il faut faire. Bien entendu, face à une telle situation, un être humain a une vue d'ensemble, et son raisonnement est très différent.
A noter, enfin, que l'on peut aussi envisager le cas des polyèdres convexes, mais inutile de dire que la programmation n'est plus aussi simple qu'ici.
Cordialement,
Cacophrène