Jan Hartmann wrote: > >> With that in mind, if the algorithm you propose would be indeed an > >> approximation to weighted Voronoi polygons, *and* it wouldn't be all to > >> hard to implement (I have no idea about that), would it make sense to > >> propose this as a new RFC for GRASS? > >> > > > > Oops; I spoke too soon. > > > > In retrospect, this won't work. r.grow.distance relies upon the fact > > that once a cell falls out of consideration, it stays out. It will > > only consider cells which either are from the current row, or were > > used on the previous row. > > > > With distance scaling, this doesn't hold. A cell could be temporarily > > overriden by much nearer cells with increased scale factors (lower > > weights), then regain its influence once the distance increases. > > > > IOW, this isn't something which can implemented given the algorithm > > used by r.grow.distance. Any algorithm which implemented distance > > scaling would inevitably have worst-case memory usage proportional to > > the number of non-null input cells, as you can never "forget" a cell > > whose scale factor is lower than those currently being considered, as > > it will eventually regain its influence. > > Do you mean that implementing a raster version of weighted Voronoi > methods would be very inefficient, compared to vector methods, or that > it would be very difficult?
I mean only that it cannot be done using the approach which r.grow.distance uses, using memory proportional to the number of columns (it uses a number of row buffers, i.e. one-dimensional arrays, with one element per column). [In any case, weighted distances won't produce polygons; at least, not for Euclidean distances. The boundary will only be a straight line if the weights are equal.] However, that doesn't meant that other algorithms wouldn't be feasible, particularly if you're only interested in typical behaviour rather than worst-case behaviour. Also, it may be possible to use the r.grow.distance approach with something other than scaling. An offset would work, optionally combined with a monotonic function of the distance (provided that it's the same for every point). -- Glynn Clements <gl...@gclements.plus.com> _______________________________________________ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user