Ask HN: Finding a polygon given a list of random coords? | Hacker News Reader

Ask HN: Finding a polygon given a list of random coords?

4 pointsiambot9 comments

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.

You 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.

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.

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...

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

Sort them by angle from centre-point and join them in that order.

Reply on news.ycombinator.com