Enveloppe nuage de points non convexe

**hilibili** · 14/01/2013, 16h52

Bonjour à tous,
Je cherche à déterminer l'enveloppe d'un nuage de point de données 2D en forme de "diabolo".
La méthode énnoncée dans de nombreux poste avec "convhull" ne convient pas à ma problématique.
Quelqu'un aurait il une solution ??
Merci

**FLB** · 14/01/2013, 17h17

Tu trouves facilement de la littérature sur google et aussi sur DVP. Montre nous ton code et donne nous un exemple de nuage dont l'enveloppe ne correspond pas à tes attentes pour que l'on puisse t'aider.

**hilibili** · 15/01/2013, 08h54

Ci-joint, une photo pour mieux comprendre.
En rouge, ce que MATLAB me donne avec la fonction "convhull", et en bleu ce que j'aimerais obtenir...

**FLB** · 15/01/2013, 09h41

Est ce que tu sais à priori où se situe le centre de ton diabolo?
Si tu arrives à trouver 2 points qui représentent la coupe du milieu du diabolo, tu peux séparer ton nuage en 2 nuages, appliquer convhull aux 2 et fusionner le tout.
Rq : si tu choisis mal tes 2 points, tu auras des points en dehors des 2 surfaces convexes. Tu peux essayer de faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Prendre 2 points vers le centre du diabolo
Tracer virtuellement la ligne de séparation qu'ils créent, récupérer le nuage de point supérieur et inférieur (les 2 points font parties des 2 nuages)
Calculer les enveloppes convexes
Tester si tous les points sont dans une des 2 enveloppes, sinon recommencer avec 2 nouveaux points
Fusionner les 2 surfaces

**hilibili** · 15/01/2013, 14h08

D'après l'architecture de mon fichier , il m'est impossible de découper mon nuage en deux nuages de points...
De plus, la position du "centre du diabolo" sera aléatoire d'un fichier à l'autre.

**FLB** · 15/01/2013, 14h18

Regarde si tu peux implémenter un algorithme de type Jarvis (voir le lien plus haut), mais au lieu de considérer tous les points pour trouver le suivant, restreint toi à une distance donnée : assez grande pour que tu trouves un point suivant de l'enveloppe, assez petit pour coller à ta forme.

**davcha** · 15/01/2013, 15h05

Dans l'absolu, tu n'as pas qu'une solution à ton problème. Si tu te restreint à des diablos, tu peux commencer par faire une PCA et ensuite chercher le couple de points dont la distance, verticale maximale, est la plus faible.