Next: PM Pseudocode Up: Part 2: Sorted Map Previous: Anonymous Inner Classes
For part 2 of the project, you must implement a PM3 to receive full credit. In part 3 you will be able to adopt a working PM3 quadtree from part 2; so, a working PM3 quadtree will be required, and test-able with the primary input, before you submit it.
PM2 Quadtree not required in the projects.
For this project, and depending on which option you implement, we have a few new fun operations we can perform on spatial maps. Since the PM quadtrees also store line segments, we're creating roads.
We will also have airports and terminals which cannot be connected to any other city. And once we have roads in this map, we can party.
The radius search is still in, plus this time around the radius search will also report any roads that exist in that radius. We also introduce two new types of operations:
Nearest City to Segment: Given a road S, locate the nearest city. Java gives you the geometric calculations so you won't have to muck around with the math (like the folks did in C++ years ago) but you will still need to come up with a suitable algorithm to do this efficiently.
Nearest Segment to Point: Given a point P, locate the nearest road. If you're clever you can roll this operation and the previous one into a single operation where the type of geometry is irrelevant (my geometry classes attempt to make the type transparent by providing common functions like intersects() and distance() - if you use these or roll your own with similar characteristics, you can write one "nearest object to object" where it's irrelevant whether those objects are points or line segments. It's all a matter of distance, after all.
One of the convenient features of PM quadtrees is that they are deterministic, meaning all quadtrees ARE created equal. The order in which objects are inserted is irrelevant to the resulting structure, and that structure is invariant. All your quadtrees should look exactly the same, which means we can and will be using diff to test your quadtrees. Thus, you're not required to implement any specific interface, Java provided or otherwise. You can implement your quadtrees however you want.
To make your quadtrees convenient for Part 3 the spatialWidth and spatialHeight attributes of the <commands> tag will always be powers of 2. e.g. 128, 256, 512, 1024, so on. This makes dividing the regions a very quick operation. If the values are negative or not numbers use the standard "illegal attribute" error message. Java has bit shift operations that you are welcome to take advantage of (although javac probably converts x/2 into x»1). Recall shifting the bits of a positive integer one to the right has the effect of dividing it by 2 (and rounding down) - similarly x«1 multiplies x by 2; x«2 multiplies x by 4, and so forth. Using the » operator on ints for division makes you look smart and doesn't leave compiler optimization to chance. And obviously it doesn't work on floats. Also, for this part we will not create partitions in your PM Quadtree deep enough to create regions whose area is less than 1x1. Thus we are limiting the height of the tree based on max(spatialWidth,spatialHeight). (Note that I said "based on" not "exactly equal to").
Note: For our PM Quadtrees, if a city or any portion of a line segment lands on any of a region's borders, that city or line is added to that region. This is consistent with every quadrant being closed on all four boundaries
For instance, suppose you had a simple instance where your quadtree occupied an area defined by (0,0), (1024,1024). The center point of the first partition that will be created, therefore, would be at (512,512). If the first road you add contains a city at (512,512), this city would be added to all four of the children of the resulting gray node, since the city touches the corners of each of those four regions.
Our test files will include a new attribute in the <commands> tag, pmOrder, whose value can be one of the following:
1 - PM1 Quadtree 3 - PM3 Quadtree
We will run your code through tests of various orders, and give you credit for all of the ones you passed, scaling to reflect the total amount of credit we're offering for each of the options. If you are not supporting certain orders in your project, you can print anything you want (or nothing at all) when you encounter a pmOrder attribute whose value indicates something you didn't do. In the end you'll just fail the test anyway regardless of what you print since we'll be checking via diff. Regardless of which PM options you implement, always print out a <results/> tag so that the XMLParser doesn't throw an exception when we reroute your output back into the parser to auto-format it for diffing.
We will not speed test your PM Quadtree specifically because its complexity is not good as far as add and remove are concerned. We will speed test your ``nearest city/nearest segment'' in the same way we speed tested your spatial map from the previous part; so you'll have to spend some time coming up with a reasonable average case algorithm. Note that no matter what you do the complexity will still be O(n), but on average this should take drastically less time.
We will grade your PM primarily by using <printPMQuadtree />, since all PM Quadtrees given the same geometry should be identical. Another nice feature of the PM is that they are also identical regardless of the order of operations. In other words their structure is deterministic for inputs. That is, of course, because they are tries.