Simple Linear Quadtree

A first step toward better exploitation of thematic maps was the use of simple Linear quadtrees (SL-trees) [10]. In fact, the latter structure is the original Linear quadtree [5], enriched with feature information. During the procedure of successive decomposition, once a homogeneous block is reached, the information about the particular feature that was found in this block is retained together with the corresponding leaf quadcode. More specifically, now each quadtree leaf will be characterized by two fields:

1. the locational key, whose digits reflect successive quadrant subdivision,
2. the value field, which contains the id of the feature that exists in the specific node.

Then, the entries for all quadtree leaves will be inserted in a B$^+$tree, where the locational key will serve in traversing the latter structure.

Figure: An 8x8 image.

Figure: The feature-id table of the previous figure.

Figure: The Quadtree representing the image of Fig. 1.

In Figure , an 8x8 image is depicted which contains four non-overlapping features. The feature id's are listed in the table in the right part of Figure . In Figure the homogeneous leaves of the corresponding quadtree are shown, whereas internal nodes are represented with gray color. Next, the list of generated locational codes is depicted. For example, the leaf with locational code 132 has a value field equal to 2, since the feature contained in the corresponding subimage is the one having id=2.

 

(111,1), (112,3), (113,0), (114,1), (120,1), (131,0),

(132,2), (133,2), (134,0), (140,1), (210,0), (220,1),

(230,1), (240,0), (310,2), (320,0), (330,2), (340,3), (400,0)