Changes between Version 34 and Version 35 of PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools/document

Timestamp:

Aug 14, 2012, 9:07:33 AM (12 years ago)

Author:

qliu

Comment:

—

PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools/document

@@ -198 +198 @@
 assuming default value for some of the parameters. Only the most complete has to be implemented in C.
 }}}
+
+
+== Creating a Cost-weighted Distance Raster in PostGIS ==
+[[BR]][[BR]]
+=== Objectives ===
+
+We want to develop a raster/vector integrated approach to generate a cost-weighted distance raster coverage (optionally a tiled coverage) from a point coverage (could also be lines or polygons coverage) and one (could also be multiple) cost raster with some raster specifications, representing the least accumulative cost of traversing the cost surface between each cell and the source points.
+
+=== Constraints ===
+
+ 1.     The source table of geometries (points, line or polygons) can contain one geometry or many (eventually millions). We want the method to scale well whatever the number of source geometry.
+2.      The desired raster is specified with parameters or by referencing an existing raster.
+3.      Sometimes the resolution of the desired raster is so high that the whole raster coverage cannot be stored in one PostgreSQL row. The approach must be able to produce a tiled raster coverage stored into many rows.
+4.      Source geometries might be outside the extent of the desired raster, or the cost raster, or both.
+5.      The approach should work well in a number of situations:
+  a.    small number of sources vs low resolution raster
+  b.    small number of sources vs high resolution raster
+  c.    large number of sources vs low resolution
+  d.    large number of sources vs high resolution Large raster coverage
+6.      The user can specify a maximum cost distance to the source. When the cost exceeds the maximum it gets assigned a nodata value.
+7.      There are multiple cost rasters, and could be in different geographic extents.
+
+
+=== Approach ===
+
+The node-link approach:
+
+The algorithm utilizes the node/link representation for raster cells, in which each center of a cell is considered a node and each node is connected to its adjacent cells(neighbors) by multiple links. Every link has an impedance derived from the cost raster associated with the cells at each end of the link. The cost-weighted distance assigned to each cell represents the cost per unit distance for moving through the cell computed from the cell value in cost raster.
+
+For perpendicular direction link, the cost moving from cell1 to cell2 = (cost1 + cost2) / 2
+    For diagonal direction link, the cost moving from cell1 to cell2 = sqrt(2)*(cost1+cost2)/2
+The calculation begins with source points (polylines or polygons). The computing process grows in 8 directions from source points to the neighboring cells. Cells are put into a list. The cell with the lowest cumulative cost is selected from the list for computing costs to its neighboring cells. The neighbors are then put into the list while the originating cells are removed from the list. The scanning process continues until the list is empty.
+
+'''Pros:'''
+
+    The raster/vector integrated approach of Euclidean distance can be reused here so that:
+        the  source points do not have to be in the raster extent (constraint 4)
+        it is possible to to create a tiled raster coverage aligned to an existing reference raster (constraint 3)
+    The scanning process can move randomly around the entire coverage. Pieces of rasters can be swapped in and out of memory in case of high resolution raster (constraints 5b, 5d).
+
+
+'''Cons:'''
+
+    Not sure whether it will work well with large number of source points (constraint 1, 5c & 5d). Maybe we can use a binary tree with an linked list at each node in the tree to efficiently hold cells with identical cumulative costs.
+    Not sure how it will work with multiple cost rasters (constraint 7).
+