r.viewshed is a module that computes the viewshed of a point on a raster terrain. That is, given an elevation raster, and the location of an observer, it generates a raster output map showing which cells are visible from the given location. The algorithm underlying r.viewshed minimizes both the CPU operations and the transfer of data between main memory and disk; as a result r.viewshed runs fast on very large rasters.
Viewpoint (coordinate parameter): For the time being the viewpoint is assumed to be located inside the terrain. The viewpoint location is given in map coordinates.
Output: The output map may have one of three possible formats, based on which flags are set.
By default, if no flag is set, the output is in angle-mode, and each point in the output map is marked as NULL if the point is not visible or the respective point in the elevation map is NULL. Otherwise, a value in [0, 180] representing the vertical angle with regard to the viewpoint, in degrees, if the point is visible. A value of 0 is directly below the specified viewing position, 90 is due horizontal. The angle to the cell containing the viewing position is undefined and set to 180.
If the -b flag is set, the output is in boolean-mode, and each point in the output map is marked as:
If the -e flag is set, the output is in elevation-mode, and each point in the output map is marked as:
If you wish to identify the area of the map which is within the search radius but not visible, a combination of r.buffer and r.mapcalc can be used to create a negative of the viewshed map.
By default the elevations are not adjusted for the curvature of the earth. The user can turn this on with flag -c.
Observer elevation: By default the observer is assumed to have height of 1.75 map units above the terrain. The user can change this using option obs_elev. The value entered is in the same units as the elevation.
Target elevation: By default the target is assumed to have height of 0 map units above the terrain. The user can change this using option tgt_elev to determine if objects of a given height would be visible. The value entered is in the same units as the elevation.
Maximum visibility distance: By default there is no restriction on the maximum distance to which the observer can see. The user can set a maximum distance of visibility using option max_dist. The value entered is in the same units as the cell size of the raster.
Main memory usage: By default r.viewshed assumes it has 500MB of main memory, and sets up its internal data structures so that it does not require more than this amount of RAM. The user can set the amount of memory used by the program by setting the memory_usage to the number of MB of memory they would like to be used.
Ideally, the user should specify on the command line the amount of physical memory that is free for the program to use. Underestimating the memory may result in r.viewshed running in external mode instead of internal, which is slower. Overestimating the amount of free memory may result in r.viewshed running in internal mode and using virtual memory, which is slower than the external mode.
The core of the algorithm is determining, for each cell, the line-of-sight and its intersections with the cells in the terrain. For a (square) grid of n cells, there can be O(n 1/2) cells that intersect the LOS. If we test every single such cell for every point in the grid, this adds up to O(n3/2) tests. We can do all these tests faster if we re-use information from one point to the next (two grid points that are close to each other will be intersected by a lot of the same points) and organize the computation differently.
More precisely, the algorithm uses a technique called line sweeping: It considers a half-line centered at the viewpoint, and rotates it radially around the viewpoint, 360 degrees. During the sweep it keeps track of all the cells that intersect the sweep line at that time; These are called the active cells. A cell has 3 associated events: when it is first met by the sweep line and inserted into the active structure; when it is last met by the sweep line and deleted from the active structure; and when the sweep line passes over its centerpoint, at which time its visibility is determined. To determine the visibility of a cell all cells that intersect the line-of-sight must be active, so they are in the active structure. The algorithm looks at all the active cells that are between the point and the viewpoint, and finds the maximum gradient among these. If the cell's gradient is higher, it is marked as visible, whereas if it is lower, it is marked as invisible.
For a (square) raster of n point in total, the standard viewshed algorithm uses O(n sqrt(n))= O(n3/2) time, while the sweep-line algorithm uses O(n lg n) time. This algorithm is efficient in terms of CPU operations and can be also made efficient in terms of I/O-operations. For all details see the REFERENCES below.
|The sweep-line.||The active cells.|
g.region rast=elev_lid792_1m -p r.viewshed input=elev_lid792_1m output=elev_lid792_1m_viewshed \ coordinate=638728.087167,220609.261501 obs_elev=5.0
g.region rast=elevation.10m r.viewshed input=elevation.10m output=viewshed \ coordinate=598869,4916642 mem=800
Laura Toma (Bowdoin College): email@example.com
Yi Zhuang (Carnegie-Mellon University): firstname.lastname@example.org
William Richard (Bowdoin College): email@example.com
Last changed: $Date$