I have a table of approx 10,000 - 20,000 dynamic points across the globe stored as lon/lat points. I want to cluster any point within (roughly) 3km of any other point into one point (and return the averaged center point of each cluster if possible). Unlike some other solutions I have seen, I do not just want points within 3km of the central cluster point, it is fine to have a point within each cluster many kilometres away from the central cluster point as long as there is a chain of points within 3km of each other joining the points together into a single chain/cluster.

The only way I can think of doing this is looping over every point, finding any other points within 3km of that point, and then recursively each of those points etc until i find all in that perticular chain/cluster, and then repeat for all the remaining un-clustered points - this would result in millions of calculations. Is there an easier way of doing this? Preferably with MYSQL 5.6 geospatial abilities, but im open to any viable solution.

  • Finding an optimal solution - i.e. with the minimum n clusters - is I believe, NP hard. One approach to finding any single sub-optimal solution is to use a Delaunay TIN. That is also rather hard to do in spherical co-ordinates - is projection an option (sowing up the 'sides' afterward)?
    – AnserGIS
    Commented May 20, 2014 at 12:51

1 Answer 1


This spatial sql example will do exactly as you ask. Ignore the fact that the question asks for linear groups, it works fine with non-linear groups as well.

Group by cluster example

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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