voisins les plus proches

J'ai besoin d'aide pour établir un script python qui est peremte de trouver et sur une dataframe df=["point_name","x","y"] tous les points voisins les plus proches à une distance spécifique comme l'exmple sur l'image en dessous (distance <= 30)

Pièce jointe 615347

Salut,

Vous pouvez le faire "brute force" en calculant les distances entre chaque point... ou chercher un algorithme qui va limiter le nombre de distances à calculer.

Dans tous les cas, choisir l'algo. n'est pas un sujet Python et lorsque vous l'aurez choisi, postez comment vous avez essayé de le traduire serait un plus pour montrer que vous ne voulez pas qu'on réfléchisse et code à votre place.

- W

hello,
une piste ici : Recherche_des_deux_points_les_plus_rapprochés
Avec du code en python ici
A Voir si cela est adapté pour chercher plusieurs valeurs relatives à une condition.
​Ami calmant, J.P

Salut !

Peut-être avec numpy ?

https://codereview.stackexchange.com...points#tab-top

Après je méconnais grandement numpy donc à prendre avec des pincettes. Le code pourrait correspondre après il faut le comprendre :koi:

np.asarray : https://numpy.org/doc/stable/referen...y.asarray.html
np.einsum : https://numpy.org/doc/stable/referen...py.einsum.html
https://www.drgoulu.com/2016/01/17/einsum/
np.argmin : https://numpy.org/doc/stable/referen...py.argmin.html

Ne pas me demander d'explications, stp ! :mouarf:

---

:zoubi:

Sinon scikit-learn propose directement l'algo knn

Code:

---

from sklearn.neighbors import KNeighborsClassifier

---

Mais tu n'as pas besoin de ça. Un algo possible:
Faire un sort sur x de la liste des points
Puis boucler sur chaque point
Pour chaque point x,y,
- extraire la sous liste des points xi,yi qui ont xi dans l'intervalle [x-d, x+d]
- pour chaque point de la sous-liste:
tester la distance avec le point x,y

Mais comme le dit Wiztricks, ici c'est un forum Python où on t'aidera surtout pour trouver la bonne compréhension de liste pour extraire les sous-listes

Hello,
pour travailler sur un cas concret, voilà ce que j'ai "bricolé" :
Grâce à la fonction Overpass du module overpy je vais chercher par internet sur Openstreetmap les coordonnées de toutes les stations de métro en France. J'utilise aussi le module haversine pour calculer la distance entre deux coordonnées. Ensuite je dessine tous ces points dans matplotlib. Le module mplcursors quand à lui permet d'annoter les points dans matplotlib. Pour l'instant je recherche "bestialement" toutes les stations de métro qui sont éloignées entre elles de 400 mètres à 450 mètres et je trace une ligne rouge entre ces stations.
voici le code :

Code:

---

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 39 40 41

import numpy as np import matplotlib.pyplot as plt import overpy import mplcursors from haversine import haversine, Unit import time start = time.time() api = overpy.Overpass() r = api.query(""" area["ISO3166-1"="FR"][admin_level=2]; (node["station"="subway"](area);); out center; """) end = time.time() print("temps de récupération des coordonnées : " + str(end-start) + " secondes") start = time.time() noms = [] coords = [] coords += [(float(node.lon), float(node.lat)) for node in r.nodes] noms += [node.tags['name'] for node in r.nodes] X = np.array(coords) plt.plot(X[:, 0], X[:, 1], 'o') plt.title('Stations de métro en France') plt.xlabel('Longitude') plt.ylabel('Latitude') plt.axis('equal') mplcursors.cursor(hover=True).connect("add", lambda sel: sel.annotation.set_text(noms[sel.index])) end = time.time() print("temps de tracé des coordonnées : " + str(end-start) + " secondes") resultat=[] start = time.time() for pt1 in coords: for pt2 in coords: res = haversine(pt1, pt2, unit='m') if 400 < res < 450: plt.plot([pt1[0],pt2[0]],[pt1[1],pt2[1]],color = 'red', linestyle = 'solid') resultat.append(res) end = time.time() print("temps de calcul des distances : " + str(end-start) + " secondes") plt.show()

---

Voici ce que cela donne :
Pièce jointe 615472
Comme on peut le constater il y a 6 zones qui correspondent aux six métros actuels (Paris, Marseille, Lyon, Lille, Toulouse, Rennes)
Et pour les stations dont l'éloignement est entre 400m et 450m dans la zone de Paris :
Pièce jointe 615471

Voici les temps des différentes parties du programme sur mon ordinateur :

Citation:

---

temps de récupération des coordonnées : 69.56823968887329 secondes
temps de tracé des coordonnées : 0.031241655349731445 secondes
temps de calcul des distances : 0.7185783386230469 secondes

---

Comme on peut le constater il faut plus d'une minute pour récupérer les coordonnées chez OpenStreetmap.




Le but du jeu est d'optimiser la partie recherche des stations par éloignement . Déjà éliminer les redondances -> ex p1,p1 (p1,p2 p2,p1) etc... et puis trouver le meilleur algorithme.
A vous de jouer ! ;)

Ami calmant, J.P

Merci beaucoup pour tout le monde ; le probleme est résolu par l'utilisation de spatial.cKDTree