PM1 Design Requirements

PM1 quadtrees can contain points and edges. Edges are defined to have two different points as endpoints. Individual (or isolated) points can be viewed as ``edges with the same start and end point'', and should be inserted that way. Thus, a PM1 quadtree, in a sense, can be treated as a structure in which only edges are inserted. Feel free to use whichever abstraction makes the more sense to you. However, I will never use the term edge to refer to an isolated points.

The portion of a segment or edge contained in a PM1 quadtree node is called a q-edge, while the term point can be either an endpoint or an isolated point, unless otherwise stated.

The edges in a PM1 quadtree may not intersect. Given two lines, it is possible that they don't mathematically intersect but they may be very very close together, which for our purposes will be considered an intersection. (The reason is because if you get two lines that are too close together, you will continue to partition your PM1 quadtree until your stack overflows.) Therefore, we will set a maximum depth for your PM1 tree of 20 levels. If you discover that you must create more than 20 levels in your PM1 quadtree to store two edges, we will consider them to be an intersection and will reject the new edge.

Additionally, your PM1 quadtree should adhere to the following rules:

1. A black node can contain exactly one (1) isolated point.
2. A black node cannot contain a point and a segment unless that point is an endpoint of the segment or q-edge.

3. A black node can contain exactly one q-edge, unless the q-edges share an endpoint in the black node.
4. If a point falls on the boundary between more than one node, then it must be added to every node that it intersects (a point may be contained in up to four leaf nodes).

5. If even one point of a q-edge falls on the boundary of more than one node then it must be added to all of those nodes as above. (A single q-edge can of course appear in a lot of nodes).

6. The tree must at all times be minimal- that is, there must never be a smaller tree which follows all of the above rules and still contains all of the same data. This should only be a complicated issue during deletion.

7. The maximum depth of your PM1 quadtree is 20 levels. (Warning: try to count correctly, meaning that the PM1 quadtree of maximal depth has levels numbered from 0 to 19 inclusive.)

Also, by now I hope you've been taking advantage of the Java API, especially the java.awt.geom libraries. <cough> Point2D, Line2D, Rectangle2D, Ellipse2D <cough> Ahem. Sorry about that...cold season.

Please note that although our PM1 quadtree is capable of storing all of the points of interest (e.g. sites, loci, etc) and tracks, it does not provide a very simple interface for performing shortest track calculations. As a result, you should still maintain an adjacency list to perform these types of calculations.