[GRASS-user] Thiessen Polygons

[Jan Hartmann]

Glynn Clements wrote:
> 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 have tried to see what's in the ArcGIS 
extension (http://portal.acm.org/citation.cfm?id=1332465, documentation 
at: http://www.geog.unt.edu/~pdong/software/VoronoiHelp.pdf), but the 
math is beyond me. If you think it would be viable to implement this in 
GRASS, I could have a closer look at it. These weighted Voronoi polygons 
are really an interesting methodology.

Jan Hartmann
Departmann of Geography
University of Amsterdam
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/grass-user/attachments/20090215/6738dd06/attachment.html