This thesis describes the design of a data structure for use with Digitised Terrain
Elevation Data (DTED) in Terrain Reference Navigation (TRN) systems. The data
structure is based on a variant of quad-tree and oct-tree data structures to provide an
efficient representation of terrain in terms of storage requirements and acccss
operations. These data structure are applied to flight path planning operations in mission
management applications. The algorithms developed for flight path planning have becri
implemented in the C programming language for a standard PC.
Current research in TRN systems is reviewed and attention is given to the use
of hierarchical data structures to cope with the potentially large data base needed for
DTED files. Data structure combining quad-trees and oct-trees are developed with an
emphasis on data reduction using pointerless trees and the use of locational codes to
provide straightforward mapping between quad-trees and oct-trees, in other words,
between two-dimensional co-ordinates and three-dimensional co-ordinates. Analysis of
these algorithms is described for two DTED files to illustrate storage improvements and
to verify a set of database access operations.
These data structures are applied to problems of flight path planning where the
navigation space comprises objects above a specific altitude and this three-dimensional
space is searched for a flight path which avoids the obstacles and satisfies specific
operational criteria. Algorithms are developed to extract a visibility graph from the
terrain database and to determine the preferred flight path from a set of paths which
satisfy defined constraints. Several search techniques are developed which exploit the
efficiency of the quad-tree and oct-tree data structures. These methods are extended to
real-time flight-path planning where predicted times for access operations are used to
direct flight path extraction by varying the tree resolution during computation of the
flight path.
A comprehensive set of results are provided to illustrate:
the storage efficiency of quad-tree and oct-tree data structures
the application of pyramid structures to represent navigation space
analysis of the time to compute the visibility graph and to extract flight paths
integration of these methods with a real-time mission management simulation
on a PC
The thesis draws conclusions on the efficiency of these techniques for the
represcntation of DTEDs and to access objects in TRN systems. It is observed that the
use of hierarchical data structures in the form of quad-trees and oct-trees offers
significant improvement in accessing DTEDS, for future use in TRN systems. The
thesis concludes by outlining areas of further work where the techniques can be further
&N, cloped for applications in mission management and navigation using DTED files.
| Identifer | oai:union.ndltd.org:CRANFIELD1/oai:dspace.lib.cranfield.ac.uk:1826/4184 |
| Date | 05 1900 |
| Creators | Gia, M. C. |
| Contributors | Allerton, David J. |
| Publisher | Cranfield University |
| Source Sets | CRANFIELD1 |
| Language | English |
| Detected Language | English |
| Type | Thesis or dissertation, Doctoral, PhD |
Page generated in 0.0024 seconds