# Changes between Version 42 and Version 43 of PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools

Show
Ignore:
Timestamp:
06/18/12 22:08:58 (11 months ago)
Comment:

--

Unmodified
Removed
Modified
• ## PostGIS_Raster_SoC_Idea_2012/Distance_Analysis_Tools

v42 v43
8080 ''' How Euclidean distance and Cost-weighted distance are computed in ArcGIS and GRASS '''
8181
82  * Euclidean Distance
83     * ArcGIS
84       * Concepts:[[BR]]
82 * '''Euclidean Distance'''
83    * '''ArcGIS'''
84      * '''Concepts:'''[[BR]]
8585      The Euclidean Distance generates a raster layer that contains the measured distance from every cell to the nearest source.
8686      [[Image(http://help.arcgis.com/en/arcgisdesktop/10.0/help/009z/GUID-7D94981B-1DBB-40F9-9F3F-B025C9F52BCD-web.png)]]
88       * Function:[[BR]]
88      * '''Function:'''[[BR]]
8989      EucDistance (in_source_data, {maximum_distance}, {cell_size}, {out_direction_raster})
9090        * in_source_data: Raster Layer / Feature Layer (vector)

106106          * The distance raster identifies the Euclidean distance for each cell to the closest source cell, set of source cells, or source location(s).
107107          * The distances are measured as Euclidean distance in the projection units of the raster, and are computed from cell center to cell center.
108       * Algorithm
108      * '''Algorithm:'''
109109        * Euclidean distance is calculated from the center of the source cell to the center of each of the surrounding cells. The Euclidean algorithm works as follows: for each cell, the distance to each source cell is determined by calculating the hypotenuse with x and y distances between cell centers as the other two legs of the triangle.[[BR]]
110110        [[Image(http://help.arcgis.com/en/arcgisdesktop/10.0/help/009z/GUID-B6170E16-50FB-45FB-A724-E24251CDF305-web.gif)]]

113113        * If the cell is at an equal distance to two or more sources, the cell is assigned to the source that is first encountered in the scanning process. User cannot control this scanning process.
114114        * The actual algorithm computes the information using a two-scan sequential process(need to figure it out?). This process makes the speed of the tool independent from the number of source cells, the distribution of the source cells, and the maximum distance specified. The only factor that influences the speed with which the tool executes is the size of the raster. The computation time is linearly proportional to the number of cells in the Analysis window.
115       * Reference: [[BR]]
115      * '''Reference:''' [[BR]]
116116        [http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//009z0000001p000000.htm]
117117[[BR]]
118  * Euclidean Distance
119    * GRASS
118 * '''Euclidean Distance'''
119   * '''GRASS'''
120120      * r.grow.distance or GDAL tools\ Proximity (Raster Distance) in QGIS
121       * Concepts:
121      * '''Concepts:'''
122122        * '''r.grow.distance''' metric=euclidean (default):[[BR]]
123123        generates raster maps representing the distance to the nearest non-null cell in the input map and/or the value of the nearest non-null cell.
124124        * '''gdal_proximity''' generates a raster proximity map indicating the distance from the center of each pixel to the center of the nearest target pixel in the source raster.
125       * Function:[[BR]]
125      * '''Function:'''[[BR]]
126126        '''r.grow.distance''' ['''-m'''] '''input'''=name ['''distance'''=name] ['''value'''=name] ['''metric'''=string] [--'''overwrite'''] [--'''verbose'''] [--'''quiet''']
127127        * input: Raster dataset

139139        * -mxdist:[[BR]]
140140          The maximum distance to be generated. All pixels beyond this distance will be assigned the nodata value.
141       * Algorithm:
141      * '''Algorithm:'''
142142        * d(dx,dy) = sqrt(dx^2 + dy^2)
143143        * Cells grown would form isolines of distance that are circular from a given point, with the distance given by the radius.
144       * Reference: [[BR]]
144      * '''Reference:''' [[BR]]
145145        [http://grass.osgeo.org/manuals/html70_user/r.grow.distance.html][[BR]]
146146        [http://www.gdal.org/gdal_proximity.html]
147[[BR]][[BR]]
148 * '''Cost-weighted Distance'''
149   * '''ArcGIS'''
150    * '''Concepts:'''
151      * Calculates the least accumulative cost distance for each cell to the nearest source over a cost surface.[[BR]]
152        [[Image(http://help.arcgis.com/en/arcgisdesktop/10.0/help/009z/GUID-E922AC15-69E2-4965-A49E-28B1017C85E6-web.png)]]
153    * '''Function:'''[[BR]]
154      CostDistance (in_source_data, in_cost_raster, {maximum_distance}, {out_backlink_raster})
155      * in_source_data: Raster Layer / Feature Layer (vector)
156        * Identifies the cells(raster) or locations(feature) to which the Euclidean distance for every output cell location is calculated.
157        * If the source is a raster layer, it must contain only the values of the source cells, while other cells must be NoData.
158        * If the source is a feature layer, it will internally be transformed into a raster. By default, the first valid available field will be used, otherwise the ObjectID field will be used.
159      * in_cost_raster: Raster Layer
160        * The value of each cell represents the cost per unit distance for moving through the cell. Each cell location value is multiplied by the cell resolution while also compensating for diagonal movement to obtain the total cost of passing through the cell.
161        * If the input source data and the cost raster are different extents, the default output extent is the intersection of the two. Or you can Union the input rasters to get a cost distance surface for the entire extent.
162        * Cell locations with NoData in the Input cost raster act as barriers in the cost surface. Any cell location that is assigned NoData on the input cost raster will receive NoData on the output raster.
163        * The values of the cost raster cannot be negative or zero. If the cost raster does contain values of zero, and:
164          * If these values represent areas of lowest cost, change values of zero to a small positive value (such as 0.01) before running Cost Distance.
165          * If areas with a value of zero represent barriers, these values should be turned to NoData before running Cost Distance.
166      * maximum_distance: Double Precision
167        * Defines the threshold that the accumulative cost values cannot exceed.
168        * Any cell location that has accumulative cost distance value exceed this value will be assigned NoData for output value.
169        * The default is to the edge of the output raster.
170        * The unit is specified the same cost units as those on the cost raster.
172        * Defines the direction or identify the next neighboring cell along the least accumulative cost path from a cell to reach its least cost source.
173        * The first succeeding cell from the source cell will be assigned the value 1 and 2,3,... ,8 continuing clockwise. The value 0 is reserved for source cells.
174      * Return Value: Raster Layer
175        * Identifies the least accumulative cost distance for each cell over a cost surface to the closest source cell, set of source cells, or source location(s).
176        * The least-cost distance of a cell to a set of source locations is the lower bound of the least-cost distances from the cell to all source locations.
177    * '''Algorithm:'''
178      * The algorithm utilizes the node/link cell representation, in which each center of a cell is considered a node and each node is connected to its adjacent nodes by multiple links.
179      * Every link has an impedance derived from the costs associated with the cells at each end of the link and from the direction of movement through the cells. The cost assigned to each cell represents the cost per unit distance for moving through the cell, that is the cell size multiplied by the cost value.
180        * Perpendicular node cost:[[BR]]
181          The cost moving from cell1 to cell2 = (cost1 + cost2) / 2
182        * Diagonal node cost:[[BR]]
183          The cost moving from cell1 to cell2 = sqrt(2)*(cost1+cost2)/2
184      * Creating an accumulative cost-distance raster is an iterative process that attempts to identify the lowest-cost cell and add it to an output list.
185        * The process begins with the source cells.
186        * Accumulative cost distances are calculated for all the neighboring cells, activated, put into a cost cell list and arranged rom the lowest to the highest.
187        * The lowest cost cell is chosen from the active accumulative cost cell list, and the value is assigned to the output cost-distance raster for that cell location.
188        * The neighborhood is expanded from the lowest cost cell, the new costs are calculated, and the new cost cells are added to the active list.
189        * This allocation process continues until all cells have been chosen from the active list. The result is the accumulative cost or weighted-distance raster.
190        * If there are multiple zones or disconnected sets of source cells on the input source raster, the growing process continues and allocates the cheapest cost cell from the active list regardless of which source it is from.
191        * No travel is allowed through cells containing NoData values. The least accumulative cost for cells on the back side of a group of NoData cells is determined by the cost to travel around these locations. If a cell location is assigned NoData on the input cost raster, NoData will be assigned to the cell location on the cost distance output raster.
192    * '''Reference:'''[[BR]]
193      [http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Cost_Distance/009z00000018000000/]
194[[BR]]
195 * '''Cost-weighted Distance'''
196   * '''GRASS'''
197    * '''r.cost'''
198    * '''Concepts:'''
199      * Creates a raster map showing the cumulative cost of moving to each cell on a cost surface from other user-specified cell(s) whose locations are specified by their geographic coordinate(s) or from a raster points map.
200      * Each cell value in the output raster presents the lowest total cost of traversing the cost surface between each cell and the user-specified points.
201    * '''Function:'''[[BR]]
202      '''r.cost''' [-'''knrv'''] '''input'''=name '''output'''=name ['''start_points'''=name] ['''stop_points'''=name] ['''start_rast'''=name] ['''coordinate'''=x,y[,x,y,...]] ['''stop_coordinate'''=x,y[,x,y,...]] ['''max_cost'''=cost] ['''null_cost'''=null cost] ['''percent_memory'''=percent memory] [--'''overwrite'''] [--'''verbose'''] [--'''quiet''']
203      * input: raster cost map
204        * Value of each grid cell represents cost information
205      * output: output raster map of cummulative cost
206      * start_points:
207        * Point(s) with geographic coordinates (coordinate)
208        * Vector points file
209        * Raster map with non-null cells representing starting points (start_rast)
210      * stop_points:
211        * Point(s) with geographic coordinates (stop_coordinate)
212        * Vector points file
213      * max_cost: maximum cumulative cost
214        * The execution will stop accumulating costs when either max_cost is reached, or one of the stop points is reached. Once the cumulative cost to all stopping points has been determined, processing stops.
215      * null_cost:
216        * By default null cells in the input raster map are excluded from the algorithm, and thus retained in the output map.
217        * The null cells in the input cost map can be assigned a positive cost with the null_cost option.
218        * When input map null cells are given a cost with the null_cost option, the corresponding cells in the output map are no longer null cells. When specified null_cost=0.0, the movement transparently cross null cells which then propagate the adjacent costs.
219        * By using the -n flag, the null cells of the input map will be retained as null cells in the output map.
220      * -'''k''' flag:
221        * Use Knight’s move to improve the accuracy of the output by growing cost distance surface outwards in 16 directions instead of 8 directions by default.
222        * Computes slower, but more accurate
223    * '''Algorithm:'''
224      * Calculation begins with starting points.
225      * Cells (from starting points to the neighboring cells growing in 8 or 16 directions) are put into a list, on which the cell with the lowest cumulative cost is selected for computing costs to the neighboring cells.
226      * Neighbors are put into the list and originating cells are removed from the list.
227      * This process continues until the list is empty.
228      * A binary tree with an linked list at each node in the tree is used for efficiently holding cells with identical cumulative costs.
229      * As the algorithm works through the dynamic list of cells it can move almost randomly around the entire area. It divides the entire area into a number of pieces and swaps these pieces in and out of memory as needed.
230    * '''Reference:'''[[BR]]
231      [http://grass.fbk.eu/gdp/html_grass64/r.cost.html]
147232
148233----