Random Polygon

[kurtybain]

Hi, what I am trying to do is to get some positions(lat,lon) and build
a polygon with this positions. The problem is that these locations are
disordered, so that when building the polygon, there are
intersections.

What i pretend to do is to create a polygon with "random" (if they can
be called random) positions without intersections.

Thanks in advance.

[kyonn]

I've not the answer, tell us more : How do you randomly get your
coordinates ? And why ? Couldn't you build your polygon in a more
orderly manner ?

Your problem is in fact not easy to solve. It deals with the point-in-
polygon algorithm (http://en.wikipedia.org/wiki/Point_in_polygon) or
polygon intersection (http://mathworld.wolfram.com/
PolygonIntersection.html)

[Rossko]

> Hi, what I am trying to do is to get some positions(lat,lon) and build
> a polygon with this positions. The problem is that these locations are
> disordered, so that when building the polygon, there are
> intersections.

As he says, tricky to solve. Using a 'Travelling Salesman' algorithm
to find the shortest connecting path would be a start, but potentially
wouldn't always yield a simple polygon - imagine a figure-of-eight
configuration.

[kyonn]

I didn't know this algorithm. It give me an idea which still seems too
simple to be efficient, but here is it :
Start from any point, calculate all distance between others, and join
with the smallest. Do the same for the others until all points are
joined.
Any mathematician to answer ?

[SlowTarget]

Ok... There are probably any number of ways to do this.

One way is to order your points...

1. Find the average of all the latitudes and longitudes (giving
yourself a central point)
2. Find the angle of the vector from the centre to each point (or just
use dx/dy)
3. Order your points by this angle
4. Draw your polygon...

I believe that this will tend to give you a polygon that covers the
largest area for a given set of points, and you won't get any
intersections.

[barryhunter (KML Guru)]

Have a look also at the Convex Hull algorithm, sounds close to what
you want.