[GRASS-user] Thiessen Polygons

GRASS GRASS user
1

Hi folks,

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb sites that are in point vector files.

Thanks for any help you can give.

Kurt

2

Try
v.surf.idw

Cheers
Harald

Kurt Springs wrote:

Hi folks,

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb sites that are in point vector files.

Thanks for any help you can give.

Kurt
_______________________________________________
grass-user mailing list
grass-user@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user

--
-------------------------------------------
Harald Hofmann PhD Candidate - Hydrogeology School of Geosciences
Bldg 28 Monash University Clayton Campus Wellington Road VIC 3800
Australia

harald.hofmann@sci.monash.edu.au

Office: +61 3 9905 5786
Fax: +61 3 9905 4903

3

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

Hamish

4

That did the trick.

Thanks Hamish

Kurt
On Feb 10, 2009, at 6:47 PM, Hamish wrote:

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

Hamish

5

Hamish a écrit :

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi diagram using grass ?

The ability to rank a point to tune the area's influence would be great, for that purpose I've been using an arcgis'extension* but with grass it is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

6

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :
> Kurt Springs wrote:
>> Does anyone know how to do Thiessen Polygons in GRASS?
>>
>> I need to use them around various types of megalithic tomb
>> sites that are in point vector files.
>
> v.voronoi
>
>
> there is some replacement test code to look at in grass-addons as well:
> http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

What exactly is a 'weighted voronoi diagram' (the link does not work)? If you
are after a weighted network connecting points, here is one approach:

http://casoilresource.lawr.ucdavis.edu/drupal/node/698

Dylan

--
Dylan Beaudette
Soil Resource Laboratory
http://casoilresource.lawr.ucdavis.edu/
University of California at Davis
530.754.7341

7

On Wed, Feb 11, 2009 at 5:03 PM, Dylan Beaudette
<debeaudette@ucdavis.edu> wrote:

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :
> Kurt Springs wrote:
>> Does anyone know how to do Thiessen Polygons in GRASS?
>>
>> I need to use them around various types of megalithic tomb
>> sites that are in point vector files.
>
> v.voronoi
>
>
> there is some replacement test code to look at in grass-addons as well:
> http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

Strike that. Link appears to work and RTFM-ing the user guide...

Dylan

8

On Wed, Feb 11, 2009 at 5:03 PM, Dylan Beaudette
<debeaudette@ucdavis.edu> wrote:

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :
> Kurt Springs wrote:
>> Does anyone know how to do Thiessen Polygons in GRASS?
>>
>> I need to use them around various types of megalithic tomb
>> sites that are in point vector files.
>
> v.voronoi
>
>
> there is some replacement test code to look at in grass-addons as well:
> http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

Now that I have read about 'weighted voronoi diagrams', I wonder if a
combination of r.cost + r.mapcalc would solve this problem. Something
along those lines is demonstrated here:

http://casoilresource.lawr.ucdavis.edu/drupal/node/288

This example isn't quite what is requested, although using r.cost with
start=point_i, and stop=neighbor_points (derived from v.delaunay /
v.distance?) may work. It would then be a little more work to convert
the weighted-distance rasters into polygons, and link back to the
original attribute tables... but (hopefully) not outside the realm of
possibility via a script.

Cheers,

Dylan

9

Dylan Beaudette wrote:

>> >> Does anyone know how to do Thiessen Polygons in GRASS?
>> >>
>> >> I need to use them around various types of megalithic tomb
>> >> sites that are in point vector files.
>> >
>> > v.voronoi
>> >
>> >
>> > there is some replacement test code to look at in grass-addons as well:
>> > http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi
>>
>> While we are on this topic, is there a way to get a weigthed voronoi
>> diagram using grass ?
>>
>> The ability to rank a point to tune the area's influence would be great,
>> for that purpose I've been using an arcgis'extension* but with grass it
>> is not possible**. Is there a way to get a similar result ?
>>
>> *http://www.geog.unt.edu/~pdong/software.htm
>> **http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html
>>
>> Regards,
>> MORREALE Jean Roc

Now that I have read about 'weighted voronoi diagrams', I wonder if a
combination of r.cost + r.mapcalc would solve this problem. Something
along those lines is demonstrated here:

http://casoilresource.lawr.ucdavis.edu/drupal/node/288

This example isn't quite what is requested, although using r.cost with
start=point_i, and stop=neighbor_points (derived from v.delaunay /
v.distance?) may work. It would then be a little more work to convert
the weighted-distance rasters into polygons, and link back to the
original attribute tables... but (hopefully) not outside the realm of
possibility via a script.

The problem with using r.cost is that you would need to know the cost
for each cell before you have created the polygons.

I think that the simplest accurate approach would be to modify
r.grow.distance.

--
Glynn Clements <glynn@gclements.plus.com>

10

On 12/02/09 04:15, Dylan Beaudette wrote:

On Wed, Feb 11, 2009 at 5:03 PM, Dylan Beaudette
<debeaudette@ucdavis.edu> wrote:

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

Now that I have read about 'weighted voronoi diagrams',

One version of such diagrams are Reilly surfaces [1],[2] used in retail geography to identify the influence/attraction zone of a city, often depending on population size.

I wonder if a
combination of r.cost + r.mapcalc would solve this problem. Something
along those lines is demonstrated here:

http://casoilresource.lawr.ucdavis.edu/drupal/node/288

This example isn't quite what is requested, although using r.cost with
start=point_i, and stop=neighbor_points (derived from v.delaunay /
v.distance?) may work. It would then be a little more work to convert
the weighted-distance rasters into polygons, and link back to the
original attribute tables... but (hopefully) not outside the realm of
possibility via a script.

This actually raises the same question as [3] about attributing pixels to closest neighbors (where "closest" can obviously be weighted). I think such a functionality would be very useful.

Moritz

[1] Reilly, W.J. (1929) Methods for the study of retail relationships, University of Texas, Bulletin, 2944.
[2] Reilly, W.J. (1931) The law of retail gravitation, New York.
[3] http://lists.osgeo.org/pipermail/grass-user/2009-January/048585.html

11

Glynn Clements wrote:

Dylan Beaudette wrote:

  

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*[http://www.geog.unt.edu/~pdong/software.htm](http://www.geog.unt.edu/~pdong/software.htm)
**[http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html](http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html)

Regards,
MORREALE Jean Roc
        

Now that I have read about 'weighted voronoi diagrams', I wonder if a
combination of r.cost + r.mapcalc would solve this problem. Something
along those lines is demonstrated here:

[http://casoilresource.lawr.ucdavis.edu/drupal/node/288](http://casoilresource.lawr.ucdavis.edu/drupal/node/288)

This example isn't quite what is requested, although using r.cost with
start=point_i, and stop=neighbor_points (derived from v.delaunay /
v.distance?) may work. It would then be a little more work to convert
the weighted-distance rasters into polygons, and link back to the
original attribute tables... but (hopefully) not outside the realm of
possibility via a script.
    


The problem with using r.cost is that you would need to know the cost
for each cell before you have created the polygons.

I think that the simplest accurate approach would be to modify
r.grow.distance.

Do you mean: adding a metric parameter to Euclidean, Squared, Manhattan, and Maximum? Something like: compute on the basis of the value of traversed cells?

Jan

12

Moritz Lennert a écrit :

On 12/02/09 04:15, Dylan Beaudette wrote:

On Wed, Feb 11, 2009 at 5:03 PM, Dylan Beaudette
<debeaudette@ucdavis.edu> wrote:

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

Now that I have read about 'weighted voronoi diagrams',

One version of such diagrams are Reilly surfaces [1],[2] used in retail geography to identify the influence/attraction zone of a city, often depending on population size.

I didn't knew about it, I'll try look for the reference you gave thank. My aim is quite similar to your example as it consists in balancing the influence zone of a archeological settlement, not by the estimated population, but by a factor resulting from the amount of data collected (historical&material).

Regards,
MORREALE Jean Roc

13

The messages from Kurt Spring and Jean Roc Morreale point to archaeological work using GRASS. How many other archaeologists are there on the list using GRASS. I'd be interested in hearing about archaeological applications as I have just begun the learning curve for my own archaeological work.

Thanks,

Lyle Browning

On Feb 12, 2009, at 5:49 PM, MORREALE Jean Roc wrote:

Moritz Lennert a écrit :

On 12/02/09 04:15, Dylan Beaudette wrote:

On Wed, Feb 11, 2009 at 5:03 PM, Dylan Beaudette
<debeaudette@ucdavis.edu> wrote:

On Wednesday 11 February 2009, MORREALE Jean Roc wrote:

Hamish a écrit :

Kurt Springs wrote:

Does anyone know how to do Thiessen Polygons in GRASS?

I need to use them around various types of megalithic tomb
sites that are in point vector files.

v.voronoi

there is some replacement test code to look at in grass-addons as well:
http://trac.osgeo.org/grass/browser/grass-addons/vector/voronoi

While we are on this topic, is there a way to get a weigthed voronoi
diagram using grass ?

The ability to rank a point to tune the area's influence would be great,
for that purpose I've been using an arcgis'extension* but with grass it
is not possible**. Is there a way to get a similar result ?

*http://www.geog.unt.edu/~pdong/software.htm
**http://osdir.com/ml/gis.grass.user/2004-04/msg00036.html

Regards,
MORREALE Jean Roc

Now that I have read about 'weighted voronoi diagrams',

One version of such diagrams are Reilly surfaces [1],[2] used in retail geography to identify the influence/attraction zone of a city, often depending on population size.

I didn't knew about it, I'll try look for the reference you gave thank. My aim is quite similar to your example as it consists in balancing the influence zone of a archeological settlement, not by the estimated population, but by a factor resulting from the amount of data collected (historical&material).

Regards,
MORREALE Jean Roc
_______________________________________________
grass-user mailing list
grass-user@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user

14

Lyle E. Browning wrote:

The messages from Kurt Spring and Jean Roc Morreale point to
archaeological work using GRASS. How many other
archaeologists are there on the list using GRASS.

I believe quite a few,

I'd be interested in hearing about archaeological applications as I
have just begun the learning curve for my own archaeological
work.

see/add to the GRASS Archeology wiki page linked from:
  http://grass.osgeo.org/wiki/Applications

the Archeology page there is still a bit under developed & preliminary,
but as it's a wiki all can help improve it.

regards,
Hamish

15

Jan Hartmann wrote:

> The problem with using r.cost is that you would need to know the cost
> for each cell before you have created the polygons.
>
> I think that the simplest accurate approach would be to modify
> r.grow.distance.

Do you mean: adding a metric parameter to Euclidean, Squared, Manhattan,
and Maximum? Something like: compute on the basis of the value of
traversed cells?

I mean scale the distance by the value of the nearest non-null cell.

--
Glynn Clements <glynn@gclements.plus.com>

16

Yes, I guess that what I meant too, you just formulate it better, in a more general way. I find this interesting, as I have experimented with weighted Voronoi polygons, but only in vector format. There is a complete book on that methodolgy: Atsuyuki Okabe, Barry Boots, Kokochi Sugihara, Sung Nok Chiu: Spatial Tesselations. Concepts and Applications of Voronoi Diagrams. Wiley, Chichester 2000. It’s really fascinating to see how much you can do with this technology, not only in theory but also in practice. Of course, the vector based algorithms are hard to implement and can be very resource hungry. A lot of them are already available however: just Google on “weighted voronoi”. As always, a raster based approach could be not only more efficient, but also conceptually more general. There is an ArcGIS extension available that does exactly this: see http://portal.acm.org/citation.cfm?id=1332465

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?

Jan

Glynn Clements wrote:

17

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?

Oops; I spoke too soon.

In retrospect, this won't work. r.grow.distance relies upon the fact
that once a cell falls out of consideration, it stays out. It will
only consider cells which either are from the current row, or were
used on the previous row.

With distance scaling, this doesn't hold. A cell could be temporarily
overriden by much nearer cells with increased scale factors (lower
weights), then regain its influence once the distance increases.

IOW, this isn't something which can implemented given the algorithm
used by r.grow.distance. Any algorithm which implemented distance
scaling would inevitably have worst-case memory usage proportional to
the number of non-null input cells, as you can never "forget" a cell
whose scale factor is lower than those currently being considered, as
it will eventually regain its influence.

--
Glynn Clements <glynn@gclements.plus.com>

18

Dear Glynn Clements

Is there a command r.grow.distance on GRASS?
I tryed to find it on Native WinGrass, but it appears not be available, almost on 6.3 version.

Best wishes

miltinho

2009/2/14 Glynn Clements <glynn@gclements.plus.com>

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?

Oops; I spoke too soon.

In retrospect, this won’t work. r.grow.distance relies upon the fact
that once a cell falls out of consideration, it stays out. It will
only consider cells which either are from the current row, or were
used on the previous row.

With distance scaling, this doesn’t hold. A cell could be temporarily
overriden by much nearer cells with increased scale factors (lower
weights), then regain its influence once the distance increases.

IOW, this isn’t something which can implemented given the algorithm
used by r.grow.distance. Any algorithm which implemented distance
scaling would inevitably have worst-case memory usage proportional to
the number of non-null input cells, as you can never “forget” a cell
whose scale factor is lower than those currently being considered, as
it will eventually regain its influence.

–
Glynn Clements <glynn@gclements.plus.com>

grass-user mailing list
grass-user@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/grass-user

19

Milton Cezar Ribeiro wrote:

Is there a command r.grow.distance on GRASS?
I tryed to find it on Native WinGrass, but it appears not be available,
almost on 6.3 version.

It's new in 6.4/7.0.

--
Glynn Clements <glynn@gclements.plus.com>

20

Glynn Clements wrote:

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?
    


Oops; I spoke too soon.

In retrospect, this won't work. r.grow.distance relies upon the fact
that once a cell falls out of consideration, it stays out. It will
only consider cells which either are from the current row, or were
used on the previous row.

With distance scaling, this doesn't hold. A cell could be temporarily
overriden by much nearer cells with increased scale factors (lower
weights), then regain its influence once the distance increases.

IOW, this isn't something which can implemented given the algorithm
used by r.grow.distance. Any algorithm which implemented distance
scaling would inevitably have worst-case memory usage proportional to
the number of non-null input cells, as you can never "forget" a cell
whose scale factor is lower than those currently being considered, as
it will eventually regain its influence.

Do you mean that implementing a raster version of weighted Voronoi methods would be very inefficient, compared to vector methods, or that it would be very difficult? I have tried to see what’s in the ArcGIS extension (http://portal.acm.org/citation.cfm?id=1332465, documentation at: http://www.geog.unt.edu/~pdong/software/VoronoiHelp.pdf), but the math is beyond me. If you think it would be viable to implement this in GRASS, I could have a closer look at it. These weighted Voronoi polygons are really an interesting methodology.

Jan Hartmann
Departmann of Geography
University of Amsterdam