This week you will have a chance to practice what you have learned about linked data structures, dynamic memory allocation, and trees. You are to write a program that will allow the user to click in points on a square screen window. The program should automatically draw the points as small dots on the screen, and draw the quadtree spatial subdivision that partitions the screen into squares, so that no square has more than one point in it. The program should start with the entire window considered as a square. Each time a point is entered, if the square it is entered into now has more than one point, then subdivide the square into four equal sized squares. If none of the new squares has more than one point in it, then you are done. Otherwise, you must continue, subdividing the square that still has two points in it, until no square has more than one point. To see a demo of how the program should work, try running the program quadtree in the /usr/local/misc/courses/viza653/1999/examples subdirectory of the course directory.
To keep track of the points, you are to use a quadtree data structure. Each node in the quadtree should record its own position and size. If the node is a leaf node, and it contains a point, then the node should record the position of the point. If the node is a non-leaf node, it should contain pointers to its four sub-quadtree children.
Your program should open the window, and should respond to callbacks to service the mouse button and to automatically redraw the screen if the display is covered and then uncovered. The program should not quit until quit is selected from the window menu.
Please submit your results using the standard submit procedure.