I am working with a data set of over 3000 points which I need to cluster/group based on a distance criteria.

What I would like to do is build clusters from the point data which contain the maximum number of points possible to group in a 50 m radius. To be clear I don't want to group any points that are within 50 m of each other.

The way I envisage it is taking a 50 m radius polygon and centring it one by one over each point and counting how many other points fall inside the polygon. At a simple level this would return a value for each point saying how many points are within 50 m of it. I could then choose groups based on which points return the most other points with 50 m.

I would however like to be even more iterative than this as doing the above does exclude a point falling in multiple 50 m polygons. I would like a process which looks over the data and provides the most inclusive 50 m clusters for the data set as a whole.

I'm not sure if QGIS has a tool which could do this at all or whether I should look to develop a process in Excel or elsewhere.

1 Answer 1


If you are doing distance querying and interested in using Python / Scipy, you may consider using a KDTree which enables fast nearest-neighbor queries, and goes something like this:

(example uses 1 million points):

import numpy as np
from scipy.spatial import cKDTree

# random mercator points
count = int(1e6) 
xs = np.random.uniform(int(-20e6), int(20e6), count)
ys = np.random.uniform(int(-20e6), int(20e6), count)
points = np.dstack((xs, ys))[0, :]

#build tree
tree = cKDTree(points, leafsize=1000)

# find all points within 10km of Bourbon Street, HAPPY MARDI GRAS
bourbon_street = (-10026195.958134, 3498018.476606)
radius = 10000 # meters
indices = tree.query_ball_point(x=bourbon_street, r=radius)

points_within_radius = tree.data[indices] 

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.