Dear All

I am trying to figure out any algorithm that can identify a group of 2D points and draw the contour around them (or a polygon that includes them. I did one manually so as to explain what I need to achieve)

Also I need to isolate potential groups of points that are close enough, and define them as part of the same group or cluster.

Any ideas will be highly appreciated.

Thanks!

You can try k-means clustering, and then build the convex hull of each cluster.

Thanks Randy.

Do you have a working snippet or something where I can start with? I'll code it in C or C++

Hmm, k-means is really easy to implement; examples: http://rosettacode.org/wiki/K-means%2B%2B_clustering

The 2D convex hull is also fairly simple, and I like the implementation by Catto: http://pastebin.com/trBtQRvH (lines 62 to 119 are the hull algorithm). You can find this code by downloading Box2D's source from Catto's website.

thanks Randy again.

I have an additional question, does it worth to explore doing a non-convex hull for this? Any code for this as well ?

Well if you have a set of points and want a non-convex shape, then you have to define what "non-convex" means. Usually there are many candidate representatives of a point cloud that are "non-convex", so you'd have to somehow pick one. The convex hull is simpler to think about since it is unique for a given point set.

Solving for the number of clusters is a different problem. I found a bunch of results just by googling "k means clustering, find k", including this nice wiki page: http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

Solving for the number of clusters is a different problem. I found a bunch of results just by googling "k means clustering, find k", including this nice wiki page: http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

Thanks so much. Will take a look