NCGIA Core Curriculum in Geographic Information Science
URL: "http://www.ncgia.ucsb.edu/giscc/units/u057/u057.html"
 

Unit 057 - Quadtrees and Scan Orders

by Michael F. Goodchild, University of California, Santa Barbara

This unit is part of the NCGIA Core Curriculum in Geographic Information Science. These materials may be used for study, research, and education, but please credit the author, Michael F. Goodchild, and the project, NCGIA Core Curriculum in GIScience. All commercial rights reserved. Copyright 1997 by Michael F. Goodchild.

Your comments on these materials are welcome. A link to an evaluation form is provided at the end of this document.


Advanced Organizer

Topics covered in this unit

Learning Outcomes

Full Table of Contents

Instructors' Notes

Metadata and Revision History


Unit 057 - Quadtrees and Scan Orders

1. Scanning the raster

1.1 Bostrophedon scan order

 
63  62  61  60  59  58  57  56 
48  49  50  51  52  53  54  55 
47  46  45  44  43  42  41  40 
32  33  34  35  36  37  38  39 
31  30  29  28  27  26  25  24 
16  17  18  19  20  21  22  23 
15  14  13  12  11  10 
   
 

1.2. Morton Order

 
42  43  46  47  58  59  62  63 
40  41  44  45  56  57  60  61 
34  35  38  39  50  51  54  55 
32  33  36  37  48  49  52  53 
10  11  14  15  26  27  30  31 
12  13  24  25  28  29 
18  19  22  23 
16  17  20  21 
 

1.3. Pi-order

 
21  22  25  26  37  38  41  42 
20  23  24  27  36  39  40  43 
19  18  29  28  35  34  45  44 
16  17  30  31  32  33  46  47 
15  12  11  10  53  52  51  48 
14  13  54  55  50  49 
57  56  61  62 
58  59  60  63 
 

2. Quadtrees

 
 

2.1 Additional quadtree example


3. Applications of quadtrees


4. Addressing quadtree spaces


5. References

Goodchild, M.F. and A.W. Grandfield (1983) Optimizing raster storage: an examination of four alternatives. Proceedings, AutoCarto 6, Ottawa 1: 400-407.

 
Mark, D.M. (1990) Neighbor-based properties of some orderings of two-dimensional space. Geographical Analysis 22: 145-157.

 
Samet, H. (1990a) The Design and Analysis of Spatial Data Structures. Reading, MA: Addison-Wesley.

 
Samet, H. (1990b) Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Reading, MA: Addison-Wesley.

6. Exam and discussion questions

  1. Why doesn't the Morton order perform better as a compression device?

  2.  
  3. What other potential ways are there of scanning a raster?

  4.  
  5. Discuss the research reported by Mark (1990).

  6.  
  7. Given the arguments presented above, why haven't quadtree-based raster GISs done better in the commercial marketplace (why did TYDAC add other raster structures besides quadtrees to SPANS)?

  8.  
  9. Try to determine the spatial indexing scheme used by your favorite GIS. How could you deduce the nature of the indexing scheme by watching the system's behavior?

Evaluation

We are very interested in your comments and suggestions for improving this material.  Please follow the link above to the evaluation form if you would like to contribute in this manner to this evolving project..


Citation

To reference this material use the appropriate variation of the following format:

The correct URL for this page is: http://www.ncgia.ucsb.edu/giscc/units/u057/u057.html.
Created: August 8, 1997.  Last revised: October 23, 1997.


Gateway to the Core Curriculum