Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 0 down vote favorite
1

I have a map of stores for a retailer. I am trying to form clusters (of these stores) such that each member of a cluster is at most 5km away from any other member and any non-member is at least 10 km from any member. I also would like to create a field in the point dataset indicating to which cluster a specific store beongs to. What would be the easiest way to do this? Thanks

share|improve this question
3  
This problem needs to be framed differently, because its objectives can be contradictory. E.g., what would be a solution for two stores that are 8 km apart? They can't be part of the same cluster but they can't be put into separate clusters. – whuber♦ Oct 31 '11 at 19:37
maybe single stores 8km apart are in their own group. – Brad Nesom Oct 31 '11 at 19:54
2  
@Brad Putting stores 8 km apart into a group violates the first criterion. I gave only the simplest example of the internal contradictions. What would be done with 3 stores spaced 4 km apart on a line, for instance? Or with a bunch of stores spaced along the perimeter of a 4 km radius circle around another store? – whuber♦ Oct 31 '11 at 21:28
umut, IMHO it's a good idea to sketch (with paper and pencil) the clustering criteria, that will certainly help you to reach a better approach. Also, look for some clustering theory (en.wikipedia.org/wiki/Cluster_analysis) to understand the machine's interpretation of clusters. – Pablo Nov 1 '11 at 15:16

1 Answer

up vote 2 down vote

As @whuber says, I think you're going to need to relax your criteria, because it won't work as stands. One possible algorithm would be:

  • for each point calculate the distance to the nearest other point - in Mapinfo this can be done using the Distance Calculator tool, or in MapBasic
  • arrange these distances in descending order
  • for the smallest nearest distance, select all points that are within 5km (or whatever parameter you choose) of that point -
  • draw a convex hull around these points (a shape that encloses all points)
  • remove those points from the list and continue down the descending list of nearest distances, only selecting those points which have not already been made into a convex hull

There are automated routines to do this sort of analysis in packages like ArcGIS or R, but processing time will be significant if you have a large number of points. You will probably have to experiment to get the best results, I don't think it's possible to lay down hard rules about clusters as you have above.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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