|
Posted by rgc on February 27, 2006, 2:51 pm
Please log in for more thread options
The following article appears on page 44 of the January 2006 issue of
NASA Tech Briefs:
Using a Quadtree Algorithm To Assess Line of Sight
A matched pair of computer algorithms determines whether line of
sight (LOS) is obstructed by terrain. These algorithms were originally
designed for use in conjunction with combat-simulation software in
military training exercises, but could also be used for such commercial
purposes as evaluating lines of sight for antennas or determining what
can be seen from a "room with a view." The quadtree preparation
algorithm operates on an array of digital elevation data and only needs
to be run once for a terrain region, which can be quite large.
Relatively little computation time is needed, as each elevation value is
considered only one and one-third times. The LOS assessment algorithm
uses that quadtree to answer LOS queries. To determine whether LOS is
obstructed, a piecewise-planar (or higher-order) terrain skin is
computationally draped over the digital elevation data. Adjustments are
made to compensate for curvature of the Earth and for refraction of the
LOS by the atmosphere. Average computing time appears to be proportional
to the number of queries times the logarithm of the number of elevation
data points. Accuracy is as high as is possible for the available
elevation data, and symmetric results are assured. In the simulation,
the LOS query program runs as a separate process, thereby making more
random-access memory available for other computations.
These programs were written by Joseph Gonzalez, Robert Chamberlain,
Eric Tailor, and Gary Gutt of Caltech for NASA's Jet Propulsion
Laboratory. For further information, access the Technical Support
Package (TSP) free on-line at www.techbriefs.com/tsp under the Software
category.
This software is available for commercial licensing. Please contact
Karina Edmonds of the California Institute of Technology at (818)
393-2827. Refer to NPO-40596.
| 
XML Sitemap