Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2919 connectés 

  FORUM HardWare.fr
  Programmation
  Python

  Trier des points selon leurs distances les uns aux autres

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Trier des points selon leurs distances les uns aux autres

n°2301511
doctardis
Posté le 03-06-2017 à 16:25:23  profilanswer
 

Bonjour,
 
Je débute sur python et je voudrais trier des points en fonction de leur distance les uns aux autres. J'ai commencé le programme ci-dessous pour calculer la distance entre chaque points :
 

Code :
  1. x,y,z=np.loadtxt('points.txt', unpack=True)
  2. x0,y0,z0=x[0],y[0],z[0]
  3. for i in range(len(x)):
  4.     L=[]
  5.     for j in range(0,len(x)):
  6.         if x[j]!=x0 or y[j]!=y0 or z[j]!=z0:
  7.             distance=m.sqrt((x[j]-x0)**2+(y[j]-y0)**2+(z[j]-z0)**2)
  8.             L.append(distance)


 
Malheureusement, je ne sais pas vraiment comment continuer, sachant que je voudrais à la fin une liste avec tous les points triés et que chacun n'apparaissent qu'une seule fois (je précise que x[i],y[i] et z[i] sont trois coordonnées qui définissent le point dans l'espace).
 
Est-ce que quelqu'un peut m'aider svp ?
 
Merci d'avance

mood
Publicité
Posté le 03-06-2017 à 16:25:23  profilanswer
 

n°2301512
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 16:54:07  profilanswer
 

Bonjour,
 

doctardis a écrit :

je voudrais trier des points en fonction de leur distance les uns aux autres


 
Pour l'instant, d'après ton code, tu sembles surtout vouloir trier des points en fonction de leur distance à l'origine du repère et non de leur distance entre eux. Est-ce bien ça?
 
Exclure du calcul un point sur l'origine, ok, mais ne pas le supprimer de la liste même si sa distance est nulle puisque tu veux TOUS les points triés à la fin.
 
À quoi sert ta boucle for avec la variable i?
 
Sinon les algos de tri sont nombreux, cela dépend de la quantité de données à trier.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301514
doctardis
Posté le 03-06-2017 à 17:14:15  profilanswer
 

C'est juste un bout de programme pour l'instant, où j'ai mis des commandes que je pensais peut-être utiles pour la suite.  
 
Je prends à chaque fois la distance par rapport à un  autre point et non l'origine. Il me faudrait quelque chose juste après ma boucle for en j qui prendrait le minimum dans L et mette les points qui ont servi à trouver cette distance minimale dans une liste (L2 par exemple), tout en faisant attention à ce que cette valeur n'appartienne pas déjà à L2.
 
Ma boucle for en i est là pour la suite ; quand on a trouvé les coordonnées du point suivant, on change les valeurs de x0, y0 et z0 et on recommence avec ce nouveau point.
 
Par exemple: avec x=[1,3,2],y=[1,3,2],z=[1,3,2], on a x0=1,y0=1 et z0=1. Ainsi le point le plus proche de [1,1,1] est [2,2,2]. Après que le programme ait mis [2,2,2] dans L2, x0 prend la valeur 2, y0 la valeur 2 et z0 la valeur 2. et si tout se passe bien, on devrait trouver à la fin L2=[[1,1,1],[2,2,2],[3,3,3]]
 
Pour la quantité de points à trier, j'ai un peu moins de 700 points.
 
Je ne sais pas si j'ai été vraiment très clair, mais j'espère que ça pourra aider

n°2301530
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 19:06:27  profilanswer
 

Ok j'avais regardé trop rapidement, sinon 700 points ça fait 244 650 distances possibles. Je ne connais pas Python mais ça doit faire quelques Mo de mémoire.
 
Pourquoi tu ne peux pas avoir plusieurs distances égales? Laquelle éliminer? Que veux-tu faire avec ta liste de distances triées?
 
Sinon pour le tri, tu retrouveras plusieurs algos sur cette page : https://fr.wikipedia.org/wiki/Algorithme_de_tri
Je te conseille d'utiliser le "tri rapide" qui n'est pas très compliqué à mettre en place.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301531
doctardis
Posté le 03-06-2017 à 19:23:53  profilanswer
 

J'avais prévu que ça prendrait pas mal de mémoire et aussi de temps à se résoudre.  
 
Normalement, mes points sont prévus pour qu'il n'y ait pas de distance égale, donc pas de problème la-dessus.
 
Après, avec la liste, je prévois d'exporter les points triés sur excel et je pourrais faire une étude de dérivée au point par point si je connais le point juste avant et celui juste après.
 
Pour le lien, merci beaucoup, je vais regarder ça de plus près !

n°2301532
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 19:50:25  profilanswer
 

Par contre je crois que je viens enfin de comprendre ton problème, mais ça n'a pas de sens comme tu l'as présenté. Au final tu veux quoi? Une liste des points triés de manière à que la distance entre 2 points consécutifs soit toujours la plus faible possible?

 

Sinon, juste comme ça, comment ce fait-ce que tes points sont dans le désordre? N'as-tu pas un autre moyen de les ordonner?


Message édité par MaybeEijOrNot le 03-06-2017 à 19:51:15

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301533
doctardis
Posté le 03-06-2017 à 19:57:40  profilanswer
 

Alors, pour tout t'expliquer, je dois étudier le trajet d'une montagne russe. J'avais une vue de dessus du manège avec le trajet en noir et le fond blanc donc j'ai fait un algorithme qui me trouvait toutes les coordonnées des pixels noirs. Du coup, ça les as triés colonne par colonne et pas dans l'ordre. Et le seul moyen pour les ordonner serait de le faire à la main (et pour 700 points, ça va vite être chiant..).
 
Ce que je veux au final, c'est donc l'ordre des points par lesquels passe le wagon pendant le trajet.

n°2301539
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 20:44:45  profilanswer
 

Oui donc tu veux bien les plus proches voisins.

 

Tu as des intersections dans le trajet?

 

Tu pourrais tout simplement partir d'un pixel noir, regarder les pixels autour de ce dernier, tout en définissant un sens de recherche, et définir à quelles coordonnées est le pixel noir le plus proche et ainsi de suite. Cela réduit considérablement la complexité de l'algo puisque tu tombes dans un cas de traitement linéaire.
En effet si on part sur un pixel, ça ne ferait au max que 700*7 comparaisons.

 

Bon en réalité ce sera plus compliqué car tu dois prendre en compte l'épaisseur de ta trajectoire si je puis dire. Ainsi chaque coordonnée sera entourée en fait de plusieurs pixels noirs mais ça reste largement jouable.


Message édité par MaybeEijOrNot le 03-06-2017 à 20:45:19

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301540
doctardis
Posté le 03-06-2017 à 21:16:12  profilanswer
 

Ok je vois où tu veux en venir, et j'ai déjà fait en sorte que "l'épaisseur du trajet" ne prenne qu'un seul pixel donc pas besoin de s'en préoccuper. Pas d'intersections non plus. Par contre, je ne vois pas vraiment comment faire pour "regarder les pixels autour"...

n°2301541
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 21:41:28  profilanswer
 

Comment as-tu fais pour récupérer les coordonnées des pixels noirs?
 
Mais bon grossomodo, ton image c'est une grille de pixels pouvant être représentée par un tableau (ou une liste) multidimensionnel où chaque clé représente les coordonnées d'un pixel et la valeur représente la couleur du pixel.
 
Tu détermines un point de départ sur un pixel noir. Tu ranges ses coordonnées dans une nouvelle liste. Tu détermines un sens de recherche. Par exemple vers la droite, à ce moment là tu regardes la valeur du pixel au-dessus puis dans le coin supérieur puis à droite puis coin inférieur droite ainsi de suite jusqu'à temps que la valeur fasse apparaitre un pixel noir. À ce moment là tu notes les coordonnées du pixel trouvé dans ta nouvelle liste. Tu passes alors à la recherche d'un pixel noir autour du dernier trouvé en tenant compte du sens dans lequel tu t'es déplacé afin d'éviter de faire demi-tour.
Tu répètes cela jusqu'à temps d'être revenu aux coordonnées de départ.
 
Donc ça c'est le cas où chaque pixel noir est contigüe avec uniquement deux pixels noirs : le précédent et le suivant.
 
Par contre je vois que tu travailles sur 3 axes et non 2, la profondeur est gérée comment (niveau de gris?) ou alors tu parts d'un fichier 3d?
Si fichier 3d alors ça ne change pas grand chose, ça fait juste plus de pixels à vérifier à chaque fois.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
mood
Publicité
Posté le 03-06-2017 à 21:41:28  profilanswer
 

n°2301542
doctardis
Posté le 03-06-2017 à 21:50:08  profilanswer
 

J'ai pu récupérer la hauteur avec un modèle 3D et avec certaines données que j'ai trouvées. Après, je n'arrive justement pas à voir comment jouer sur les trois axes sachant que l'image est en 2D. Ou alors, il faudrait faire l'algo en 2D et remettre toutes les valeurs de hauteur après.

n°2301545
MaybeEijOr​Not
but someone at least
Posté le 03-06-2017 à 23:29:45  profilanswer
 

Oublie l'image, je t'induis en erreur avec, je pensais que tu étais parti d'une image et non d'un fichier 3d.

 

Les coordonnées sont-elles des valeurs entières?

 

Malheureusement je ne connais pas Python mais si j'essaye de prendre les termes exactes, peut-on créer des dictionnaires de dictionnaires (dictionnaire multi-dimensionnel)? Ainsi tu places chacun de tes points dans un dictionnaire de 3 dimensions où chaque clé correspond aux coordonnées du point.
Je ne fais pas de python mais ça ressemblerait à un truc comme :

 
Code :
  1. def fct_verif(sens, Xcoord, Ycoord, Zcoord):
  2.    if dico[Xcoord + 1][Ycoord][Zcoord] == 1 and sens != 26:
  3.       Xcoord = Xcoord + 1
  4.       Ycoord = Ycoord
  5.       Zcoord = Zcoord
  6.       l.append([Xcoord,Ycoord,Zcoord])
  7.       sens = 1
  8.    elif dico[Xcoord + 1][Ycoord + 1][Zcoord] == 1 and sens != 25:
  9.       Xcoord = Xcoord + 1
  10.       Ycoord = Ycoord + 1
  11.       Zcoord = Zcoord
  12.       l.append([Xcoord,Ycoord,Zcoord])
  13.       sens = 2
  14.    elif dico[Xcoord + 1][Ycoord - 1][Zcoord] == 1 and sens != 24:
  15.       Xcoord = Xcoord + 1
  16.       Ycoord = Ycoord - 1
  17.       Zcoord = Zcoord
  18.       l.append([Xcoord,Ycoord,Zcoord])
  19.       sens = 3
  20.    ...
  21. dico[x0][y0][z0] = 1
  22. dico[x1][y1][z1] = 1
  23. ...
  24. dico[xn][yn][zn] = 1
  25. nbre_pts = len(dico)
  26. l = [[x0,y0,z0]]
  27. sens = 1
  28. Xcoord = x0
  29. Ycoord = y0
  30. Zcoord = z0
  31. i = 0
  32. While i < nbre_pts:
  33.    fct_verif(sens, Xcoord, Ycoord, Zcoord)
  34.    i += 1
 

Il ne faut pas en fait dans les conditions des if vérifier si la valeur est égale à 1 mais si la variable existe, si elle existe alors c'est un point noir, si elle n'existe pas alors c'est un point blanc.

 

Bon il doit y avoir moyen de factoriser les else if dans la fonction mais ma tête ne veut pas pour l'instant. Il faut commencer par se représenter un cube (ton point de référence) entouré de 26 autres cubes (sur chaque face, arrête et coin de ton cube de réf) qui représentent les coordonnées entourant ton cube de référence. Marquer alors chacun de ces 26 cubes pour visualiser quel sens interdire. Si tu viens de te déplacer vers la droite tu ne dois pas considérer le cube à gauche, mais là tu as 26 directions possibles.


Message édité par MaybeEijOrNot le 03-06-2017 à 23:38:46

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301550
doctardis
Posté le 04-06-2017 à 07:57:56  profilanswer
 

Ok je vois où tu veux en venir et ça peut être une bonne idée. Malheureusement, pour minimiser le nombre de points, j'ai modifier l'image de départ pour qu'elle soit en pointillés. Donc tous les pixels ne sont pas forcément contigus avec un autre pixel noir.  
 
Pour les coordonnées, j'ai aussi fait en sorte que ce soit des valeurs entières (je sais que Python n'aime pas les float)

n°2301567
MaybeEijOr​Not
but someone at least
Posté le 04-06-2017 à 13:48:34  profilanswer
 

Du coup il faut en effet trier les points et ce n'est pas évident car en fait chaque point possède deux distances minimales, l'une avec le point qui le précède et l'autre avec le point qui le succède.
Il faut donc pouvoir trouver lequel des deux points précède et lequel succède et là c'est plus compliqué. Je pense qu'il faut faire des couples de points et ensuite agencer ces couples de manière à qu'ils se suivent.
 
Surtout que si tu travailles avec des pointillés alors ça veut aussi dire que les deux points les plus proches d'un point ne sont pas forcément le point précédant et le point suivant.
 
ex : -----    -----
 
Ici les deux points les plus proches (en vert) du point rouge sont en fait deux points qui précèdent le point rouge.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301573
doctardis
Posté le 04-06-2017 à 17:54:55  profilanswer
 

Oui c'est pour ça que je cherchais un moyen d'éliminer les points déjà utilisés. Comme ça, le seul point qui peut avoir deux distances plus faibles est le premier point, qui définira juste le sens du circuit.

n°2301575
rat de com​bat
attention rongeur méchant!
Posté le 04-06-2017 à 18:18:27  profilanswer
 

Si tu as un modèle 3D (quel format?) tu peux pas partir de ça? Il doit bien y avoir un module (pas sûr du terme) Python pour travailler avec? Ou sinon tu refait simplement ton graphique avec ses lignes continues?

n°2301576
MaybeEijOr​Not
but someone at least
Posté le 04-06-2017 à 19:05:14  profilanswer
 

doctardis a écrit :

Oui c'est pour ça que je cherchais un moyen d'éliminer les points déjà utilisés. Comme ça, le seul point qui peut avoir deux distances plus faibles est le premier point, qui définira juste le sens du circuit.

 

Oui mais comme tu ne peux pas savoir si après avoir calculé une distance minimale c'est le point suivant ou précédant qui a été utilisé tu ne peux pas l'éliminer.

 

Je me suis amusé à installer Python, alors pour avoir les couples de voisins on peut faire comme ça (j'ai volontairement non factorisé des choses pour que ce soit plus simple à suivre) :

 
Code :
  1. # pts (0,0,0) (0,1,0) (0,2,0) (0,3,0), (0,4,0) (1,4,0) (2,4,0) (3,4,0) (4,4,0) (4,3,0) (4,2,0) (4,1,0) (4,0,0) (3,0,0) (2,0,0) (1,0,0)
  2. x,y,z = [(0,0,0,0,0,1,2,3,4,4,4,4,4,3,2,1), (0,1,2,3,4,4,4,4,4,3,2,1,0,0,0,0), (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]
  3. nbre_pts = len(x)
  4. liste_pts = [[0 for j in range(2)] for i in range(nbre_pts)]                     #création d'une liste de couples de points
  5. i = 0
  6. while i < nbre_pts:                                                              #pour tous nos points
  7.    liste_dist = []
  8.    j = 0
  9.  
  10.    while j < nbre_pts:                                                           #par rapport à tous nos points
  11.       if i != j:                                                                 #on ne prend pas le cas d'un point par rapport à lui-même
  12.          distance = sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2 + (z[i] - z[j])**2) #calcul de la distance entre le point i et le point j
  13.          liste_dist.append(distance)                                             #ajout de la distance entre point i et j à une liste qui contiendra la distance du point i par rapport à tous les points j
  14.  
  15.       j += 1
  16.    mini = min(liste_dist)                                                        #recherche de la distance minimale
  17.    decal = 0
  18.    pt_min_dist = liste_dist.index(mini)                                          #numéro du point ayant la distance minimale avec le point i dans la liste des distances
  19.    if pt_min_dist >= i:                                                          #comme le cas du point i par rapport à lui-même n'est pas traité, on décale d'un index quand la valeur minimale trouvée est à la position de i ou au-dessus
  20.       decal = 1
  21.    voisin = pt_min_dist + decal                                                  #numéro du point ayant la distance minimale avec le point i dans la liste des points initiaux
  22.    liste_pts[i][0] = (x[voisin], y[voisin], z[voisin])                           #ajout des coordonnées du plus proche voisin à une liste
  23.  
  24.    liste_dist.remove(mini)                                                       #la valeur minimale est supprimée de la liste des distances
  25.  
  26.    mini = min(liste_dist)                                                        #recherche de la nouvelle distance minimale
  27.    pt_min_dist = liste_dist.index(mini)                                          #numéro du point ayant la seconde distance minimale avec le point i dans la liste des distances
  28.    if pt_min_dist >= i - 1:                                                      #comme le cas du point i par rapport à lui-même n'est pas traité, on décale d'un index quand la valeur minimale trouvée est à la position de i - 1 (on a supprimé une valeur de la liste) ou au-dessus
  29.       decal = 1
  30.    voisin = pt_min_dist + decal + 1                                              #numéro du point ayant la seconde distance minimale avec le point i dans la liste des points initiaux (toujours parce qu'une valeur a été supprimée il faut penser à décaler l'index)
  31.    liste_pts[i][1] = (x[voisin], y[voisin], z[voisin])                           #ajout des coordonnées du second plus proche voisin à une liste
  32.    del(liste_dist)                                                               #on efface la liste des distances pour le prochain point à calculer
  33.    i += 1
 

Mais après pour trouver quels points il faut garder ou éliminer puis les remettre dans l'ordre ce n'est pas évident alors que là on part de points triés dans l'ordre. :pt1cable:

 

Comme évoqué par rat de combat ou comme je cherchais à faire avant, il vaudrait mieux contourner le problème car il est très lourd et un peu complexe.


Message édité par MaybeEijOrNot le 04-06-2017 à 19:07:43

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
n°2301579
doctardis
Posté le 04-06-2017 à 20:32:20  profilanswer
 

J'ai essayé de faire ce petit programme, mais il n'arrive à me trier que juste une trentaine de points. Je ne sais pas pourquoi le programme s'arrête avant la fin, mais par contre les points triés sont correctement triés :
 

Code :
  1. import numpy as np
  2. import math as m
  3. x,y,z=np.loadtxt('points.txt', unpack=True)
  4. x0,y0,z0=x[0],y[0],z[0]
  5. def Recherche(T,x):
  6.     i=0
  7.     n=len(T)
  8.     while i<n and T[i]!=x:
  9.         i+=1
  10.     return i
  11. def Minimum(T):
  12.     n=len(T)
  13.     Min=100**5
  14.     for i in range(n):
  15.         if T[i]<Min:
  16.             Min=T[i]
  17.     return Min
  18. def TestPrésence(T,x):
  19.     i=0
  20.     n=len(T)
  21.     while i<n:
  22.         if T[i]==x:
  23.             return 1
  24.         else:
  25.             i+=1
  26.     if i==n:
  27.         return 0
  28.        
  29. ind=0
  30. ListeTriée=[[x[0],y[0],z[0]]]
  31. PointsTriés=str(x[0])+','+str(y[0])+','+str(z[0])+'\n'
  32. for j in range(len(x)):
  33.     L=[]
  34.     for i in range(0,len(x)):
  35.         if x[i]!=x0 or y[i]!=y0 or z[i]!=z0:
  36.             distance2=m.sqrt((x[i]-x0)**2+(y[i]-y0)**2+(z[i]-z0)**2)
  37.             L.append(distance2)
  38.         else:
  39.             ind=i
  40.     print(x0,y0,z0)
  41.     print(L)
  42.     Min=Minimum(L)
  43.     DistanceMin=Recherche(L,Min)
  44.     if DistanceMin>ind and DistanceMin!=len(L):
  45.         if TestPrésence(ListeTriée,[x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])==0:
  46.             ListeTriée.append([x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])
  47.             PointsTriés+=str(x[DistanceMin+1])+','+str(y[DistanceMin+1])+','+str(z[DistanceMin+1])+'\n'
  48.             x0,y0,z0=x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]
  49.         else:
  50.             for k in range(len(L)):
  51.                 L[DistanceMin+1]=100**5
  52.                 Min=Minimum(L)
  53.                 DistanceMin=Recherche(L,Min)
  54.                 if DistanceMin<ind:
  55.                     if TestPrésence(ListeTriée,[x[DistanceMin],y[DistanceMin],z[DistanceMin]])==0:
  56.                         ListeTriée.append([x[DistanceMin],y[DistanceMin],z[DistanceMin]])
  57.                         PointsTriés+=str(x[DistanceMin])+','+str(y[DistanceMin])+','+str(z[DistanceMin])+'\n'
  58.                         x0,y0,z0=x[DistanceMin],y[DistanceMin],z[DistanceMin]
  59.                         break
  60.                 else:
  61.                     if TestPrésence(ListeTriée,[x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])==0:
  62.                         ListeTriée.append([x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])
  63.                         PointsTriés+=str(x[DistanceMin+1])+','+str(y[DistanceMin+1])+','+str(z[DistanceMin+1])+'\n'
  64.                         x0,y0,z0=x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]
  65.                         break
  66.     else:
  67.         if TestPrésence(ListeTriée,[x[DistanceMin],y[DistanceMin],z[DistanceMin]])==0:
  68.             ListeTriée.append([x[DistanceMin],y[DistanceMin],z[DistanceMin]])
  69.             PointsTriés+=str(x[DistanceMin])+','+str(y[DistanceMin])+','+str(z[DistanceMin])+'\n'
  70.             x0,y0,z0=x[DistanceMin],y[DistanceMin],z[DistanceMin]
  71.         else:
  72.             for k in range (len(L)):
  73.                 L[DistanceMin]=100**5
  74.                 Min=Minimum(L)
  75.                 DistanceMin=Recherche(L,Min)
  76.                 if DistanceMin<ind:
  77.                     if TestPrésence(ListeTriée,[x[DistanceMin],y[DistanceMin],z[DistanceMin]])==0:
  78.                         ListeTriée.append([x[DistanceMin],y[DistanceMin],z[DistanceMin]])
  79.                         PointsTriés+=str(x[DistanceMin])+','+str(y[DistanceMin])+','+str(z[DistanceMin])+'\n'
  80.                         x0,y0,z0=x[DistanceMin],y[DistanceMin],z[DistanceMin]
  81.                         break
  82.                 else:
  83.                     if TestPrésence(ListeTriée,[x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])==0:
  84.                         ListeTriée.append([x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]])
  85.                         PointsTriés+=str(x[DistanceMin+1])+','+str(y[DistanceMin+1])+','+str(z[DistanceMin+1])+'\n'
  86.                         x0,y0,z0=x[DistanceMin+1],y[DistanceMin+1],z[DistanceMin+1]
  87.                         break
  88.                    
  89. """print(ListeTriée)"""
  90. fic=open('Points triés.txt','w')
  91. fic.write(PointsTriés)
  92. fic.close()


 
 
Rat de combat, mon modèle 3d est fait sous Inventor donc je ne pense pas que Python puisse intervenir là-dedans. Après, si j'ai mis en pointillés, c'est justement pour minimiser les points à trier et aussi le nombre de points pour lequel je devais trouver la hauteur. Donc je pourrais refaire avec une ligne continue mais je devrais recalculer la hauteur pour au moins 200 points je pense. Après, si je ne trouve pas d'autres solutions, j'essaierais peut-être de faire comme ça.

n°2301582
Totoche17
Posté le 04-06-2017 à 21:15:29  profilanswer
 

doctardis a écrit :


 
Rat de combat, mon modèle 3d est fait sous Inventor donc je ne pense pas que Python puisse intervenir là-dedans.


 
export en STL ascii et ça roule
 

n°2301583
MaybeEijOr​Not
but someone at least
Posté le 04-06-2017 à 21:25:06  profilanswer
 

Ben mince alors que je venais de trouver la solution, mais ça n'empêche en rien que c'est un programme lourd, petite démo :

 
Code :
  1. import os
  2. from math import sqrt
  3. # pts (0,0,0) (0,1,0) (0,2,0) (0,3,0), (0,4,0) (1,4,0) (2,4,0) (3,4,0) (4,4,0) (4,3,0) (4,2,0) (4,1,0) (4,0,0) (3,0,0) (2,0,0) (1,0,0)
  4. #x,y,z = [(0,0,0,0,0,1,2,3,4,4,4,4,4,3,2,1), (0,1,2,3,4,4,4,4,4,3,2,1,0,0,0,0), (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)]
  5. x,y,z = [(2,3,4,4,0,0,1,3,0,1,2,4,4,4,0,0), (4,0,2,1,4,3,4,4,0,0,0,0,3,4,1,2), (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,)]
  6. def voisinage(mini, liste, i, n):
  7.    decal = 0
  8.    pt_min_dist = liste.index(mini)
  9.    if pt_min_dist >= i - n:
  10.       decal = 1
  11.    voisin = pt_min_dist + decal + n
  12.    return((x[voisin], y[voisin], z[voisin]))
  13. nbre_pts = len(x)
  14. liste_pts = [[0 for j in range(2)] for i in range(nbre_pts)]
  15. i = 0
  16. while i < nbre_pts:
  17.    liste_dist = []
  18.    j = 0
  19.  
  20.    while j < nbre_pts:
  21.       if i != j:
  22.          distance = sqrt((x[i] - x[j])**2 + (y[i] - y[j])**2 + (z[i] - z[j])**2)
  23.          liste_dist.append(distance)
  24.  
  25.       j += 1
  26.    mini = min(liste_dist)
  27.    liste_pts[i][0] = voisinage(mini, liste_dist, i, 0)
  28.    liste_dist.remove(mini)
  29.    mini = min(liste_dist)
  30.    liste_pts[i][1] = voisinage(mini, liste_dist, i, 1)
  31.    del(liste_dist)
  32.    i += 1
  33. liste_ordo = []
  34. liste_ordo.append((x[0], y[0], z[0]))
  35. a,b,c = liste_pts[0][0]
  36. liste_ordo.append((a,b,c))
  37. sens = (a - x[0], b - y[0], c - z[0])
  38. i = 1
  39. while i < nbre_pts - 1:
  40.    j = 0
  41.    while j < nbre_pts:
  42.       e,f,g = liste_pts[j][0]
  43.       if (e,f,g) == (a,b,c) and sens != (a - x[j], b - y[j], c - z[j]):
  44.          k = j
  45.          sens = (x[j] - a, y[j] - b, z[j] - c)
  46.          break
  47.       e,f,g = liste_pts[j][1]
  48.       if (e,f,g) == (a,b,c) and sens != (a - x[j], b - y[j], c - z[j]):
  49.          k = j
  50.          sens = (x[j] - a, y[j] - b, z[j] - c)
  51.          break
  52.       j += 1
  53.  
  54.    a,b,c = (x[j], y[j], z[j])
  55.    liste_ordo.append((a,b,c))
  56.    i += 1
  57. liste_ini = []
  58. i = 0
  59. while i < nbre_pts:
  60.    liste_ini.append((x[i], y[i], z[i]))
  61.    i += 1
  62. print("liste des points dans le désordre :" )
  63. print(liste_ini)
  64. print(" " )
  65. print("liste des couples :" )
  66. print(liste_pts)
  67. print(" " )
  68. print("liste triée :" )
  69. print(liste_ordo)
  70. os.system("pause" )
 

Le seul moyen de l'accélérer là je crois c'est de supprimer petit à petit les couples utilisés, mais là je n'ai pas envi de réfléchir plus si tu as une autre solution.

 


EDIT : il y a surement moyen de se passer des dernières boucles mais je ne trouve pas comment récupérer l'index d'une valeur dans une liste multi-dimensionnelle. Je ne maîtrise pas encore les listes Python. :'(


Message édité par MaybeEijOrNot le 04-06-2017 à 21:39:20

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Python

  Trier des points selon leurs distances les uns aux autres

 

Sujets relatifs
Objectif trier mes ebooks !!!Courbe sinusoïdale entre deux points
[sh]Trier les manpages sur disque.Trier avec union
créer un tableau clé valeur (int) trier par valeur descTrier des groupes via jquery datatables
Trier des donnees sur deux colonnes ( ID + Version)Trier années de naissances cadets, juniors, seniors
Trier une liste de cellules[algo] trier alphabétiquement une liste chainée
Plus de sujets relatifs à : Trier des points selon leurs distances les uns aux autres


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR