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.
This Brief includes a Technical Support Package (TSP).
Using a Quadtree Algorithm to Assess Line of Sight
(reference NPO-40596) is currently available for download from the TSP library.
Don't have an account?
Overview
The document is a Technical Support Package from NASA, specifically referencing NPO-40596 of NASA Tech Briefs. It aims to disseminate information about aerospace-related developments that have broader technological, scientific, or commercial applications. The package is part of the Commercial Technology Program, which seeks to make advancements accessible to various sectors.
One of the key focuses of the document is the use of a Quadtree Algorithm for assessing line of sight (LOS). This algorithm is significant in various applications, including military operations, urban planning, and telecommunications, where understanding visibility and obstruction is crucial. The document outlines the importance of accurate line of sight assessments, which can impact decision-making in both civilian and military contexts.
The document also references the Shuttle Radar Topography Mission (SRTM), which has provided high-resolution elevation data for much of the Earth's surface. This data is essential for constructing accurate digital elevation models (DEMs), which serve as the foundation for various analyses, including those involving line of sight. The integration of modern computing capabilities has enhanced the processing of this data, allowing for more sophisticated algorithms and models to be developed.
Additionally, the document discusses the SURF (Summer Undergraduate Research Fellowship) project, which aimed to optimize the TIN (Triangulated Irregular Network) construction process. This project was designed to address previous challenges in TIN construction and improve the quality of terrain modeling. The goal was to produce "superlative" TINs that could better represent the complexities of the terrain.
The document emphasizes the collaboration between various organizations, including the National Imagery and Mapping Agency (NIMA), which is tasked with providing mapping products to the U.S. armed services. This collaboration highlights the importance of integrating advanced technologies and methodologies in producing reliable and accurate mapping and modeling tools.
In summary, the Technical Support Package provides insights into the advancements in line of sight assessment using a Quadtree Algorithm, the significance of high-resolution elevation data from the SRTM, and the collaborative efforts to enhance terrain modeling through optimized TIN construction. It serves as a resource for those interested in aerospace technology and its applications across different fields.
