Jump to content
  • Advertisement
Sign in to follow this  
noobnerd

Getting the outline of a bunch of points

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

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!