AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

  • Visual Basic, VB6, VB.NET, VB 2005, VB CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2009 07 06 18:19:15
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

ENVELOPPE CONVEXE D'UN NUAGE DE POINTS


Information sur la source

Catégorie :Maths Classé sous : enveloppe, convexe, déterminant Niveau : Débutant Date de création : 19/03/2006 Date de mise à jour : 19/03/2006 12:49:06 Vu / téléchargé: 6 052 / 608
Auteur : Cacophrene Ecrire un message privé
Note :
9,67 / 10 - par 3 personnes
9,67 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Commentaire sur cette source (9)
Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale
Le code que je vous propose ici est destiné à illustrer un exemple de recherche d'enveloppe convexe à l'aide de la notion mathématique de déterminant, POUR REPONDRE A UNE QUESTION POSEE SUR LE FORUM. L'enveloppe convexe est le plus petit polygone contenant un ensemble de points du plan. L'exemple que je vous propose ici ne fonctionne que pour des points à coordonnées entières. Evidemment, vous pouvez sans problème remplacer les Integer par le type qui vous plaira. De même l'algorithme peut être amélioré, simplifié, etc... mais il ne s'agit ici que d'une illustration. Le programme nécessite l'OCX de Renfield (ReyXp.ocx).
 

Conclusion

Remerciements à Renfield pour l'OCX, comme de coutume. Si vous avez des questions sur l'algorithme n'hésitez pas (surtout celui à qui cet exemple est destiné !).
 

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Historique

19 mars 2006 12:49:07 :
Quelques retouches dans le code (erreurs inattendues).

Commentaires et avis

signaler à un administrateur
Commentaire de Cacophrene le 19/03/2006 13:00:39

Juste une précision : L'algorithme que je vous présente s'apparente à la "marche de Jarvis". Il existe une autre méthode, le "parcours de Graham". On peut trouver quelques infos sur le sujet sur Wikipédia (tapez http://fr.wikipedia.org/wiki/Enveloppe_convexe).

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

signaler à un administrateur
Commentaire de boulacmoi le 19/03/2006 14:41:04

Merci,
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

signaler à un administrateur
Commentaire de Cacophrene le 19/03/2006 14:51:50

En effet.

signaler à un administrateur
Commentaire de jean_marc_n2 le 19/03/2006 19:56:18

Hello, très sympa, le code est nicekl et bien commenté. Le tout fonctionne parfaitement et l'exemple d'utilisation est très sympa, avec un joli rendu.
Je mets un 10/10, bien mérité.

signaler à un administrateur
Commentaire de us_30 le 19/03/2006 20:30:57

Bonsoir à tous,

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.

signaler à un administrateur
Commentaire de baka02 le 21/03/2006 11:19:32

Bonjour,
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.

signaler à un administrateur
Commentaire de Cacophrene le 24/03/2006 19:47:03

Salut !

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

signaler à un administrateur
Commentaire de Zakata le 28/05/2007 21:48:10

Salut

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

signaler à un administrateur
Commentaire de Zakata le 28/05/2007 21:58:19

Petite rectification, la boucle trouve le point le plus a gauche su ce dernier n'a pas une asisse comune avec un autre. Dans le cas contraire, il trouvera le point le plus à gauche et le plus en bas des points.

Voila a plus
Damien

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

Calcul de l'enveloppe convexe d'un nuage de points en C++ [ par fantome2040 ] Bonjour Comme il est ecrit dans le sujet je cherche un programme en C++ qui me permetrai de calculer une enveloppe convexe d'un nuage de point. Je vie Enveloppe et étiquette [ par jayrock ] BonjourJ'aimerais savoir comment faire pour utiliser le module de création d'enveloppe et étiquette de Word 2000 depuis VB6. Le but est de créer une f enveloppe [ par laurent180 ] J'aimerai a partir d'une base de donné, imprimé le nom et adresse de la ou les personne choisie sur enveloppe, y a t'il dans vb une fenetre d'impressi Publipostage d'enveloppe [ par pachaa ] Dans acess 2002 j'ai bien l'assistant étiquette mais pas enveloppe pourtant dans une version antèrieure il y etait.pourait-on m'éclairer. Figure convexe a partir d'un nuage de point [ par boulacmoi ] Bonjour,J'essaie de faire un petit programme qui me permettrait a partir d'un nuage de points cr&#233;er dans une picture, de r&#233;aliser la figure Déplacer le déterminant à la fin de la phrase [ par mierkool ] Bonjour, je voudrais savoir comment faire pour dans une chaine de caractères, déplacer le déterminant du début de la phrase et le mettre à la fin de


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Comparez les prix Nouvelle version


Console Nintendo DSi Blanche
Entre 160€ et 170€


Visiter le guide achat

Photothèque Nouveau !

Photo friends at the beach.Photo alphabet langue des sourds
Photo homme nu 

Visiter la photothèque


Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés
Temps d'éxécution de la page : 0,499 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.