[GRASS-user] Thiessen Polygons

Glynn Clements glynn at gclements.plus.com
Sun Feb 15 17:42:55 EST 2009


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 <glynn at gclements.plus.com>


More information about the grass-user mailing list