Hi Tim, You could compute the convex hull first, and then iterate from points on the convex hull. That should be much faster already, especially since hexagons are convex and the perimeter will be locally convex around all the points touching the convex hull. You could do a variation of the "monotone pieces" algorithm that is used in computational geometry. But this is a simpler problem. Are there cases with interior holes?
I have been meaning to write something like this for hexbin for a while. There are many cases where it would be nice to find approximations to the density contours and a quick and dirty way is to threshold the hexagon counts, find the hull and smooth the perimeter. Nicholas On Fri, 16 Mar 2007 08:34:20 -0500, "Tim Keitt" <[EMAIL PROTECTED]> said: > Hi Nic, > > The convex hull would be fast and easy to compute (there's existing > code in R). I want the ordinary hull which is the set of arcs forming > the perimeters (inside and out). My crude and very slow solution was > to convert all the polygons (in this case hexagons on a lattice) into > their constituent arcs and then for each arc count how many times it > occurs in the set (requires slightly fuzzy matching of points). Arcs > that occur more than once are removed. The remaining arcs form the > hull. Runs in about 20 minutes with a few hundred hexagons. > Sufficient for the moment. > > THK > > On 3/16/07, Nicholas Lewin-Koh <[EMAIL PROTECTED]> wrote: > > Hi Tim, > > I am not quite sure what you are getting at here. Do you want to > > intersect > > polygons and then select the set of lines that form the outer perimeter? > > Do you wan the convex hull of a set of polygons. I guess I have been out > > of the > > GIS world to long. It seems to me that this would be something easy to > > solve, > > just tedious iteration of the polygon coordinates and some > > triangulation. > > > > Nicholas > > > > > Date: Thu, 15 Mar 2007 10:49:23 -0500 > > > From: "Tim Keitt" <[EMAIL PROTECTED]> > > > Subject: [R-sig-Geo] polygons to arcs? > > > To: r-sig-geo@stat.math.ethz.ch > > > Message-ID: > > > <[EMAIL PROTECTED]> > > > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > > > > > Is there an 'sp' function that takes a polygon as its argument and > > > returns a set of line objects corresponding to the arcs in the > > > polygon? > > > > > > Or better yet, a function that given a set of polygons, returns the > > > hull? (ie the set of singleton arcs after applying the polys to arcs > > > function) > > > > > > THK > > > > > > -- > > > Timothy H. Keitt, University of Texas at Austin > > > Contact info and schedule at http://www.keittlab.org/tkeitt/ > > > Reprints at http://www.keittlab.org/tkeitt/papers/ > > > ODF attachment? See http://www.openoffice.org/ > > > > > > > > > > > > > > -- > Timothy H. Keitt, University of Texas at Austin > Contact info and schedule at http://www.keittlab.org/tkeitt/ > Reprints at http://www.keittlab.org/tkeitt/papers/ > ODF attachment? See http://www.openoffice.org/ _______________________________________________ R-sig-Geo mailing list R-sig-Geo@stat.math.ethz.ch https://stat.ethz.ch/mailman/listinfo/r-sig-geo
