International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B7. Istanbul 2004
cable or many relay towers. That solution is the multiple :
observer visibility problem. Mars also has no useful iono-
sphere, tho its satellites do have stable orbits. A related
application is to site the observers to minimize their visi-
bility, which is appropriate if they are visual nuisances that
we wish to hide.
The terrain data structure used here is a matrix of eleva-
tions, often a 1201 x 1201 USGS level-1 Digital Elevation
Model cell. The relative advantages and disadvantages of
this data structure versus a triangulation are well known,
and still debated; the competition improves both alterna-
tives. This current paper utilizes the simplicity of the ele-
vation matrix, which leads to greater speed and small size,
which allows larger data sets to be processed.
For distances much smaller than the earth’s*radius, the ter-
rain elevation array can be corrected for the earth’s curva-
ture, as follows. For each target at a distance D from the
observer, subtract E from its elevation, where E is the
earth's radius. (The relative error of this approximation is
(2. It is sufficient to process any cell once, with an
observer in the center. The correction need not changed
for different observers in the cell, unless a neighboring cell
is being adjoined. Therefore, since it can be easily cor-
rected for in a preprocessing step, our visibility determina-
tion programs ignores the earth's curvature.
The radius of interest, R, out to which we calculate visi-
bility, has no relation to the distance to the horizon, but is
determined by the technology used by the observer. E.g.,
if the observer is a radio communications transmitter, dou-
bling R causes the required transmitter power to quadru-
ple. If the observer is a searchlight illuminating diffusely
reflecting targets, then its required power is proportional to
RS,
In order to simplify the problem under study enough to
make some progress, this work also ignores factors such as
vegetation that need to be handled in the real world. We as-
sume that it’s possible, and a better strategy, to incorporate
them only later.
The ability to process large, hi-res terrain datasets is impor-
tant. Demonstration programs may be useless for real ap-
plications if their time and space requirements limit them
to toy datasets. Nevertheless, it is worthwhile to measure
how good are the results computed on low-res datasets.
For instance, the current state of battery technology lim-
its the computation and communication speeds of portable
devices, regardless of other hardware advances. For in-
stance, subject to various caveats, doubling a microproces-
sor's speed doubles its power consumption.
2 OURSITING TOOLKIT
This toolkit, whose purpose is to select a set of observers
to cover a terrain cell, consists of four core C++ programs,
supplemented with zsh shell scripts, Makefiles, and as-
sorted auxiliary programs, all running in linux.
1198
1. VIX calculates approximate visibility indices of ev-
ery point in a cell. VIX takes several user parameters:
R, the radius of interest, H, the observer and target
height, and 7, a sample size. VIX reads an elevation
cell. For each point in the cell in turn, VIX considers
that point as an observer, picks 7 random targets uni-
formly and independently distributed within R of the
point, and computes what fraction are visible. That is
this point’s estimated visibility index. 7" = 20 to 30
appears sufficient.
. FINDMAX selects a manageable subset of the most
visible tentative observers from VIX's output, to be
called the top observers. This is somewhat subtle
since there may be a small region containing all points
of very high visibility, such as the center of a lake
surrounded by mountains. Since multiple close ob-
servers are redundant, we force the tentative observers
to be spread out as follows.
(a) Choose an appropriate value for £, the desired
number of top observers. Experimentally, £ ~
800 suffices to cover 80% of the terrain, while a
95% coverage requires L = 3000.
(b) Partition the map cell into about £/K equal-
sized smaller blocks. Experimentally, K = 2
is good.
(c) In each block, find the Æ points of highest
approximate visibility index (as determined by
VIX). If there are more than K points with
equally high visibility index, then select K at
random (using a multiplicative hash function of
the point's coordinates as a secondary sort key),
to prevent a bias towards selecting points all on
one side of the block. If a block has fewer than
K points, then return all its points.
3. VIEWSHED finds the viewshed of a given observer at
height H out to radius, R. The procedure, based on
Franklin and Ray (1994) and Ray (1994), goes as fol-
lows.
(a) Define a square of side 2R centered on the ob-
server.
(b) Consider each point around the perimeter of the
square to be a target in turn.
(c) Run a sight line out from the observer to each
target calculating which points adjacent to the
line, along its length, are visible, while remem-
bering that both the observer and target are prob-
ably above ground level.
(d) If the target is outside the cell, because R is
large or the observer is close to the edge, then
stop processing the sight line at the edge of the
cell.
One obvious “improvement”, when the target is out-
side the cell, would be to move the target in to the
edge of the cell before running the sight line. How-
ever, this would cause the computed viewshed to de-
pend slightly on R, which looks bad.
