> 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 _______________________________________________ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user