7 replies to this topic

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

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

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.

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.

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.

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.]

[EDIT: In fact, outlying points are

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

Regards,

Mike

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

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

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.

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.