Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
algorithme de convex hull
Bonsoir tout le monde, svp j'ai besoin de votre aide afin de programmer l'algorithme de convex hull.
Je l'ai cherché sur le net, mais j'ai touvé plusieurs alternatives.est ce que quelqu'un pourrait m'aider en me passant l'algoithme afin que je puisse l'implémenter par la suite.merci d'avance
Salut,
Tu trouveras ici l'article qui a servi pour la fonction d'enveloppe convexe de la librairie qhull (écrite en c++).
Pour une bonne utilisation des balises codec'est ici!
Petit guide du voyageur MATLABien :
La nature est un livre écrit en langage mathématique. Galilée.
Bonjour,
convex hull <=> Enveloppe convexe.
Tu peux faire une recherche sur le forum et tu trouveras une multitude de discussions sur le sujet.
Sinon, regarde du coté des algorithmes : marche de Graham, marche de Jarvis.
Il y en a aussi une version qui fait du diviser pour régner : tu calcules l'enveloppe de groupes de deux ou trois points, puis tu les fusionnes.
Consignes aux jeunes padawans : une image vaut 1000 mots !
- Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
- Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
-ton poste tu dois marquer quand la bonne réponse tu as obtenu.
n'étant pas un aficionados de ce forum, je me permettrai une remarque sans doute naïve aux yeux de certains... tu veux coder un algorithme d'enveloppe convexe, c'est bien, mais que souhaites-tu réellement réaliser ?
parce que la vision géométrique n'est pas forcement la bonne manière de faire... une suite de réductions de noyau peut très bien amener au résultat attendu sans avoir à s'embêter avec les détails géométriques
Salut gorgonite,
tu pourrais expliquer cette technique? (ou donner un lien?)Envoyé par gorgonite
une suite de réductions de noyau peut très bien amener au résultat attendu sans avoir à s'embêter avec les détails géométriques
Pour une bonne utilisation des balises code
Petit guide du voyageur MATLABien :
La nature est un livre écrit en langage mathématique. Galilée.
prenons un exemple où une enveloppe convexe représente un polyhèdre, qui lui même n'est en fait qu'un système de (in)équations linéaires sur des variables...
on sait que chacune de ces (in)équations peut alors être vue comme le résultat d'une transformation linéaire (et donc en simplifiant, on ne fait que des réductions de noyau)
en gros, pour la même analyse, tu auras soit à manipuler des enveloppes convexes assez complexes (quid des intersections), ou alors de simples matrices creuses et des transformations linéaires... pas sûr que l'enveloppe convexe soit le plus adapté
j'espère être assez clair
http://www.springerlink.com/content/dyfrulyv6pdhpnul/
Je ne suis pas sûr d'avoir bien saisi la notion de réduction de noyau (ce n'est pas très grave), par contre tu m'as permis de formaliser un peu mieux la recherche d'enveloppe à partir d'une famille de surfaces!prenons un exemple où une enveloppe convexe représente un polyhèdre, qui lui même n'est en fait qu'un système de (in)équations linéaires en des variables...
on sait que chacune de ces (in)équations est également peut alors être vu comme le résultat d'une transformation linéaire (et donc en simplifiant, on ne fait que des réductions de noyau)
en gros, pour la même analyse, tu auras soit à manipuler des enveloppes convexes assez complexes (quid des intersections
j'espère être assez clair
http://www.springerlink.com/content/dyfrulyv6pdhpnul/
Merci et merci pour lien.
Pour une bonne utilisation des balises code
Petit guide du voyageur MATLABien :
La nature est un livre écrit en langage mathématique. Galilée.
disons que si le problème est celui exposé dans le premier post, là tu prends un bulldozer pour écraser une mouche...n'étant pas un aficionados de ce forum, je me permettrai une remarque sans doute naïve aux yeux de certains... tu veux coder un algorithme d'enveloppe convexe, c'est bien, mais que souhaites-tu réellement réaliser ?
parce que la vision géométrique n'est pas forcement la bonne manière de faire... une suite de réductions de noyau peut très bien amener au résultat attendu sans avoir à s'embêter avec les détails géométriques
disons que si le problème est celui exposé dans le premier post, là tu prends un bulldozer pour écraser une mouche...
c'est un post pour apprendre... et le fait d'éviter l'approche géométrique, n'est pas toujours intéressante, mais utile culturellement parlant. ainsi le jour où il aura un vrai problème à traiter, il saura quelle approche utiliser
Répondre avec citation
Partager