5

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

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

Points and hubs on the map

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:

previous version

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?

4
  • 1
    Have a look at K-means clustering: docs.qgis.org/3.16/de/docs/user_manual/processing_algs/qgis/…
    – Babel
    Sep 27 '21 at 16:28
  • 1
    Just an idea, which is bound to not entirely address your question: have you considered creating Thiessen polygons around the hubs, and then intersecting the polygons and the points to allocate the latter to the hub to which they are closer?
    – NewAtGis
    Sep 27 '21 at 16:47
  • If you have access to postgis, you should check out st_clusterKMEANS postgis.net/docs/ST_ClusterKMeans.html
    – jbalk
    Sep 27 '21 at 17:49
  • 1
    Do you have an idea for an algorithm to solve this in words or pseudocode? I spent some hours of thinking about that now, but never end up all hubs having the same pointcount or points within a suitable distance. I guess there needs to be some decision metric like a rank for each point which hub it should get. Also I tend to say that there are several iteration steps required to solve that issue properly.
    – MrXsquared
    Sep 27 '21 at 23:06
2

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: enter image description here

Resulting Clusters: enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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