Microsoft Word – Worked Example – Grid and Quadtree Indexes
Worked Example – Grid and Quadtree Indexes
1. Create a Grid index and a Quadtree index for the following data. Your
grid should be at least 16 cells in size.
Your Quadtree index should have 4 children per node (hence Quadtree).
You can also assume that the page size on disk for the quadtree allows a
maximum of FOUR polygon references per leaf.
For the Quadtree, node order is: Top Left, Top Right, Bottom Left, Bottom
Right (in practice this will depend on the software being used)
Grid Content Grid Contents
AA 1 CA 4,5,8
AB 14 CB 8,9,13
AC CC 16
AD 19 CD
BA 2,3 DA 6,8
BB 10,11,12 DB 7,8
BC 12,15 DC
BD 18 DD 17
A B C D
D
C
B
A
2. Modify the indexes created above to include Polygons 20, 21, 22 and 23,
which have been inserted in the diagram below.
A B C D
D
C
B
A
Grid Content Grid Contents
AA 1 CA 4,5,8
AB 14,
20,22,23,21
CB 8,9,13
AC CC 16
AD 19 CD
BA 2,3 DA 6,8
BB 10,11,12 DB 7,8
BC 12,15 DC
BD 18 DD 17