[R-sig-Geo] Put polygon points in correct order

[Don MacQueen]

I have a set of points that form a polygon, except that they are in 
the wrong order. For example, source into R the object "tmpsub" given 
below. Then do

plot(tmpsub)
polygon(tmpsub)

You will see that although the points define a polygon, they are in 
the wrong order.

I need an algorithm to put them in the correct order. It's not 
obvious to me how to do this.
(They will then be used to build a SpatialPolygons object.)

Suggestions, or pointers to algorithms, would be much appreciated.

-Don



## defines a two column matrix
tmpsub <-
structure(c(-337.739799897238, 184.995108083333, 191.915187666667,
191.915187666667, 185.349158666667, 185.326133441305, -21.0945178333333,
-21.2232635, -132.491705916667, -132.620451583333, -339.418178666667,
-387.149289912409, -413.426281562044, -414.136470525547, -338.146251430657,
-337.739799897238, -338.613951361612, -283.102594633440, -283.102594633440,
-182.623434321894, -182.623434321894, -126.691537012447, -128.515403229060,
-40.3618694261276, -40.3618694261276, 42.9280211325047, 44.1439319435797,
129.865644124362, 129.865644124362, 185.815172793583, -338.613951361612,
126.309002505437, 107.131313166667, 107.195686, 87.8194631666667,
87.8194631666667, -172.925954755075, -173.0192575, -223.745050166667,
-223.745050166667, -172.890511833333, -172.890511833333, -172.631459722628,
-173.164101445255, -115.816342642336, -116.171437124088, 126.309002505437,
226.049864194626, 226.049864194626, 195.140131470985, 195.329505335223,
225.119320206559, 225.119320206559, 195.329505335223, 195.937460740761,
225.119320206559, 225.727275612096, 196.545416146298, 195.329505335223,
225.727275612096, 225.734458758671, 226.049864194626), .Dim = c(31L,
2L))



p.s.
I'm actually trying to solve a bigger problem, which is to take two 
adjacent polygons and combine them into a single polygon that 
outlines both of them. Kind of like a convex hull, but I need it to 
trace the outlines of the polygons. The above re-ordering is part of 
one way to solve my bigger problem. But if anyone has suggestions for 
the bigger problem, that would even better.
-- 
---------------------------------
Don MacQueen
Lawrence Livermore National Laboratory
Livermore, CA, USA
925-423-1062
macq at llnl.gov