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
Getting the outline of a bunch of points
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.
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.
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 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.]
@ 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
Author
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
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.
@ 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
