So I am definitely new to the GIS world, so bear with me if I don't know the best way to articulate my problem. That said, I am ready to learn, I would definitely welcome any direction that you all could point me in.

The problem: I have a set of coordinate points (just three attributes: name, lat, long). I hope to identify the minimum number of regions (circles with a predefined radius) that would be required to encompass XX percent of the sites (Where XX is configurable).

Initial thoughts: My thoughts were to first create clusters (of set size) of all data points, then sort the clusters by the number of points they enclose. That way I can just count the number of clusters needed (in order of priority) until they represent the desired XX percent of the points.

Thus far I have tried to do some research, but I haven't found any resources where the clustering is done within a set radius. (I have found plenty where the number of clusters is set, and the size is variable - I need the reverse of that.)

I have tried using QGIS, but I am open to any suggestions. I am new to GIS, but I have a decent knowledge of programming if that could be of any help.

  • I did a bit more searching and it would appear that the crux of what I am looking for is "distance-based clustering". However, I cannot seem to find an open/published algorithm (see the end of the section here: developers.google.com/maps/articles/…)
    – MattJ
    Jun 29, 2014 at 15:01

1 Answer 1


Given your initial thoughts I'd take a look at scipy.cluster.hierarchy to start with (or the equivalent in scikit-learn) to build the clusters based on distance.

For instance, given a numpy.array of coordinates - coords you could build a cluster based on distance like so:

import numpy as np
import scipy.cluster.hierarchy
import collections

labels = scipy.cluster.hierarchy.fclusterdata(
    threshold, #The distance of whether or not an object is in the cluster
    criterion='distance', #cluster based on distance
    method='complete' #method complete means all points must be within threshold distance of one another to be in the same cluster

cluster_count = np.bincount(labels) # count the number of entities in each cluster
sorted_labels = np.argsort(cluster_count)
sorted_labels = sorted_labels[sorted_labels != 0] #hierarchy starts labels at 0, so you want to get rid of it
sorted_count = cluster_count[sorted_labels]

progressive_sum = np.cumsum(sorted_count)
labels_you_care_about = sorted_labels[progressive_sum > number_points_excluded]

points_covered = coords[np.in1d(labels, labels_you_care_about)]

#And from here you can find the centroid and so on

For a potentially better solution you might need to look into Genetic Algorithms with a package like pyevolve which should give you better results. It might be worth asking this across on Stack Overflow as well clu

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.