[GRASS-user] Thiessen Polygons

[Benjamin Ducke]

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 at 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.ducke at 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.