[R-sig-Geo] Creating non-overlapping polygons from centroid with known size

[Barry Rowlingson]

On Sun, May 23, 2010 at 6:25 PM, Jens Oldeland <oldeland at gmx.de> wrote:
> Dear group,
>
> I am looking for a method that allows me to creating non-overlapping
> polygons from centroids with a known size. I have information on the
> location of farms in Azerbaijan. All farms have a specific size, but I don´t
> know the exact borderlines of those farms. Now, I have to create a polygon
> layer that has polygons with the specific farmsize for each polygon, and the
> polygons of the farms should not overlap. However, I do not have a good idea
> how to do that.
>
>
> I would be grateful for any hints or suggestions!
>

 Hmmmm. seems like an interesting problem. The easiest ideas I can
come up with operate on raster grids. Start with an empty grid on a
finer resolution than the closest pair of farms. Seed one grid square
for each farm centroid. Then loop over farms, allocating an adjacent
grid square in a non-allocated space until all farms have their
allocation. How do you choose the next grid square for a farm? I'd go
for the nearest non-allocated space that is contiguous to current
squares for that farm, which should keep it compact. I think I've seen
a screensaver do something similar with advancing waves of pixels. Any
solution to this in pure R would probably be horrendously slow for
even a small number of farms on a fine grid. Coded in C it should zip
along, with some clever data structures to help.

 There may be code to do this already, in the raster processing
section of a GIS package such as GRASS or gvSIG or geotools.

 Doing it with vectors could be tricky. For a first try, especially if
the farms are quite spaced out, you could generate voronoi polygons
for each farm, and if they are all larger than the required farm area
then all you then need to do is shrink each voronoi polygon about the
centroid by a factor. If any voronoi polys aren't big enough then
maybe you can shrink the big ones, and feed their points into the
voronoi algorithm again to get polys for the remaining centroids. And
repeat. This might not work though!

Barry