I am looking for an algorithm that will allow me to find the centers of clusters of an arbitrary radius, such that all coordinates are covered.

Currently, I am doing a very basic routine where I randomize my array, loop through it, and find the distance from one point to all points - if any point falls within my radius, it gets removed from the array and the loop starts over. I then do this x amount of times and keep the best (smallest) attempt of coordinates. Naturally this is very inefficient and also doesnt produce the best results, as sometimes there will be two or more points slightly farther apart than the given radius but a midpoint between them will cover them all.

I have looked around at other clustering algorithms such as kmeans and they don't seem to really handle my case (covering points with a maximum radius), but this is also my first time working on a project anything like this so I am pretty new to dealing with maps and coordinates.

Currently I am usually working with about 500-2000 points spread out across maybe 50 square miles, and keeping with a 500m radius

I am using a leaflet frontend and pulling coordinates from a database using ajax and PHP, so something that could be done either in javascript or PHP would be ideal. My current solution runs on the server using PHP since front end processing capabilties vary, but performance is not my biggest concern right now.

  • Could you give a little more detail on your problem definition? Are you trying to find the minimum number of clusters of a fixed maximum radius covering all your points? (This is likely an optimisation problem). Also this answer may be relevant math.stackexchange.com/questions/1176493/… – Open Door Logistics Nov 5 '18 at 7:55