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

https://news.ycombinator.com/item?id=2854427

by iambot • 15 years ago

4 9 15 years ago

news.ycombinator.com

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.

mooism22• 15 years ago

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

iambot3• 15 years ago

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?

mooism22• 15 years ago

I've no idea, sorry.

willvarfar• 15 years ago

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

JoachimSchipper• 15 years ago

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

iambot3• 15 years ago

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.

redxaxder• 15 years ago

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.

iambot3• 15 years ago

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.

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

Related Stories