[GRASS-user] Thiessen Polygons

[Hamish]

> 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?

Glynn wrote:
> 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).


Hi,

just some brainstorming ideas for a weighted Voronoi module:

input: vector points with weight column
output: raster map with weighted Voronoi polygons (or r.to.vect built in)
 
the module would create 2 raster maps:
 - one with each vector point expanded to a 2.5D "hemisphere of influence"
bubbles centered over it, map value being the bubble "height", similar to
r.cost or when you lose in the old Missile Command arcade game.
 - the second map being a categorical raster containing the vector cat
which has contributed the maximum bubble at each cell.

e.g.
canvas_map = all zeros;

loop over vector_pts
{
  bubble_height_at_cell = some_calc();
  if ( bubble_height_at_cell > canvas_map(row,col) ) {
    canvas_map(row,col) = bubble_height_at_cell;
    id_map(row,col) = current_vect_cat;
  }

}

when done the 2.5D map can be discarded. [low weight points have no area]
id_map contains the vector point "of note" for that area.

other ideas:
 - use r.param.scale to create a feature map and extract all saddle-point
boundaries between the bubbles as the voronoi boundaries,
(or r.slope.aspect and find areas where slope<1 deg then r.thin, r.to.vect)

 - use some mountain peak prominence algorithm* on the 2.5D map starting at
each input vector pt.
[*] http://article.gmane.org/gmane.comp.gis.grass.user/19467/

 - see v.surf.icw script in addons for other radial basis function ideas
for the bubbles beyond the usual IDW 1/distance^2.


well, ideas are somewhat abstract/vague, but perhaps something in it.


Hamish