create convex hull based on the each set of N points nearby (cluster)

2278
3
08-19-2012 10:16 PM
JackZHANG
Occasional Contributor II
Greetings,

I have 10k points which I need to build convex hull for each set of 50 points that are nearby each other. I had tried all tools in Mapping Cluster Toolset under ArcGIS Desktop 10.1 but none of them does what I'm after. I've tried some other third-party tools which allows me to create convex hull based on K-means algorithm - means I can specify the number of convex hulls to be generated but still can't see how to create convex hulls for a specified number of points. Any advise will be appreciated!
0 Kudos
3 Replies
ThomMackey
New Contributor III
So you want to partition the points into 50-point clusters based on distance, then draw a convex hull around each cluster? Sounds like a custom tool to me. Everything I know about K-means suggests that you can only specify the number of classes, not the number of points which will reside in each class. Can you just run the spacetime clustering tool with K = number of points / 50? Even that won't guarantee 50 points per class, though.

You might be able to do it by generating a spatial weights matrix file with the KNN conceptualisation with K=50. You'd have to write a bit of glue code to read in the SWM and make the MBRs. But it won't be exclusive; that is, you won't get groups of 50 coherent points; each point will have 50 neighbours, and some of those neighbours will be shared with other points. You won't get something that looks like your diagram.

I'd be surprised if there wasn't an algorithm to do this, but I don't know what it is. I guess you could do something like

  1. Assign all points to one of n/50 classes at random (where n = number of points)

  2. Calculate the centroid of each class

  3. Assign each point to the class with the nearest centroid (we're just doing K-means so far)

  4. Count number of points in each class, and redistribute them so classes are equal (this is the hard bit). I guess for classes with >= 50 points, you could "lock in" the 50 closest points, and redistribute the remainders using the same algorithm excluding the centroid they are technically closest to.

  5. GOTO 2 until convergence (ie. average distance doesn't change very much)


Are you able to share why you want to do this? It sounds interesting.
0 Kudos
JeffreyEvans
Occasional Contributor III
If you have overlap in the groups (points) that you want to cluster than a KNN based clustering approach will be somewhat nonsensical or arbitrary. If your data follows the example image that you provided then you could just run a buffer (dissolved) with your desired distance. If you want an actual convex hull just assign you points back to the buffers to get unique IDs and then iterate through each group and create a convex hull object using the appropriate ArcGIS tool.
0 Kudos
JackZHANG
Occasional Contributor II
Thank you Thom, Thank you Jeffrey.

Thom,
You�??re right the hardest part is to redistribute the points from K-Mean cluster to the nearby cluster. The idea is we have 10k hydrants scattered in the town for inspection. We need to slice the inspection area into sub-areas that each have 50 hydrants close to each other, so that we can allocated the inspection works to our scopers. I know this might sound like a ArcGIS Logistic or similar study but we don�??t have access to these extension/tools. I guess there�??re some other scenarios that have similar required as mine, each create census areas based on each of 200 nearby households?


Jeffrey,
There�??re no overlapping in the dataset. As mentioned above the issue in my scenario is there�??s no such �??desired distance�?� exists.
0 Kudos