这个作业是用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.