这个作业是用C语言完成计算机图形学的数据结构

CMSC 420 ASSIGNMENT: A DATA STRUCTURE FOR
COMPUTER GRAPHICS

1 REGION-BASED QUADTREES
The quadtree is a member of a large class of hierarchical data structures that are based on the principle
of recursive decomposition. As an example, consider the point quadtree of Finkel and Bentley [3] which
should be familiar to you as it is simply a multidimensional generalization of a binary search tree. In two
dimensions each node has four subtrees corresponding to the directions NW, NE, SW, and SE. Each subtree
is commonly referred to as a quadrant or subquadrant. For example, see Figure 2 where the correspondence
of a quadtree of 8 nodes to the data of Figure 1 is presented. In our presentation we shall only discuss twodimensional quadtrees although it should be clear that what we say can be easily generalized to more than
two dimensions. For the point quadtree, the points of decomposition are the data points themselves (e.g., in
Figure 2, Chicago at location (35,40) subdivides the two dimensional space into four rectangular regions).
Requiring the regions to be of equal size leads to a variant of the region quadtree of Klinger [5,6,8,9]. This
data structure was developed for representing homogeneous spatial data and is used in computer graphics,
image processing, geographical information systems, pattern recognition, and other applications. Its use in
computer graphics is rooted in the work of Warnock [11] who applied it to hidden surface elimination. For
a good introduction to computer graphics, see the texts by Foley, van Dam, Feiner, and Hughes [4] and
Newman and Sproull [7].

As an example of the region quadtree, consider the region shown in Figure 3a which is represented by
a 23 × 2
3 binary array in Figure 3b. Observe that 1s correspond to picture elements (termed pixels) which
are in the region and 0s correspond to picture elements that are outside the region. The region quadtree
representation is based on the successive subdivision of the array into four equal-size quadrants. If the array
does not consist entirely of 1s or 0s (i.e., the region does not cover the entire array), then we subdivide
it into quadrants, subquadrants, … until we obtain blocks (possibly single pixels) that consist entirely of
1s or entirely of 0s. For example, the resulting blocks for the region of Figure 3b are shown in Figure 3c.
This process is represented by a quadtree in which the root node corresponds to the entire array, the four
sons of the root node represent the quadrants, and the leaf nodes correspond to those blocks for which no
further subdivision is necessary. Leaf nodes are said to be BLACK or WHITE depending on whether their
corresponding blocks are entirely within or outside of the region respectively. All non-leaf nodes are said to
be GRAY. The region quadtree for Figure 3c is shown in Figure 3d.
2 PR QUADTREES
There are a number of ways of adapting the region quadtree to represent point data. If the domain of data
points is discrete, then we can treat data points as if they are BLACK pixels in a region quadtree. If this
is not the case, then the data points cannot be represented since the minimum separation between the data
points is unknown. This leads us to an adaptation of the region quadtree to point data which associates
data points (that need not be discrete) with quadrants. In order to avoid confusion with the point and
region quadtrees we call the resulting data structure a PR quadtree (P for point and R for region). The PR
quadtree is organized in the same way as the region quadtree. The difference is that leaf nodes are either
empty (i.e., WHITE) or contain a data point (i.e., BLACK) and the values of its coordinates.

2.1 INSERTION
Nodes in the PR quadtree consist of two types of records. The record’s type depends on whether it corresponds to a terminal or non-terminal node. This information is stored in the NODETYPE field of the
record. We use P to denote a pointer to the record. Non-terminal nodes have four fields in addition to the
NODETYPE field. These four fields are termed SON(P,I) where I corresponds to one of the four principal
directions. In addition to the NODETYPE field, terminal nodes have the following three fields. NAME
contains descriptive information about the node (e.g., city name, etc.). XCOORD and YCOORD contain
the x and y coordinate values, respectively, of the data point. We assume that each data point is unique
– i.e., it is associated with just one name. If more than one data point were permitted to have the same
coordinate values, then an overflow list would be required at each data point node. The empty PR quadtree
is represented by a pointer to a WHITE node. .PR In order to cope with data points that lie directly on
one of the quadrant lines emanating from a subdivision point, we adopt the convention that quadrants NE
and SE are closed with respect to the x coordinate and quadrants NW and NE are closed with respect
to the y coordinate. This means that quadrants NW and SW are open with respect to the x coordinate
and quadrants SW and SE are open with respect to the y coordinate. For example, in Figure 4, Mobile
with coordinate values (50,10) lies in quadrant SE of the tree rooted at (50,50). Using this convention, the
function PRCOMPARE, given below, determines the quadrant in which a given data point lies relative to a
grid subdivision point.