[R-sig-Geo] Truncating polygons in R

[Barry Rowlingson]

Sandy Burden wrote:

> I have been creating polygons around the points using the commands
> voronoi.mosaic and voronoi.polygon commands from the tripack package.  I can
> then convert the polygons to a spatial polygon data frame so I can use the
> polygons for other things, but I am finding that my polygons extend beyond
> the boundaries of the 1*1 square.  Is there any command I can use in R to
> truncate the polygons so that they don't extend beyond the boundary using
> either the voronoi polygons or the spatial polygons?  Or is there a better
> way to create the polygons?

  Off the top of my head here, but if you generate a number of extra 
points along the edges of your 1x1 square that may constrain the voronoi 
polygons of your data points to stay within the square. The spacing of 
the extra points depends on the distance from the edge to the nearest 
data point. I think!

*thinks a bit more*

Yep, place artificial points on the edges so that from any location on 
the edges, the nearest point is an artificial point rather than a data 
point. Then construct voronoi polygons from the union of the 
artificial+data points, and then only take the data point polygons. 
These will be constrained to be within the square because voronoi 
polygons define nearest neighbour areas, we know the nearest neighbour 
of any location on the edge is one of our constructed points on the 
edge, and hence that the voronoi polys for the data points are within 
the square.

  I'm also sure a diagram would explain this better!

  So the problem is now constructing the extra edge point locations. I 
think if you take all your data points and project them perpendicularly 
onto the north, south, east, and west edges you'll have a solution, but 
not the best one, just one that is simple to construct. You'll just have 
a bigger voronoi triangulation that strictly necessary. Oh lets try a 
diagram (this needs a fixed-width font).

-------------------------------------- north edge
                               3
          1
                        2               some points 1,2,3


  - now project onto north edge, we add 3 new points


---------a-------------b------c------- north edge
                               3
          1
                        2               some points 1,2,3


Now any location on the edge will be nearer to a,b, or c than any of 1,2 
or 3. The voronoi polys for 1,2 and 3 will be within the north edge.

This isn't optimal because imagine 2 is a lot further south, then you 
could get away with only needing a and c on the edge. I cant think of an 
optimal method, it probably involves constructing the voronoi polygons 
and then adding extra points and recomputing, but it is 8am here and 
I've not been awake that long...

Further details on request. And after my morning coffee. And probably 
after someone comes up with a *realy simple* solution!

Barry