Drawing a polygon given multiple points

[Brian Krebs]

I've ran into a situation where I have multiple lat/long coordinates in
no particular order and I need to use them to create a polygon so there
aren't any intersecting lines.  The code I've written so far loops
through the coordinates and creates a new line point using line.add(new
pointObj(x, y, 0, 0)) for each one.  Unfortunately, there is no
guarantee that the data we receive from other companies is going to be
in any logical order.

 

As an example, say I had 4 points and I want to create a box:

If we receive them in the following order, we get a box. 

-2, 2

2, 2

2, -2

-2, -2

 

If we receive them in this order, we get an hourglass type shape.

-2, 2

2, 2

-2, -2

2, -2

 

Is there any function or some simplified algorithm that will put these
coordinates into a proper order?  I need something that will figure out
the order no matter how many points there are.

 

Thanks

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/mapserver-dev/attachments/20060926/7c7068a4/attachment.html