I have been working with a huge Map project in .NET. During working at that project, I encountered a problem. I have a plenty points with my coordinates (latitude,longitude), and I need to draw a polygon which could "fill" my points. My question is, how to choose points being outside to draw polygon by them. I attached a image file to clarify my problem -> http://postimg.org/image/fwsf0v285/
Asked
Active
Viewed 959 times
-1
-
Not a lot anyone can say. Some code would help. – Rhys Jun 25 '15 at 21:30
-
Possibility of meta effect on this question: linked from http://meta.stackoverflow.com/questions/297804/summer-time-is-it-still-acceptable-to-close-as-duplicate – Alexei Levenkov Jun 25 '15 at 21:55
-
Thanks for your answer. This is what I was looking for. – Mariusz Jun 25 '15 at 21:38
1 Answers
1
It sounds like you want a polygon that surrounds the data points. There are two algorithms available.
First is a "Convex Hull". This is a classic algorithm of computation geometry and will produce the polygon you have drawn. Imagine your data points are nails in a board, it produces a polygon resembling an elastic band that has been put around the outer data points. Convex Hulls are fast (or should be). Convex Hulls really are common, I know I've coded them up to work on the Earth's surface (ie. to take into account the Earth's curvature). Here's a simpler Euclidean example (from stackoverflow) that should get you started: Translating concave hull algorithm to c#
The alternative is an "Alpha Shape" which is sometimes known as a "Concave Hull". Basically it allows for concave (inward) curves in the side of the polygon that are larger than a specified dimension ('alpha'). For example a 'C' of data points should produce a 'C shape', whilst a convex hull would give you something more like an 'O' as will cut off the concave hollow. Alpha shapes are much more involved as they require the calculation of a Delauney Triangulation.
-
3If the question is a duplicate please vote to close rather than posting an answer that's essentially a link. – ChrisF Jun 25 '15 at 21:58
-
2My answer is a bit more than a link - the link is an implementation. I also gave a second option that produces a more accurate result depending on the situation. It wasn't clear from the OP which was the more appropriate, but they both do what he requested. – winwaed Jun 25 '15 at 22:11
-
Thank you so much for your comprehensive answer. I think, I will decide to use "Convex Hull" because, As you said, It's quite fast. – Mariusz Jun 26 '15 at 10:00