[GRASS-user] Thiessen Polygons
Hamish
hamish_b at yahoo.com
Tue Feb 17 02:32:25 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?
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
More information about the grass-user
mailing list