algorithme de convex hull

Version imprimable

28/08/2009, 00h35
dey84

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
28/08/2009, 09h00
Jean Dumoncel

Salut,

Tu trouveras ici l'article qui a servi pour la fonction d'enveloppe convexe de la librairie qhull (écrite en c++).
29/08/2009, 14h39
ToTo13

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.
30/08/2009, 23h08
nicolas66

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
01/09/2009, 17h16
gorgonite

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 ;)
02/09/2009, 11h43
Jean Dumoncel

Salut gorgonite,

Citation:

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 ;)

tu pourrais expliquer cette technique? (ou donner un lien?)
03/09/2009, 09h58
gorgonite

Citation:

Envoyé par magelan

tu pourrais expliquer cette technique? (ou donner un lien?)

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 :aie:), 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/
03/09/2009, 11h45
Jean Dumoncel

Citation:

Envoyé par gorgonite

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 :aie:), 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!

Merci et merci pour lien.
05/09/2009, 12h46
souviron34

Citation:

Envoyé par gorgonite

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... :aie:
05/09/2009, 16h21
gorgonite

Citation:

Envoyé par souviron34

disons que si le problème est celui exposé dans le premier post, là tu prends un bulldozer pour écraser une mouche... :aie:

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 ;)