Discussion :

[Alextoche]

Bonjour à tous,
Je travaille sur un morceau de code depuis un bon moment déjà mais c'est la galère totale et je n'arrive pas le faire fonctionner

Mon problème est assez simple :
Etant donné une liste de points [[x1,x2],[x2,y2], ... ,[xn,yn]]
Je voudrais calculer les enveloppes convexes successives de mon nuage de points et les tracer (on arrête le procédé lorsque la plus petite contient au maximum 3 points).



J'ai déjà essayé de regarder du côté du module scipy dédié (ConvexHull) mais impossible de retirer les points de l'enveloppe convexe qui vient d'être calculée pour calculer la suivante ...
J'ai essayé avec des codes comme celui de Tom Switzer mais il m'a l'air d'y avoir un problème (pour 30 points donnés il me renvoie une enveloppe de 58 points ...).

J'ai vraiment beaucoup besoin de votre aide et de vos conseils,
Merci d'avance,
Alextoche

[Alextoche]

Voici la structure globale de mon programme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def min_convex(points):
 
    oignon_layers = []    
 
    while len(points) > 4:
        layer = convex_hull_graham(points)
        oignon_layers += [layer]
        points = [x for x in points if x not in layer] # I don't know any correct method to remove couples from list of couples
 
    if Plot == True:
        x = [x[0] for x in points]
        y = [y[0] for y in points]
        plt.scatter(x,y,marker = 'o')               # plot all points 
        for x in oignon_layers:                     # plot convex layers
            plot convex hull defined by layer x     #have been trying to do this with plt.Polygon or scipy.ConvexHull but then I have problems of type  
    plt.show()

[Kevin_Mylano]

Bonjour Alextoche ,

je ne sais ce que vaut ma réponse mais sait-on jamais ( à toi par la suite de vérifier mes dires )

Déjà, ce qui me chagrine : on n'écrit pas : oignon_layers += [layer] : là tu traites une liste pas une variable particulière. Tu dois utiliser la fonction append(ou insert ou extend) pour remplir

ta liste : oignon_layers.append(object -> ton objet ici c'est ton layer).

Pour ta liste en compréhension, tu devrais avoir un truc plus dans ce genre : points = [x for x in range(nbre_de_point)] au lieu de : points = [x for x in points if x not in layer]

Tu veux construire une liste de points à partir d'elle-même alors qu'elle n'est pas définie donc comment tu veux par la suite utiliser la taille de ta liste de points (len(points)) comme

condition de ta boucle while

Je ne 'comprends' pas le : if Plot == True ?!

Ensuite tu refais 2 liste en compréhension pour x et y : x = [x[0] for x in points] ?! Je pense que tu devrais écrire un truc plus dans ce genre :


list_point_x = [ x for x in range(nbre_de_point)) idem pour ta liste de y. C'est un peu le bordel

Tu devrais reprendre étape par étape :

1 / : définir une variable : nbre_de_points
2/ : construire ta liste de coordonnées x, y : tu définis une liste de x et de y : list_x/list_y = [x/y for x/y in xrange(nbre_de_point)]
3/ : construire ta liste de points : list_de_points = []
4/ : for i in xrange(len(list_x)) : list_de_point.append([x[i],y[i]]) , une chose comme celà
5/ : Pour le traçage : plt.plot(list_de_point) en 'gros'

ça sera je pense déjà plus clair et structuré

Tiens moi au courant.

Cordialement,

KM

[Alextoche]

Merci pour ta réponse !!

C'est vrai que c'est un peu le bordel ...

Par contre je ne comprend pas en quoi ma liste définie par compréhension : points = [x for x in points if x not in layer] serait équivalente à un : points = [x for x in range(nbre_de_point)] ... Ce que je veux faire c'est supprimer les couples de cordonnées qui interviennent dans l'enveloppe convexe afin de pouvoir récupérer le nuage de points inclus dans cette dernière et itérer.
De plus, je ne sais pas vraiment quelle est la bonne méthode pour supprimer des coulpes dans une liste de couples.

Mon second problème se trouve au niveau du traçage des enveloppes successives et je ne crois pas que vos conseils y répondent, j'ai déjà essayé. J'ai une liste "oignon_layers", qui contient elle même des listes "layers" qui sont composées de couples. Et je n'arrive pas à relier les points de chaque enveloppe correctement pour avoir un polygone convexe.

L'idéal serait d'utiliser ceci : https://docs.scipy.org/doc/scipy/ref...onvexHull.html mais le problème est que l'on ne peux pas retirer les points de l'enveloppe au nuage de point avec une commande du module dédiée ...
Il faudrait alors convertir cette enveloppe sous un format exploitable. Malheureusement le type de l'enveloppe générée est "scipy.spatial.qhull.ConvexHull" et je ne sais pas comment la convertir en liste de couples pour appliquer le procédé expliqué plus haut ...

Merci beaucoup pour vos réponses !!
Alextoche

[wiztricks]

Salut,

L'idéal serait d'utiliser ceci : https://docs.scipy.org/doc/scipy/ref...onvexHull.html mais le problème est que l'on ne peux pas retirer les points de l'enveloppe au nuage de point avec une commande du module dédiée ...

Code :

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

1
2
3
4
>>> from scipy.spatial import ConvexHull
>>> import numpy as np
>>> points = np.random.rand(30, 2)
>>> hull = ConvexHull(points)

L'enveloppe sont les points dont les index sont:

Code :

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

1
2
>>> hull.vertices
array([21, 12, 28,  0, 14, 22], dtype=int32)

Pour les retirer:

Code :

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

>>> points = np.delete(points, hull.vertices, axis=0)

- W

[Alextoche]

Merci beaucoup, c'est clair et net Je teste ça tout de suite !!
Voici donc le code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
import numpy as np
 
points = np.random.rand(30, 2)
 
Plot = True
 
def min_convex(points):
 
    oignon_layers = []    
 
    while len(points) > 4:
        layer = ConvexHull(points)
        oignon_layers.append(layer)
        points =  points = np.delete(points, layer.vertices, axis=0)
 
    if Plot == True:
          plt.plot(points[:,0], points[:,1], 'o')
          for layer in oignon_layers:
              for simplex in layer.simplices:
                 plt.plot(points[simplex, 0], points[simplex, 1], 'k-')  
    plt.show()

Au risque de poser une question idiote, de quoi provient cette erreur :

Code :

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

1
2
3
 
plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
IndexError: index 24 is out of bounds for axis 0 with size 4

Je ne vois pas de listes non définies ou d'itérations excessives ...
Merci pour votre aide !
Alextoche

[wiztricks]

Salut,

Au risque de poser une question idiote, de quoi provient cette erreur :

Code :

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

1
2
3
 
plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
IndexError: index 24 is out of bounds for axis 0 with size 4

Je ne vois pas de listes non définies ou d'itérations excessives ...

Votre question n'est pas idiote. Elle montre que vous avez des difficultés à relire les instructions de que vous avez écrites: comprendre, anticiper ce que la machine en fera...

Et là, je ne peux rien pour vous car c'est un problème de synapses entre vos neurones. Normalement elles sont construites lors de l'apprentissage (ici de la programmation), c'est le résultat d'un processus physico-chimique qui prend plus ou moins de temps suivant les individus, leur histoire,... à vous de trouver un rythme adapté et les tutos. qui vous vont bien.

- W

[Alextoche]

Merci pour le conseil sur l'apprentissage
Je suis assez nouveau en terme de programmation et j'ai appris à peu près seul. J'utilise python comme outil dans le cadre d'un travail de recherche personnelle.
Étant très occupé à faire autre chose que de l'informatique je ne connais que les méthodes de bases liées aux mathématiques.
Il est vrai qu'un apprentissage par la recherche et la sueur sur un problème reste plus longtemps. Dans mon cas, ce petit bout de code qui s'insère dans un ensemble beaucoup plus gros n'est qu'un plus apporté à mon travail puisque l'on ne m'y demande rien en terme de programmation.
Pourriez vous me guider vers un de ces tutoriels dont vous parlez ?
Merci,
Alextoche

[wiztricks]

Pourriez vous me guider vers un de ces tutoriels dont vous parlez ?

Il y a ce qu'il faut dans ma signature.
Après, c'est à vous de voir, le bon tuto. sera celui qui présente des concepts de façon agréable (pour vous) et qui vous incitera à pratiquer (pour vérifier que vous les avez un peu compris).

- W