Discussion :

[rabeh.ram]

salut a tous je cherche script python qui donne la plus proche deux points dans une liste des coordonnées et je ce trouvé sa dans ce lien :
https://www.geeksforgeeks.org/closes...uer-algorithm/
mais Le problème qui je trouve dans ce scripts ne nous donne que la min_distance sans donner les nom des points, et le deuxieme problème est que je ne savais pas comment réécrire ce script pour charger la liste de coordonnées depuis un fichier texte


La liste des points :

[wiztricks]

Salut,

je cherche script python qui donne la plus proche deux points dans une liste des coordonnées

Ici, c'est plutôt pour de l'aide à programmer ce genre de script.
Commencer par regarder ce qui se fait sur Internet c'est bien, mais après, il faut se l'approprier (comprendre comment çà marche pour l'adapter).
Ce qui suppose que vous avez essayé d'en faire quelque chose avec plus ou moins de succès.

- W

[Sve@r]

Bonjour

et le deuxieme problème est que je ne savais pas comment réécrire ce script pour charger la liste de coordonnées depuis un fichier texte

Les points de l'exemple sont ici P = [Point(2, 3), Point(12, 30), Point(40, 50), Point(5, 1), Point(12, 10), Point(3, 4)].
Il suffit donc de lire le fichier texte, découper chaque ligne (si on admet qu'une ligne contient le x et y d'un point) pour recréer le tableau. Un coup de split(), de int() et de append() et ça le fait (pour peu qu'on ait au-moins des connaissances de base élémentaires en Python)...

[wiztricks]

Salut,

Il suffit donc de lire le fichier texte, découper chaque ligne (si on admet qu'une ligne contient le x et y d'un point) pour recréer le tableau.

Il serait aussi assez sage de mettre le code dans un module, histoire de mettre un frein à l'envie d'y toucher...

Et créer une classe héritant de Point pour lui ajouter l'attribut name et éventuellement une méthode __str__ pour afficher le résultat.

- W

[Sve@r]

Il serait aussi assez sage de mettre le code dans un module, histoire de mettre un frein à l'envie d'y toucher...

Là je ne suis pas trop d'accord. Il s'agit d'un exemple. Les exemples sont justement faits pour qu'on les regarde, qu'on se les approprie et qu'on y touche dans tous les sens pour en comprendre le fonctionnement...

[wiztricks]

Salut,

Là je ne suis pas trop d'accord. Il s'agit d'un exemple. Les exemples sont justement faits pour qu'on les regarde, qu'on se les approprie et qu'on y touche dans tous les sens pour en comprendre le fonctionnement...

Est ce que vous étudiez le source de toutes les bibliothèques que vous utilisez?
Peut être de temps en temps, mais à partir du moment où çà fait le boulot, on se contente de les utiliser sans trop s'intéresser à leurs détails.

Après on peut avoir des soucis spécifiques qui font qu'on va s'intéresser au code (parce que çà rame) à l'algo. utilisé pour le comparer à d'autres... mais si au départ, on cherche juste à mouliner les données d'un fichier CSV avec un algo/code similaire on va éviter d'y toucher.

note: si on écrit une fonction qui... une fois écrite, c'est pour s'en servir pas pour revoir sans cesse le code qu'elle exécute sauf problème qui motive à revisiter son contenu.

Ici on doit quand même un peu y toucher pour retourner les 2 Points en plus de la distance minimale. Ce qui demande un petit travail... ou trouver un code qui le fait déjà comme fastpair.

- W

[rabeh.ram]

Salut,

Ici on doit quand même un peu y toucher pour retourner les 2 Points en plus de la distance minimale. Ce qui demande un petit travail... ou trouver un code qui le fait déjà comme fastpair.

- W

Oui, ce code doit encore être modifié par un professionnel Python comme vous

[rabeh.ram]

Bonjour

Les points de l'exemple sont ici P = [Point(2, 3), Point(12, 30), Point(40, 50), Point(5, 1), Point(12, 10), Point(3, 4)].
Il suffit donc de lire le fichier texte, découper chaque ligne (si on admet qu'une ligne contient le x et y d'un point) pour recréer le tableau. Un coup de split(), de int() et de append() et ça le fait (pour peu qu'on ait au-moins des connaissances de base élémentaires en Python)...

Oui, j'ai essayé de travailler avec cette idée avant, mais le problème est dans le nom du point dans le code est constante mais dans mon ficher elle est variable

[Sve@r]

Oui, j'ai essayé de travailler avec cette idée avant, mais le problème est dans le nom du point dans le code est constante mais dans mon ficher elle est variable

Wiztricks a donné un point de départ

1. modifier la classe "point" pour lui rajouter un attribut "name"
   

   Code python :

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

   1
   2
   3
   4
   5
   class Point: 
       def __init__(self, x, y, name=None): 
           self.x = x 
           self.y = y 
           self.name = name

2. rajouter ce name dans la liste des points => P = [Point(2, 3, "truc"), Point(12, 30, "chose"), Point(40, 50, "machin"), Point(5, 1, "toto"), Point(12, 10, "titi"), Point(3, 4," tata")]

Ensuite quand on a trouvé les points les plus proches, on a leur nom directement.

Oui, ce code doit encore être modifié par un professionnel Python comme vous

Ou bien plus simplement par un type qui a fait l'effort de télécharger un tutoriel et de le lire pour s'imprégner des bases minimales du langage...

[jurassic pork]

hello,
bon j'ai fait un essai pour 10000 points en utilisant les fonctions suivantes :
1 - Python/divide_and_conquer/closest_pair_of_points/closest_pair_of_points (ne renvoie pas les points) disponible ici (fichier closest_pair_of_points.py)
2 - Tosha1409/Closest_pair_of_points/shortest_distance2/search_pair disponible ici (fichier shortest_distance2.py)
3 - Fastpair
Voici les résultats des temps d'exécution :

temps de génération des points : 0.0451
algo search_pair : 0.111 s - dmin : 2.0678445297289567
algo closest_pair_of_points : 1.19 s - dmin : 2.0678445297289567
algo fast_pair : 1.99e+03 s - dmin : 2.0678445297289567

Il n'y a pas photo, c'est la fonction search_pair qui est la plus intéressante : la plus rapide et renvoie les points. FastPair n'est pas appropriée pour un grand nombre de points.
Voici le code de test :

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#from fastpair import FastPair
import random
import time
import closest_pair_of_points
import shortest_distance2
 
 
def rand_tuple():
    return tuple([round(random.uniform(540000.0, 580000.0), 3), 
                         round(random.uniform(3610000.00, 3650000.0), 3)] )
 
import matplotlib.pyplot as plt
tps1 = time.clock()
points = [rand_tuple() for _ in range(10000)]  # 2D points
tps2 = time.clock()
print('temps de génération des points : {:.3}'.format(tps2-tps1))
tps1 = time.clock()
points.sort() #sorting points
p,q = points[0],points[1] #taking first p,q
m=shortest_distance2.lenght (points[0],points[1]) #and first distance (as current minimum)
pt,pt2,distance= shortest_distance2.search_pair(points,p,q,m) #finding and printing results
tps2 = time.clock()
print('algo search_pair : {:.3} s - dmin : {}'.format(tps2-tps1, distance))
tps1 = time.clock()
distance2 = closest_pair_of_points.closest_pair_of_points(points, len(points))
tps2 = time.clock()
print('algo closest_pair_of_points : {:.3} s - dmin : {}'.format(tps2-tps1,  distance2))
#tps1 = time.clock()
#fp = FastPair().build(points)
#dist, (a, b) = fp.closest_pair()
#tps2 = time.clock()
#print('algo fast_pair : {:.3} s - dmin : {}'.format(tps2-tps1,  dist))
plt.figure()
plt.scatter(*zip(*points))
plt.scatter(*zip(pt, pt2), color="red")
plt.title("Points : {:},{} \n Distance : {:.2} .".format(pt,pt2,  distance))
plt.show()

et voici le résultat graphique :






Ami calmant, J.P

[jurassic pork]

hello,

salut a tous je cherche script python qui donne la plus proche deux points dans une liste des coordonnées

combien de points y-a-t-il à analyser ?
Pour chercher les points les plus proches tu peux essayer d'utiliser la classe FastPair de licence MIT disponible ici
Voici un exemple d'utilisation où l'on génère 100 points de façon aléatoire et où l'on recherche les points les plus proches :

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
 
from fastpair import FastPair
import random
import matplotlib.pyplot as plt
 
 
def rand_tuple():
    return tuple([round(random.uniform(540000.0, 580000.0), 3), round(random.uniform(3610000.00, 3650000.0), 3)] )
 
 
points = [rand_tuple() for _ in range(100)]  # 2D points
fp = FastPair().build(points)
dist, (a, b) = fp.closest_pair()
 
 
plt.figure()
plt.scatter(*zip(*fp.points))
plt.scatter(*zip(a, b), color="red")
plt.title("Points : {:},{} \n Distance : {:.2} .".format(a,b,  dist))
plt.show()

et voici le résultat :


Ami calmant, J.P

[rabeh.ram]

hello,

combien de points y-a-t-il à analyser ?
Ami calmant, J.P

Merci pour votre réponse
le numbre des points ne pas fixe mais a estimation 10000 au minmant