Discussion :

[Tchaill39]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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.

[Tchaill39]

Et en effet, si tu préfère, je cherche bien la frontière de la surface...

[ToTo13]

Bonjour,

je partirai de l'enveloppe convexe, puis je testerai les autres points :
- On rajoute un point au contour, en l'insérant entre deux points du contour.
- Si rajouter ce point fait sortir d'autres points de la zone, alors on ne le garde pas.

[FrancisSourd]

Si tu n'as qu'une centaine de mesures, c'est difficile de se baser sur des méthodes continues...

Je me baserais sur l'algorithme de recherche d'enveloppe convexe dans lequel on fait tourner une tangente. La différence, pour tenir compte de la non-convexité, serait de ne considérer que les points qui sont dans une "petit" rayon du point courant. Tu peux imaginer cet algoritme comme une fourmi myope qui se promène dans le plan: il faut aller à chaque fois au point visible le plus à droite (si tu tournes dans le sens trigo). Si à un moment, il n'y a plus de point visible, il faudra augmenter le rayon de visibilité.

Une autre approche se baserait sur dijkstra. Tu pars d'un point intérieur et tu fais avancer un front de propagation (en ajoutant et supprimant successivement des points) jusqu'à ce que ce front épouse les contours de la région.

Les deux descriptions d'algo sont assez flous. D'une part, ce sont plus des idées que des algos mais aussi la définition d'enveloppe non convexe est elle aussi assez subjective. On peut considérer plusieurs "bonnes" enveloppes pour un ensemble de points donnés.

[sovitec]

Bonjour,

Ma suggestion est d'utiliser le diagramme de Voronoï du nuage de point et de relier les points des "cellules externes" pour obtenir l'enveloppe.

Je ne sais pas si je suis suffisamment clair ?

[ToTo13]

Ma suggestion est d'utiliser le diagramme de Voronoï du nuage de point et de relier les points des "cellules externes" pour obtenir l'enveloppe.

Juste une question :
- Comment sait on si le point d'une cellule est à l'extérieur du diagramme de Voronoi ?

[Jean-Marc.Bourguet]

Bonjour,

Ma suggestion est d'utiliser le diagramme de Voronoï du nuage de point et de relier les points des "cellules externes" pour obtenir l'enveloppe.

Je ne sais pas si je suis suffisamment clair ?

Tu es clair (pour moi et pour quelqu'un qui connait les diagramme de Voronoï), mais si je ne m'absuse, le résultat est l'enveloppe convexe.

Par contre ça me donne une idée qui devrait avoir un résultat pas trop mauvais: partir de la triangulation de Delaunay (dual du diagramme de Voronoï) et virer les côtés des triangles extérieurs si l'angle intérieur de ce triangle est optu (ou supérieur à X degré). Voir le dessin où deux côtes sont enlevés avec ce critère.

[Nemerle]

une idée en +, provenant de la décomposition en triangle "à la périphérie":
http://www.iag.asso.fr/articles/nuage.htm

je l'avais oublié celui-là

[ToTo13]

Bonjour,

à utiliser une triangulation, il vaut mieux utiliser une triangulation de Delauney afin d'être sûr de ne pas avoir de triangles trop "gros". Ca évitera que certains triangles fassent la longueur d'un coté avec une mauvaise triangulation.

En revanche, je ne suis pas sûr qu'une triangulation réponde bien à la question.