Clustering point data to obtain maximum count groups using QGIS?

Question

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.

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]