Definitions

• Terrain means elevation. Ignore surface features for now.
• Use a grid (matrix) of elevations (in this talk; I implemented TINs in 1973).
• Visibility Index: How much can a particular observer see?
• Viewshed: What, specifically, can a particular observer see?
• Multiple Observer Siting

Given some terrain...

Choose the smallest set of observers that will cover as much terrain as possible.

VIX - Find Approx Visibility Index of Each Point

• 1,442,401 points (aka observers): speed is essential.
• Choose a parameter, T, say T=10.
• Other parameters: observer ht, target ht, radius of interest.
• For each observer, select T targets at random. Run a line of sight to see if the target is visible.
• Number of targets visible by that observer: its approx visibility index.
• Program coded carefully. Each LOS test averages 8 microseconds on a 600 MHz Pentium.

Findmax - Select Observer Subset

• From the 1442401 points, select the best 1000.
• Best: highest visibility index and also well spaced (to correct for clusters of good points).

VIEWSHED

To determine which points within R, the radius of interest of the observer, are visible.

• Define a 2R by 2R square about the observer.
• Iterate around its perimeter.
• For each point on the perimeter, run a line of sight from the observer to it.
• See which points on that LOS are visible.
• The execution time per observer is proportional to R².
• If we had run LOSs to each point, instead of to each point on the perimeter, the time would have been much worse: R³.

Site - Find a good set of observers

We have a set of possible observers, with their viewsheds (stored as bitmaps). Now, select a subset that covers the terrain cell.

• This is a greedy algorithm.
• As we progress, we know the set of observers chosen so far, and C, the region that they cumulatively see (stored as a bitmap).
• To add another observer to the set:
  • Temporarily unite each remaining observer's viewshed with C, and calculate its area.
  • Pick the observer that results in the largest resulting area.
  • However, remember how much new area each possible observer would have added. In the next round, perhaps do not even consider this observer. This saves time.
• Update everything.