[GRASS-dev] Add a cost distance measure to GRASS GIS lib

[Glynn Clements]

Benjamin Ducke wrote:

> I believe we are thinking in different directions here.
> My idea was not about _least_ cost paths, but about
> replacing straight-line distance measurements with
> cost-based distances -- for more realism when modelling
> physical processes. Just like you'd use a geodetic
> distance instead of eculidean in a lat/lon region.
> 
> What I was thinking about was to have just one CONST
> raster that encodes the cost of moving through each
> of its cells (in all directions in the simple
> isotropic case).
> 
> All GRASS modules that use fixed neighborhoods or
> flexible search radii would then measure the distance
> between two points by accumulating the costs in the
> cells on the straight line between the two points.
> 
> Suppose the user has created a COST raster with "1"
> representing "no additional cost" and "2" representing
> "doubled cost for crossing steep terrain". Then if
> he/she specified 100 m as e.g. the search radius for
> a KDE, the maximum search distance will in some
> extreme cases already be reached after approximately
> 50 m, because those 50 cost as much as 100 m on flat
> terrain. That would make the kernel's shape flexible
> and adjusted to the real terrain, instead of a fixed
> circle. 

Even cost along a straight line (or maybe a great circle?) is
computationally expensive, and in the general case would require
holding the entire cost map in memory. Less-general cases would have
to be implemented within the module, as the libraries wouldn't know
how the module intends to access the cost map.

Also, many algorithms which have a concept of distance require that it
follows the conditions for a metric, i.e. for some metric d and all
points x, y, z:

	d(x,x) = 0
	d(x,y) >= 0
	d(x,y) = d(y,x)
	d(x,z) <= d(x,y) + d(y,z)

A distance calculated by integrating a cost map along a fixed path
could violate the fourth condition (transitivity).

Other algorithms (e.g. r.grow.distance) require that distance
increases monotonically with both delta-x and delta-y, and the
proposed solution would violate that.

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