Sign in to follow this  
fs1

Contours and Cluster Algorithm

Recommended Posts

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!

Edited by fs1

Share this post


Link to post
Share on other sites

Thanks Randy.

 

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

Edited by fs1

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 ?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Thanks. I'll think of the non convex hull approach later.

I have a last question: what happens if you don't know on beforehand the number of clusters? What is the best approach for determining them?

Share this post


Link to post
Share on other sites
I have been researching and my clusters are very well defined.

You can isolate and differentiate one to each other very easily at least visually.

Is there a way to determine the number of clusters as they seem to be apart one of each other very clearly?

K-means could work but my problem seems to be more simple. Maybe detecting clusters by a certain radial and distance from a plane center point?

Also, if I go ahead and use the Elbow (or other algorithm), how fast are they?

Thanks

Share this post


Link to post
Share on other sites

There are other clustering methods like hierarchical bottom-up and top-down clustering. They may be a better fit for your problem.

Though research has so far not found a method nearly as sophisticated as the human looking at the picture and "seeing" all clusters immediately, if anyone did he/she could write a paper, which would be read eagerly, by scientists and all those big data people.

Share this post


Link to post
Share on other sites
Thanks make sense.

Just last question, any c++ snippet that you can recommend that implement the Elbow or any other algorithm to find k ?

Thanks

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this