enveloppe d'un nuage de points

**Tchaill39** · 04/09/2006, 11h15

Salut à tous....

Je cherche à tracer l'enveloppe d'un nuage de points. Quelqu'un connaitrait-il pas un algo pour ca.

NB : J'ai déja trouvé des truc mais ca ne marche que pour les courbes convexes. Si on a un point d'inflexion, c'est mort...

**Nemerle** · 04/09/2006, 11h25

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

http://www.cs.sunysb.edu/~algorith/i...mplement.shtml

tu en as plétore sur google --> ce que tu cherches s'énonce en anglais "convex hull"

**Tchaill39** · 04/09/2006, 11h33

Non, "convex hull", c'est enveloppe convexe. Moi dans mon Pb, j'ai des concavités et la ca marche plus du tout. La méthode avec les triangles ne marche plus.

**ToTo13** · 04/09/2006, 12h53

Bonjour,

la seule méthode que je connaisse est du type diviser pour régner :
- tu tries tes points.
- tu les divises jusqu'a obtenir des doublons ou des triangles.
- tu remonte en fusionnnant les enveloppes.

Sinon, google est tont ami.

**Nemerle** · 04/09/2006, 13h41

Envoyé par Tchaill39

Non, "convex hull", c'est enveloppe convexe. Moi dans mon Pb, j'ai des concavités et la ca marche plus du tout. La méthode avec les triangles ne marche plus.

Dans ce type de problème, tu peux pré-trier en utilisant un algorithme qui te décompose ton nuage "non"-convexe en réunions de nuages ayant une enveloppe convexe --> tu pars d'un point et ajoute un des voisins les + proche pour construire la composante convexe.

**FrancisSourd** · 05/09/2006, 08h51

Envoyé par Tchaill39

NB : J'ai déja trouvé des truc mais ca ne marche que pour les courbes convexes. Si on a un point d'inflexion, c'est mort...

Comment définis-tu cette enveloppe: est-ce que tous les points doivent-être dans l'enveloppe? Si c'est le cas tu peux prendre un chemin hamiltonien sans croisement: soit le plus court chemin (NP-complet) soit un chemin hamiltonien quelconque dans lequel tu "décroises" les croisements par voisinage.

**Tchaill39** · 05/09/2006, 10h45

Nom : simu_pas_cool.jpg
Affichages : 1837
Taille : 22,3 Ko

La figure bleue est un ensemble de points. Je veut trouver la courbe permettant de dessiner la forme et d'avoir un afichage plus rapide.

**FrancisSourd** · 05/09/2006, 14h14

Recherches-tu donc la frontière d'une surface?
Apparamment, tu as un très grand nombre de points: comment les as-tu en entrée? Est-ce un continuum de points comme le laisse penser l'image? Sont-ils donnés à partir d'une image? d'équations?

**ToTo13** · 05/09/2006, 15h10

Bonjour,

effectivement, ça ne ressemble pas trop à un nuage de points.
Peux tu préciser l'origine et la structure de tes données...

**Tchaill39** · 05/09/2006, 15h54

Mes données sont tirées d'un fichier définit comme ceci :

FSimul = File of TTabNb;
TTabNb = array[1..Nb_simulation] of real;
Nb_simulation : 100

Sur le représentation dqui est au dessus, les points correspondant à chaque tableau sont reliés par des segments. En tout, j'ai à peu près 200 tableaux.

enveloppe d'un nuage de points

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager