# Fastest way to extract the neighbours of a GPS point among millions of other points?

I have millions of GPS point located in the same city. I would like to make spatial bins that contain adjacent points together (GPS points that are within a specific range of each other). I have a shapefile of that city and the GPS points located in it. Given the enormous amount of data, I'm looking for the least-cost way to do so.

I have already considered making a distances matrix but its size would grow quadratically with the size of the dataset.

I have also considered making a bounding box around that point and compare its top-left and bottom-right coordinates to all of the points in the dataset but it proved high temporal complexity.

I'm quite new to GeoPandas and I was wondering if there's a way to extract neighbours of a given point from the plot itself? Like an interactive map or something like this.

PS: The plot below contains a sample of data (not all of it)

• Have you tried the tree algorithm in shapely? It will do distance lookups without making distance matrices of every point, I suspect it can handle millions of points but I'm not 100% positive. shapely.readthedocs.io/en/stable/manual.html#str-packed-r-tree Dec 12, 2021 at 13:52
• Can you add a screenshot showing the data? Are the points grouped spatially or more "random"?
– BERA
Dec 12, 2021 at 14:02
• Are you looking for a "bin" of fixed radius around each point containing all points within that distance (and hence millions of bins)? Or are you trying to cluster points so that each point in the cluster is within some distance of all the others? If it's clusters, how do you want to determine which points are clustered together, since there are many arrangements that satisfy a given distance criterion. Do you want to pre-compute the entire arrangement, or find the bin/cluster dynamically for a given point? Dec 12, 2021 at 16:07
• @Shawn I did try it but as you said I have millions of GPS points.
– mira
Dec 13, 2021 at 15:04
• @BERA The GPS points are dispersed in the same city, so they are not grouped
– mira
Dec 13, 2021 at 15:06

There are many clustering algorithms you can use, for example DBSCAN:

Very large n_samples, medium n_clusters

``````import geopandas as gpd
import pandas as pd
from sklearn.cluster import DBSCAN
import datetime
start = datetime.datetime.now()

in_shapefile = r'/home/bera/Desktop/gistemp/1000000_random_points.shp'
out_shapefile = r'/home/bera/Desktop/gistemp/1000000_random_points_clustered.shp'

df['xcoord'] = df.geometry.apply(lambda x: x.x) #Add a x coordinate column
df['ycoord'] = df.geometry.apply(lambda x: x.y) #and y

coords = df[['xcoord','ycoord']].values #Create a numpy array of x and y coordinate
db = DBSCAN(eps=30, min_samples=1).fit(coords) #cluster them. eps is distance between points, adjust it
cluster_labels = pd.Series(db.labels_).rename('cluster')  #.labels_ creates a numpy array. Convert to a series and rename it

df = pd.concat([df, cluster_labels], axis=1) #Add the cluster series to your dataframe

df2 = df.loc[(df.xcoord<666148) & (df.ycoord>6587010)] #I create a small sample to visualize in QGIS by selecting points in the upper left corner
df2[['geometry','cluster']].to_file(out_shapefile.replace('.shp','_sample_.shp')) #Export

stop = datetime.datetime.now()
print((stop-start).seconds, ' seconds')
``````

With 1 million points it takes 50 s.

My points are completely random so alot of them ends up in one cluster:

• Unfortunately, in the response to my comment which came after your post, the OP is not looking for clusters, but rather fixed radius bins around every point. Dec 13, 2021 at 18:59