[R-sig-Geo] Truncating polygons in R

[Gregory Snow]

I have one suggested extension to Barry's idea.

With Barry's idea the polygons will all be inside the square, but there
will be some area in the square that is not inside any of the polygons.
If you want the entire square to be included within the polygons then
take Barrys Idea of projecting the points perpendicular to the sides,
but instead of projecting them onto the sides, project them beyond that
side so that they are the same distance from the side of the square.
Then the set of points that are equal distance from the projected point
and the original point will fall along the border of the square.
Consider the following code:

x <- runif(10)
y <- runif(10)

plot(x,y)

plot(voronoi.polygons(voronoi.mosaic(x,y)))
points(x,y)

xx <- c( x,  x,   x, -x, 2-x )
yy <- c( y, -y, 2-y,  y,   y )

plot(voronoi.polygons(voronoi.mosaic(xx,yy)))
points(x,y)


This is a little bit of overkill (you may want to delete some of the
projected points), but you can see that in the center is a set of
polygons that together form the unit square around the data points.  It
is now just a matter of extracting only those polygons.

Hope this helps,

-- 
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.snow at intermountainmail.org
(801) 408-8111
 
 

> -----Original Message-----
> From: r-sig-geo-bounces at stat.math.ethz.ch 
> [mailto:r-sig-geo-bounces at stat.math.ethz.ch] On Behalf Of 
> Barry Rowlingson
> Sent: Thursday, April 06, 2006 1:22 AM
> To: sburden at uow.edu.au
> Cc: r-sig-geo at stat.math.ethz.ch
> Subject: Re: [R-sig-Geo] Truncating polygons in R
> 
> 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
> 
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at stat.math.ethz.ch
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>