Getting the outline of a bunch of points

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

Recommended Posts

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

Share on other sites
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.

Share on other sites
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.

Share on other sites
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.]

Share on other sites
@ 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

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

Share on other sites
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.

Share on other sites

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

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 13
• 30
• 9
• 16
• 12