🚀 go-pugleaf

In article <1992Sep3.194209.10620@athena.mit.edu>, gleung@athena.mit.edu (Gilbert Leung) writes:
> 	I have a polygon with known vertices, but these points are
> arranged in random order.  I need an algorithm to put these points
> in an order such that I can trace the perimeter of this polygon.
> 

It can't be done in general.  Look at these points:

        *   *     
  
      *   *
  
        *   *
   
You could connect them like this:

        *---*     
       /    |
      *   * |
       \ / \|
        *   *

or like this:

        *   *     
       / \ /|
      *   * |
       \    |
        *---*

There are more possibilities, even without allowing edges to cross.

For polygons with only 3 vertices there is no problem.  If you allow 
only convex polygons you should be able to do it as well (sorry, I
don't have an algorithm handy).

> Note that this arbitrary polygon can be concave and weird-shaped,
> but it is simple enough that there is only ONE way to connect all
> these points to form a polygon.

The only way I can see for there to be only one way to connect the
points is if the polygon is a triangle.  In that case it doesn't matter
in what order you connect the dots.
----------------------------------------------------------------------
Lorne Epp                                               epp@mala.bc.ca