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 <m...@llnl.gov> > Subject: [R-sig-Geo] Put polygon points in correct order > To: r-sig-geo@stat.math.ethz.ch > Message-ID: <p06240800c6eb329bf...@[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 > m...@llnl.gov > > > > ------------------------------ > > Message: 7 > Date: Fri, 2 Oct 2009 08:27:06 +0100 > From: Barry Rowlingson <b.rowling...@lancaster.ac.uk> > Subject: Re: [R-sig-Geo] Put polygon points in correct order > To: Don MacQueen <m...@llnl.gov> > Cc: r-sig-geo@stat.math.ethz.ch > Message-ID: > <d8ad40b50910020027n357a260dh1f0628fecb87c...@mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > On Fri, Oct 2, 2009 at 5:52 AM, Don MacQueen <m...@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 > > > _______________________________________________ R-sig-Geo mailing list R-sig-Geo@stat.math.ethz.ch https://stat.ethz.ch/mailman/listinfo/r-sig-geo
