Context Navigation

document

Timestamp:: Aug 20, 2012, 8:21:01 AM (12 years ago)
Author:: qliu
Comment:: —

Legend:

: Unmodified
: Added
: Removed
: Modified

PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools/document

-              v36
+              v37
 }}}
+[[BR]][[BR]][[BR]][[BR]]
 == Creating a Cost-weighted Distance Raster in PostGIS Raster ==
 [[BR]][[BR]]
 …
 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.
+[[BR]][[BR]]
 === Constraints ===
 .     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.
 .      The desired raster is specified with parameters or by referencing an existing raster.
 .      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.
 .      Source geometries might be outside the extent of the desired raster, or the cost raster, or both.
 .      The approach should work well in a number of situations:
+.     The desired raster is specified with parameters or by referencing an existing raster.
+.     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.
+.     Source geometries might be outside the extent of the desired raster, or the cost raster, or both.
+.     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
 .      The user can specify a maximum cost distance to the source. When the cost exceeds the maximum it gets assigned a nodata value.
 .      There are multiple cost rasters, and could be in different geographic extents.
+.     The user can specify a maximum cost distance to the source. When the cost exceeds the maximum it gets assigned a nodata value.
+.     There are multiple cost rasters, and could be in different geographic extents.
+[[BR]][[BR]]
 === 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
+ 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).
+ * The raster/vector integrated approach of Euclidean distance can be reused here so that:
+   * the  source points do not have to be in the output raster extent nor the cost 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 (constraint 1, constraints 5b, 5c, 5d). C implementation would be used for this situation. Use of a binary tree with an linked list at each node in the tree to efficiently hold cells with identical cumulative costs.
+'''Cons:'''
+ * PL/pgSQL is not quite useful in initializations of vary large size arrays, any array update can be very slow (Constraint 1). Using array options in PL/pgsql can get very inefficient if the array size gets very large (constraint 5b,5c,5d).
+ * There could be situation where source points are not within output raster nor current cost raster due to that cost raster or output raster might be tiled raster coverage (constraint 4). In that case, accumulatvie cost will be calcualted based upon the edge pixels to adjacent raster.
+'''Future work:'''
+Future work will be done to make it work with multiple cost rasters (constraint 7).
+[[BR]][[BR]]
+==== Tentative functions signatures: ====
+ST_CostDistance(refrast raster,pixeltype text,costrast raster,sourceschema text,sourcetable text,sourcegeomcolumn text, double precision = -1);
+ST_CostDistance(width integer,height integer,rastulx float8,rastuly float8,rastscalex float8,rastscaley float8,rastskewx float8,rastskewy float8,rastsrid integer,rastndv float8,pixeltype text,costrast raster,sourceschema text,sourcetable text,sourcegeomcolumn text,double precision = -1);