|
Bas de page | |
---|---|
Auteur | Sujet : Trier des points selon leurs distances les uns aux autres |
Publicité | Posté le 03-06-2017 à 16:25:23 |
MaybeEijOrNot but someone at least | Bonjour,
--------------- C'est en écrivant n'importe quoi qu'on devient n'importe qui. |
doctardis | 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.
|
MaybeEijOrNot but someone at least | 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.
--------------- C'est en écrivant n'importe quoi qu'on devient n'importe qui. |
doctardis | J'avais prévu que ça prendrait pas mal de mémoire et aussi de temps à se résoudre. |
MaybeEijOrNot but someone at least | 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. |
doctardis | 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..).
|
MaybeEijOrNot but someone at least | 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. 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. |
doctardis | 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"... |
MaybeEijOrNot but someone at least | Comment as-tu fais pour récupérer les coordonnées des pixels noirs?
--------------- C'est en écrivant n'importe quoi qu'on devient n'importe qui. |
Publicité | Posté le 03-06-2017 à 21:41:28 |
doctardis | 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. |
MaybeEijOrNot but someone at least | 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.
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. |
doctardis | 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. |
MaybeEijOrNot but someone at least | 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.
--------------- C'est en écrivant n'importe quoi qu'on devient n'importe qui. |
doctardis | 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. |
rat de combat attention rongeur méchant! | 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?
|
MaybeEijOrNot but someone at least |
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) :
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. 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. |
doctardis | 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 :
|
Totoche17 |
|
MaybeEijOrNot but someone at least | 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 :
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.
Message édité par MaybeEijOrNot le 04-06-2017 à 21:39:20 --------------- C'est en écrivant n'importe quoi qu'on devient n'importe qui. |
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 desc | Trier 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 |