Help.
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.
Ask HN: Finding a polygon given a list of random coords?
1–10 of 10 posts
Re: Ask HN: Finding a polygon given a list of random coords?
#2If 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...
Re: Ask HN: Finding a polygon given a list of random coords?
#3Sort them by angle from centre-point and join them in that order.
Re: Ask HN: Finding a polygon given a list of random coords?
#4If 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...
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?
Re: Ask HN: Finding a polygon given a list of random coords?
#5You may mean "convex hull"; you should be able to find 2D and 3D algorithms easily (Wikipedia?).
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 XRe: Ask HN: Finding a polygon given a list of random coords?
#6Finding 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.
Re: Ask HN: Finding a polygon given a list of random coords?
#7If 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...
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.
Re: Ask HN: Finding a polygon given a list of random coords?
#8You may mean "convex hull"; you should be able to find 2D and 3D algorithms easily (Wikipedia?). 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 X
yes 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.
Re: Ask HN: Finding a polygon given a list of random coords?
#9Finding 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.
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.
Re: Ask HN: Finding a polygon given a list of random coords?
#10Earlier quoted context omitted.
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