[R-sig-Geo] R-sig-Geo Digest, Vol 43, Issue 14

[Nicholas Lewin-Koh]

Hi Tim,
Now I think I get it. What about the following:
1) threshold based on your qvalues
2) find all disconnected sets 
3) For each disconnected set 
  a) find the convex hull of the hexagon centers, this should be
  equivalent to the
     the convex hull of the hexagons themselves (convexity of the
     hexagons and a regular lattice)
  b) iterate from each (center)point on the hull, using only points in
  the set and test for an exterior neighbor,
     you have to be careful here due to holes, just keep a binary matrix
     of each hexagons exterior faces.
  c) invert the polygon and find the boundaries of interior holes
4) put it all together saving just the vertices of the hexagons sides on
the exterior

So you have already reduced your constant by 1/6 using the centers. I
think this should be no worse
than the convex hull itself times some function of n representing the
fraction of exterior polygon
centers.

Now you already have something that works so this is just thinking about
if you have to do it again or
do some simulations.

Cheers
Nicholas
  

On Fri, 16 Mar 2007 10:55:06 -0500, "Tim Keitt" <tkeitt at gmail.com> said:
> Ya, there can be pretty arbitrary holes. The situation is a large
> hexagonal lattice where some fraction of cells have q-values < 0.05.
> Now draw lines around those cells following the hexagonal edges, but
> omitting any interior arcs. I can send you an example solution. The
> images are bit big for the list.
> 
> THK
> 
> On 3/16/07, Nicholas Lewin-Koh <nikko at hailmail.net> wrote:
> > 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" <tkeitt at gmail.com> 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 <nikko at hailmail.net> 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" <tkeitt at gmail.com>
> > > > > Subject: [R-sig-Geo] polygons to arcs?
> > > > > To: r-sig-geo at stat.math.ethz.ch
> > > > > Message-ID:
> > > > >       <6262c54c0703150849qe60ab14nfef1eb3bf73dfb5d at mail.gmail.com>
> > > > > 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/
> >
> 
> 
> -- 
> 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/