🚀 go-pugleaf

In article <1992Sep3.194209.10620@athena.mit.edu> you write:
> 	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.
> 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.
> 
> 	Any help would be greatly appreciated.  Thanks in advance.
> 
> Gilbert
> 


An arbitrary set of vertices does not always become a polygon. It could
turn up to be a line. What you need to sort, is the EDGES of the polygon.
Then you can trace the perimeter easy.

You represent the egdes on the form (xmin, ymin, xmax, ymax) and if you
sort after these criterias:

	ymin, xmin, m  (where m is the elevation of the edge, that is
                        m = (ymax-ymin)/(xmax-xmin))

then a polygon like this (the P's are the crosspoints)




                Pp
               p  pp  (4)
               p    pp
         (3)  p       pP
             p         p
            p          p
            p          p
           Ppp        p  (2)
              ppp     p
             (1) ppp  p
                    ppP

be sorted after the shown numbering.

(This is in fact the way you sort edges if you are going to graphicly fill the
 polygon using scan-conversion)

Espen.