Graphics Reference
In-Depth Information
Figure 5.40.
Quadtree examples.
Figure 5.41.
Quadtree structure.
The binary nature of the algorithm suggests a binary tree structure, but this is not
as efficient as the quadtree in the two-dimensional case and octree in the three-
dimensional case.
Quadtrees.
Assume that a planar region is contained in a rectangle. For example,
consider the shaded region
R
in Figure 5.40(a). Now change the general algorithm
above to the following:
(1) If the region covers the current rectangle or is disjoint from it, then stop sub-
dividing and return that fact; otherwise,
(2) divide the rectangle into four equal parts and repeat these two steps for each
of the subrectangles.
For the region
R
in Figure 5.40(a) we shall end up with a subdivision as indicated
in the figure. The region can therefore be represented by a tree structure, called
a
quadtree
, where each node has up to four nonempty subtrees. If we label the four
subrectangles of a rectangle as indicated in Figure 5.41(a), then the Figure 5.41(b)
shows the tree structure for
R
.
Quadtrees can also be used to represent curved regions as shown in Figure 5.40(b)
by modifying the criteria for when one quits subdividing in one of two ways:
