On Sun, May 23, 2010 at 6:25 PM, Jens Oldeland <oldel...@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 _______________________________________________ R-sig-Geo mailing list R-sig-Geo@stat.math.ethz.ch https://stat.ethz.ch/mailman/listinfo/r-sig-geo
