• Create Account

## Getting the outline of a bunch of points

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1noobnerd  Members

128
Like
0Likes
Like

Posted 10 January 2012 - 05:27 PM

Hi there!

For a game i am making, I would need to know which points of a bunch of points make up the ''outline".

I have about one hundred points of which the xy coordinates are known. And i would need to get the outermost points ids. I could then Draw an outline for the bunch.

Any suggestions appreciated.

I have tried comparing distances and vectors from a centerpoint but my results have not been satisfactory

### #2RulerOfNothing  Members

1369
Like
0Likes
Like

Posted 10 January 2012 - 05:36 PM

I believe what you want is called the convex hull of the set of points, and there are some algorithms that will allow you to get the convex hull of a set of points.

### #3Emergent  Members

982
Like
0Likes
Like

Posted 10 January 2012 - 07:58 PM

Unless the shapes you're looking for are all convex, I don't think you want the convex hull. The following might look better:

1. Compute a Delaunay triangulation of the points.
2. Remove any edge longer than a given threshold.
3. Classify any remaining edge shared by fewer than two triangles as "exterior."

The threshold in 2 is your tunable parameter.

### #4Emergent  Members

982
Like
0Likes
Like

Posted 10 January 2012 - 08:11 PM

The method of my previous post produces results like the attached image. Note that "outlying" points are ignored entirely (maybe good, maybe bad -- but something I hadn't thought about).

[EDIT: In fact, outlying points are not ignored, depending on how you do it. In the code that I used to generate this image, I deleted every triangle having at least one edge of length greater than the threshold (this was easy to do with the API I had). Had I instead kept "orphan" edges -- perhaps as degenerate triangles -- then those two points in the upper right would have been connected to the rest of the outline, but only by single line segments.]

### #5h4tt3n  Members

1917
Like
0Likes
Like

Posted 11 January 2012 - 12:22 AM

@ Emergent. I've been trying to implement something like this without satisfactory result. Would you care to explain this i more detail or perhaps link to some good reference material about that topic.

Regards,
Mike

### #6noobnerd  Members

128
Like
0Likes
Like

Posted 11 January 2012 - 02:49 AM

thank you all for your replies!

it will take me a moment to get all of this sorted out and understood.

@ruler of nothing : looks interesting and i think i will have a look at it but at the moment i need to get shapes that arent entirely convex.

@emergent : looks pretty much like just what i wanted! in my game there is no risk for "orphan" points an if there were they arent important so it just good that it "skips" them, i will probably use the method you proposed but it might take some time to figure it out

### #7Álvaro  Members

20254
Like
0Likes
Like

Posted 11 January 2012 - 07:58 AM

Similarly to what Emergent proposed, I would compute the Delaunay triangulation and then iteratively remove the triangle with a smallest angle among the ones that wouldn't leave any orphans and have an edge on the boundary. I am not sure what the stopping condition should be; it requires experimentation.

### #8Emergent  Members

982
Like
0Likes
Like

Posted 11 January 2012 - 02:08 PM

@ Emergent. I've been trying to implement something like this without satisfactory result. Would you care to explain this i more detail or perhaps link to some good reference material about that topic.

All the heavy lifting was done for me by MATLAB's "delaunay" function.

The MATLAB script I used to generate the earlier image is attached with a .txt file extension. Just a quick-and-dirty proof-of-concept.

#### Attached Files

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.