Programming Assignment 2 - Quad Trees

Due Date

See the assignment turn-in page (last modified on 16 October 2007) for instructions on turning in your assignment.

Background

A quad tree is similar to a binary search tree, except a quad tree can have up to four children rather than just two. Like a binary search tree, a quad tree is ordered, although what the ordering is depends on how the quad tree is being used.

A quad tree's four children make it a useful data structure for representing two-dimentional data; each child represents a quadrant of the data.

Each child can further subdivide its quadrant as needed, or be a leaf node with no futher subdivisions. Whether to subdivide a quadrant or not depends on the data being stored and how it will be used. For example, if the quad tree represents a binary (black-white) image, the typical rule is to stop subdividing a quadrant when it has only black or white pixels, or it's small enough as determined by the application using the quad tree.

The Problem

void quad_tree::init(int * characters);

std::string quad_tree::match(double * points);

These prototypes are declared in the file quad-tree.h in the /export/home/class/cs-306/a2 assignment directory; this file should not be included in the files you turn-in. These are procedures in a name space rather than public methods in a class. You may use classes to implement your solution, but you should make your data structure available via these two procedures. You may make other procedures or methods available, but they will be ignored by testing code. The code you turn-in should not contain a main(); one is provided by the testing code.

The quad_tree::init() procedure initalizes the quad tree with the characters it should be able to recognize. The quad_tree::match() procedure matches a point set against characters in the quad tree.

Input

There are two inputs: the initialization data and the point sets.

The initialization data is an integer array c with the following format:

c[0]: N, the number of characters.
c[1]: c₀, the first character represented.
c[2]: p₀, the number of points in the first character.
c[3]: x₀, the x coordinate of the first point of the first character.
c[4]: y₀, the y coordinate of the first point of the first character.
c[5]: x₁, the x coordinate of the second point (if it exists) of the first character.
And so on.

The point-set data has almost the same format as it had in the first assignment:

The difference is the first element is the character being represented.

Unlike the first assignment, the point-set data is not distorted by affine transformations (no rotations or scaling). However,

1. If the point set represnets a characer, some of the points may be missing, or there may be extra points.

2. A point may be jittered around a small neighborhood of where the point should be if it were a point in a character.

Output

quad_tree::match() should return a string containg the characters it has matched against the input point set. If no characters were matched, the string will be empty. Matched characters appear in the string in no particular order.

If either of the two input arrays are malformed, your code should print an informative error message to std-err and end execution with no further processing.

Testing

The procedure

int * letters();

returns an array in the format described above describing the characters that should be matched against. The array returned should be freed by the caller.

The procedure

double * candidate(int i);

returns a point set in the format described above corresponding to the ith character in the array returned by letters(). The array returned should be freed by the caller.

These procedures should not be called by your quad-tree code; they are to be used by code you write to test your quad-tree code. The procedures can be found in the files letters.h and letters.cc in the /export/home/class/cs-306/a2 assignment directory. These files should not be included in the files you turn-in.

Credits

Image:Quad tree bitmap.svg, placed in the public domain by Wojciech Mula