[GRASS-user] Thiessen Polygons

[Jan Hartmann]

Interesting. I know something of these models (worked a few years for 
the archaeology department here in Amsterdam), and, like you, never had 
enough time to really code it. Apart from efficiency, I am wondering 
whether those really cool cost surfaces will degenerate into impossible 
vector polygons.

Do you have any examples from archaeological practice, using this 
gravitation approach? How were they computed?

Jan

Benjamin Ducke wrote:
> 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
>>
>>
>
>