# How to find Clusters of N Points Within X Distance?

We have tried two methods of cluster analysis:

... but neither meets our specification which has these 3 parameters:

• a Set of Point features
• N points within a Cluster
• X distance band to look in

For example "find me the points where each cluster has 10 points within 50 meters" or something to that effect.

ArcGIS 10 has the two tools I’ve linked above but neither seems to address the N points within a cluster part.

Can our requirements be met with other tools in ArcGIS? Is what I am calling cluster analysis known as a particular clustering type?

We did have a version of this in another application but I really wanted to use the tools within ArcGIS.

-
"promised to the client without my knowledge" ... I feel your pain. Would an arcobjects solution be acceptable? – Kirk Kuykendall Mar 4 '11 at 15:46
Would it not be possible to create the clusters and then process out those that do not meet your criteria? That is to say (and I ask due to a lack of experience in this analysis), would the clusters change if they were given this third criteria before the analysis? – Nathanus Mar 4 '11 at 16:05
@Kirk Kuykendall. ArcObjects might not be possible as it needs to be exposed as a geoprocessing service via arcgis 10 server. – Hath Mar 7 '11 at 12:08
Does the cluster need to be based on a circle, or can it be rectangular. Creating a hash from coordinates such that the hash code for all points that are in the same 50x50 box are the same is easy. – Kirk Kuykendall Mar 7 '11 at 19:05
@ Kirk - has to be a circle i think. – Hath Mar 9 '11 at 10:36

Try using the Buffer tool to buffer the points to a tolerance, dissolve to create single polygons for each cluster, and then use a join to count the number of points in the cluster.

Then use the ratio between the area of the cluster and the number of points to apply your parameters.

-
+1 This approach should work, but I don't see where area comes into the solution. – whuber Mar 4 '11 at 17:28
area/count gives a measure of the density within a cluster. This would help to eliminate linear chains of points that shouldn't be considered as clusters. – Matthew Snape Mar 4 '11 at 19:18
OK, but the problem statement does not require that. It only asks for "10 points within 50 meters," e.g.. If you buffer points by 50/2 = 25 meters, then any place where there are 10 or more overlaps qualifies as the center of such a cluster. Done! – whuber Mar 4 '11 at 22:13
When you mean 'join' do you spefically mean a spatial join. – Hath Mar 9 '11 at 10:55

Try going to the first point, then creating a recursive function, which checks for points within the distance, and peforms the same operation on that, which looks for points within the distance, and performs the same operation on that, etc.

I have just solved a similar issue, in that I had to find a set of points conforming to a certain clause; I built a recursive function to find if there were points connected within 8 cells (N,NW,W,SW,S,SE,E,NE) and called the same function for that point. If the list returned contained x points, I aggregate a polygon around it.

-

This can be accomplished using ArcObjects without much difficulty.

Create a maptopology and add the point featureclass to it. Set the clustertolerance based on your cluster distance (50), and build the cache.

Loop through each node in the maptopology.cache.nodes. If ITopologyNode.Parents.Count > 10 then do whatever you need to do.

I've done something similar for a custom layer that draws each cluster point with a symbol whose color is based on the number of point features in the cluster. Performance was acceptable since the features are cached in memory - rebuilding the cache is the expensive part.

Similar to code posted here.

-
Would it be possible in python? – Hath Mar 9 '11 at 9:26
I'm thinking not. Not that familiar with arcobjects sdk and not entirely sure of the licence requirements for using it either. – Hath Mar 9 '11 at 10:21

i dont have any usage information on ArcGIS since i only use OpenSource Software. But i think that this an be accomplished, with Openlayers. There is a cluster strategy example, which you can find here: http://openlayers.org/dev/examples/strategy-cluster.html

-
-1 OP is asking for a arcgis way of doing this. Giving a OpenLayers way isn't really going to help. – Nathan W Mar 4 '11 at 14:02
But the openlayers approach couldnt help him find out the way it is done to implement it in arcgis ?? – 1amtoo1337 Mar 4 '11 at 14:08
I agree with the comment and like your approach: often we have to look outside our comfort zone for ideas and inspiration. But I would find your reply more useful if you could explain how this example is connected to the particular question asked here. Although the question and the example share the word "cluster," it is not evident that they use it in the same sense or address sufficiently similar problems. – whuber Mar 5 '11 at 22:26
I upvoted this as I was looking for an opensource way of doing this and eventhough the post wanted arcgis, I have often found that a solution in other GIS systems can help you find a solution in your software of choice by using it's tools in a way that is not common. – GeorgeC Jan 14 at 6:00