Hostname: page-component-cb9f654ff-qc88w Total loading time: 0 Render date: 2025-08-07T00:39:36.532Z Has data issue: false hasContentIssue false
  • English
  • Français

Oct-tree terrain modelling methods forterrain reference navigation systems

Published online by Cambridge University Press:  04 July 2016

D. J. Allerton  and
M. C. Gia
D. J. Allerton
Affiliation:
Department of AvionicsCollege of AeronauticsCranfield University, UK
M. C. Gia
Affiliation:
Department of AvionicsCollege of AeronauticsCranfield University, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper describes the use of oct-trees to representdigitised terrain elevation data (DTED) in terrainreference navigation (TRN) systems. Oct-treesprovide a regular method to represent digitisedterrain data where the level of detail of theterrain is encoded in the tree structure. The use ofoct-trees also provides a basis for a significantreduction in the on-line storage requirement forDT-EDs. A method of encoding using Morton orderingis introduced which allows DTEDs to be accessed asoct-trees and quad-trees where the tree structuresare represented as pointerless structures.Algorithms to construct and access terrain oct-treesare presented which form a set of access primitivesfor tree operations required in TRN applications.The paper concludes with examples to illustrate theefficiency of the methods described in the paper fortwo DTEDs, in terms of performance of the treeaccess operations and reductions in storage.

Information

Type
Research Article
Information
The Aeronautical Journal , Volume 100 , Issue 995 , May 1996 , pp. 157 - 164
Copyright
Copyright © Royal Aeronautical Society 1996 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

1. Bennett, P.J. Enhanced navigation and display from passive terrain reference avionics, IEEE Position Location and Navigation Symposium, November 1988, pp 209–216.Google Scholar
2. Priestley, N. Terrain reference navigation, IEEE Position, Location and Navigation Symposium, 1990, pp 482–489.Google Scholar
3. Weber, J.W. Future electronic map systems, IEEE National Aerospace and Electronics Conference, 1984, pp 106–111.Google Scholar
4. Barfield, F., Probert, J. and Browning, D. All terrain ground collision avoidance and manoeuvring terrain following for automated low-level night attack, IEEE AES Systems Magazine, pp 40–47, March 1993.Google Scholar
5. Barney, G. Enhanced terrain masked penetration program, IEEE National Aerospace and Electronics Conference, 1984, pp 90–96.Google Scholar
6. Zelenka, R.E. >Integration of radar altimeter, precision navigation and digital terrain data for low-altitude flight, AIAA-92-4420-CP, 1992, pp 605–615.Integration+of+radar+altimeter,+precision+navigation+and+digital+terrain+data+for+low-altitude+flight,+AIAA-92-4420-CP,+1992,+pp+605–615.>Google Scholar
7. Creel, E.E. and Fellerhoff, J.R. Data compression techniques for use with the SIT AN algorithm, IEEE Position Location and Navigation Symposium, November 1986, pp 309–315.Google Scholar
8. Cambron, T.M., Snyder, F.B. and Fellerhoff, J.R. Implementation of the SITAN algorithm in the digital terrain management and display system, IEEE National Aerospace and Electronics Conference, 1985, pp 78–86.Google Scholar
9. Klinger, A. and Dyer, C.R. Experiments in picture representation using regular decomposition, Comp Graphics Image Process, Jan 1976, 5,(1), pp 68–105.Google Scholar
10. Samet, H. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Reading, MA, 1990.Google Scholar
11. Gargantini, I., An effective way to represent quadtrees, Comms ACM, December 1982, 25, (12), pp 905–910.Google Scholar
12. Fabrini, I. and Montani, C. Autumnal quadtree, Comp J, 1986, 29, (5), pp 472–474.Google Scholar
13. Menon, S., Gao, P. and Smith, T.R. Multi-coloured quadtrees for GIS: exploiting bit-parallelism for rapid boolean overlay, Proc International Symposium on GIS, 2, Arlington, VA, November 1987, pp 371–383.Google Scholar
14. Cebrian, J.A., Mower, J.E. and Mark, D.M. Analysis and display of digital elevation models within a quadtree-based GIS, Proc Auto-Carto, 7, Washington DC, March 1985, pp 55–64.Google Scholar
15. Chen, Z.T. and Tobler, W.R. Quadtree representations of digital terrain, Proc Auto-Carto, 1, pp 475–484, London, September 1986.Google Scholar
16. Mark, D.M., The use of quadtrees in geographic information systems and spatial data handling, Proc Auto-Carto London, 1, London, September 1986, pp 517–526.Google Scholar
17. Shaffer, C.A., Samet, H. and Nelson, R.C. Technique Report, QUILT: A Geographic Information System Based on Quadtrees, University of Maryland, February 1989.Google Scholar
18. Morton, G.M. A Computer Orientated Geodetic Database and a New Technique, Ottawa, Canada, 1966.Google Scholar
19. Allerton, D.J. and Gia, M.C. The application of oct-trees in air borne terrain guidance systems, RIN & DGON Digital Mapping and Navigation Conference, London, paper 11, November 1992.Google Scholar
20. Gargantini, I. Linear oct-trees for fast processing of three-dimensional objects, Comp Graphics Image Process, December 1982, 20, (4), pp 365–374.Google Scholar
21. Lauzon, J.P., Mark, D.M., Kikuchi, L. and Guevara, J.A. Two-dimensional run-encoding for quadtree representation, Comp Graphics Image Process, April 1985, 30, (1), pp 56–69.Google Scholar
22. Aho, A.V., Hopcroft, J.E. and Ullman, J.D. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.Google Scholar
23. Gargantini, I. Detection of connectivity for regions by linear quadtrees, Comps Maths Applics, 1982, 8, (4), pp 319–327.Google Scholar
24. Bresenham, J.E. Algorithm for computer control of a digital plotter, IBM Systems J, 1965, 4, (1), pp 25–30.Google Scholar
25. Gia, M.C. Design of Data Structures for Terrain Reference Navigation, PhD Thesis, Cranfield University, 1994.Google Scholar