Ordonner des points

[Cliffe]

Salut,

Je cherche une astuce pour ordonner rapidement des points dans R^3. Je souhaite les relier pour obtenir un polygone.

exemple en 2D :
[CENTER] [/CENTER]

s'ils ne sont pas ordonnées je n'obtiens pas un polygone. Peut importe qui est le premier et qui est le dernier.
Je connais les coordonnées (x, y, z) de chaque points.

Merci.

[fatal_error]

salut

tu devrais tenter une recherche sur ce forum ca a déjà été abordé
de mémoire,
j'avais parlé de convex hull

ya aussi ben314 qui avait proposé de prendre un point (par exemple le barycentre, mais un des points doit marcher) puis de calculer pour ce point l'angle fait par chacun des autres points (ex:entre l'axe des abscisses et ce centre et l'autre point), et puis de les trier par angles croissants

edit:
http://www.maths-forum.com/showthread.php?t=153183&highlight=enveloppe+convexe

[Cliffe]

oui, je connais cette méthode.
Je cherche une autre astuce.

Si quelqu'un à mieux. :lol3:

[Ben314]

Salut,
Quand tu dit "mieux", c'est en terme de quoi, "d'esthétique" ou de complexité.
Si c'est en terme de complexité, je sais pas si tu arrivera à faire mieux que le n.log(n) des tri...

[mathelot]

oui, je connais cette méthode.
Je cherche une autre astuce.

Si quelqu'un à mieux. :lol3:

par récurrence sur le nombre de points ?

soit V la variété linéaire affine engendrée par (n-1) points


si , on le relie par des segments à tous les points précédents

si , en dimension 2 , on rajoute un triangle, en autre
dimension on aajoute un polyèdre et on efface le polygone d'adjacence (selon lequel on recolle),

est ce que ça se fait avec des coeefficients barycentriques ?