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

[Nicholas Lewin-Koh]

Hi Don,
If your polygons are all convex, then there is hope. If not
then it can only be done with added constraints, there is
not enough information in the coordinates alone to order them
except up to an approximation. If they are convex, just
compute the convex hull. If not, you could try computing the convex hull
and project points onto the closest edge (perpendicular distance), that
would give you an ordering but it would be approximate.

Nicholas 

 
> Message: 6
> Date: Thu, 1 Oct 2009 21:52:33 -0700
> From: Don MacQueen <macq at llnl.gov>
> Subject: [R-sig-Geo] Put polygon points in correct order
> To: r-sig-geo at stat.math.ethz.ch
> Message-ID: <p06240800c6eb329bfd86@[192.168.11.5]>
> Content-Type: text/plain; charset="us-ascii" ; format="flowed"
> 
> 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
> 
> 
> 
> ------------------------------
> 
> Message: 7
> Date: Fri, 2 Oct 2009 08:27:06 +0100
> From: Barry Rowlingson <b.rowlingson at lancaster.ac.uk>
> Subject: Re: [R-sig-Geo] Put polygon points in correct order
> To: Don MacQueen <macq at llnl.gov>
> Cc: r-sig-geo at stat.math.ethz.ch
> Message-ID:
> 	<d8ad40b50910020027n357a260dh1f0628fecb87cc53 at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
> 
> On Fri, Oct 2, 2009 at 5:52 AM, Don MacQueen <macq at llnl.gov> wrote:
> > 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.
> 
>  For the points you gave us I can see several ways of making a
> non-self-intersecting polygon. Along the top, for example, you could
> either have squares or triangles. Do you have any other constraints?
> It looks to me like you only want horizontal and vertical lines in
> your polygons. Is that so? That might make a unique  solution
> possible...
> 
> Barry
> 
> 
>