Equal distribution of points to regional hubs in QGIS

Question

I have approximately 1,600 points plotted on a layer in QGIS.

On another layer, I then have 8 regional hubs plotted.

I am trying to distribute the 1,600 points among the 8 hubs, based on which hub each point is closest to and I need each hub to have the same number of points allocated (i.e. approx 200 each).

I am aiming for something that looks like the below but with an equal number of points assigned to each hub:

A couple of the hubs have now moved, so I am now needing to update the distance analyses.

I have successfully done this in the past, but I did it by calculating the distances for each of the points to all of the hubs, and then exporting the results and doing some manual analysis in Excel to work out which hub is closest, second closest etc, and then manually selecting which hub is best suited for each location.

That worked, but it was a lengthy and complicated process. This is something that I will have to do on a regular basis, so I am hoping that there is some functionality within QGIS that will help me do this more quickly and easily.

Can you point me in the right direction toward some inbuilt functionality that would help with this?

Answer 1

I'm not sure about an easily repeatable way to go about this in QGIS, but here is a potential solution using the constrained kmeans algorithm in Python:

import fiona
import numpy as np
import geopandas as gpd
from shapely.geometry import shape
from k_means_constrained import KMeansConstrained

#load in points shapefile with all points including hubs 
path = 'merged_points.shp' 
points = fiona.open(path)
geoms = [ shape(feat["geometry"]) for feat in points ]

#cast all geometries in file to new numpy array
list_arrays = [ np.array((geom.xy[0][0], geom.xy[1][0])) for geom in geoms ]
arr = np.empty((0,2)) 
for array in list_arrays:
    arr = np.append(arr, np.array([array]), axis=0)
X = np.array(arr)

# let the first 9 points be our hub points (cluster centroids)
centroid_idx = [0,1,2,3,4,5,6,7,8] 
centroids = X[centroid_idx, :]

#specify parameters for  constrained kmeans (specify cluster sizes, centroids, and number of seeds) 
km_constrained = KMeansConstrained(n_clusters=9, size_min = 56, size_max=57, init=centroids, n_init = 1, max_iter=1)
#run the clustering algorithm
km_constrained.fit(X)
#load original shapefile in geopandas
gdf = gpd.read_file('merged_points.shp')
#add new column with cluster numbers
gdf['Cluster'] = km_constrained.labels_
#write out the new shapefile
gdf.to_file('merged_points_clustered.shp')

Original Data:

Resulting Clusters: