Ask HN: Finding a polygon given a list of random coords?
4 comments
You may mean "convex hull"; you should be able to find 2D and 3D algorithms easily (Wikipedia?).
Graphically:
Graphically:
X--X X-X X--X--X-X
| | / / | /
X X- | X X |
\ --X \ --X
X--/ X--/
Possible polygon Convex hull
based on the points of the points
marked X marked Xyes thats exactly what im looking for, thanks for the terminology, it makes it easier to find what I need if i actually know what I'm looking for.
Finding the convex hull of a collection of points is a studied problem, so you can use an existing solution:
http://en.wikipedia.org/wiki/Convex_hull_algorithms
Alternatively, willvarfar's approach is faster for large n, but the polygon won't be as pretty.
http://en.wikipedia.org/wiki/Convex_hull_algorithms
Alternatively, willvarfar's approach is faster for large n, but the polygon won't be as pretty.
thank you, I appreciated you taking the time to answer. As with other comments on this thead, this is exactly the info I was looking for.
If there's no restriction other than not wanting the lines to cross, then I'd find the centre of the polygon by taking the average of the list of points, then visiting those points in a clockwise direction.
If you need to restrict yourself to following streets on the map, it might be a bit trickier...
If you need to restrict yourself to following streets on the map, it might be a bit trickier...
streets dont matter, and thanks for the answer, are there any libraries for doing calulation like this, or would i have to write it manually?
I've no idea, sorry.
OpenCV
http://opencv.willowgarage.com/documentation/cpp/structural_...
cv::convexHull
http://opencv.willowgarage.com/documentation/cpp/structural_...
cv::convexHull
Sort them by angle from centre-point and join them in that order.
Is there any way of finding a polygon that would contain all of a given list of points? without any intersections.
I'm hoping to use it in an app built on Google's Maps API v3. Any help/links would be much appreciated.