The Voronoi diagram is closely related to gravity models:
every cell in the raster map gravitates towards the closest center
point in the input point pattern.
If you change the gravitational attraction of individual points,
you get a weighted Voronoi diagram. If you change the measure
of gravity by switching from straight-line distance to e.g. cost-based
then you get something more complex and realistic than any Voronoi
algorithm can provide.
In Archaeology, a simple formula (called Xtent) has been used
to calculate such gravity models for a long time:
I = C^a - k*d
With "I" being the "influence" of an input point. "I" gets calculated
for every input point at every cell in the map. The input point with
highest "I" wins and the cell gets assigned to that point's ID.
(C^a) is the weight of a point. (k*d) is your (weighted) distance
measure.
Set (C^a) constant and use a straight-line distance measure and you
get your basic Voronoi diagram. Assign different weights to C and
you get a weighted diagram. Replace (k*d) with a more realistic,
cost-based measure and you get something ... really cool.
I am sure, there is a myriad of similar models/formulas in other
disciplines.
I have actually written a GRASS module called r.xtent based on
this. It still has some known bugs, however, and I simply don't have
the time to fix it right now. It's also pretty bloated and inefficient,
so a clean, more minimalistic start might not be a bad idea.
Ben
Jan Hartmann wrote:
Wouldn't this work with cost surfaces too? Starting from several points
(the Thiessen centers) with a grid cell cost information raster
containing only the value "one", you get a raster representation of a
classic Thiessen structure. Manipulating the cost information raster ,
you should get something like a weighted Thiessen structure. The last
step would be to extract the boundaries between the polygons in vector
format, with the methods above. Starting from each center point, the
cost surface will rise, until it meets the rising surface from an
adjacent point. At this location, slope becomes zero. These zero slope
areas are effectively the Thiessen polygons, and can be vectorized. For
normal Thiessen polygons, this should be no problem, but I am not sure
what happens with really complex weighted cases. Does anyone have any
experience with this?
Jan
_______________________________________________
grass-user mailing list
grass-user@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user
--
Benjamin Ducke
Senior Applications Support and Development Officer
Oxford Archaeology Ltd
Janus House
Osney Mead
OX2 0ES
Oxford, U.K.
Tel: +44 (0)1865 263 800 (switchboard)
Tel: +44 (0)1865 980 758 (direct)
Fax :+44 (0)1865 793 496
benjamin.du...@oxfordarch.co.uk
------
Files attached to this email may be in ISO 26300 format (OASIS Open Document
Format). If you have difficulty opening them, please visit http://iso26300.info
for more information.
_______________________________________________
grass-user mailing list
grass-user@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user
