# Contours and Cluster Algorithm

This topic is 1332 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites

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

##### 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 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 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 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 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 on other sites

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

##### 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

1. 1
2. 2
3. 3
Rutin
20
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633656
• Total Posts
3013190
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!