3D Spatial Structures

As mentioned previously, your major task for this project will be designing and implementing your own structure. We've made it easier for you by giving you restraints on the roads that can be mapped. For a road to be mapped, both cities' remote coordinates must be the same. This tells us that the road exists within the scope of a single metropole and does not extend to any other metropole.

We will allow you to use either a PM1 or PM3 quadtree whenever possible, depending on which one you feel you implemented more solidly. That is, when pmOrder is not given, it is up to you to decide what value (1 or 3) you are more comfortable with. However, if pmOrder is specified, you are required to implement that particular type of PM Quadtree. We will also allow you to use whatever structure you want to aggregate the trees, as long as you can perform search queries on $O(\log n)$.

Your structure will still be graded using printPMQuadtree, but we now add remoteX and remoteY parameters to this command--you only have to print out one tree at a time. The tree you print out will be the metropole whose remote coordinates are (remoteX, remoteY).

Travel between different metropoles is only possible through airports. Airports correspond to isolated cities in Part 2. Like cities, airports have both remote and local coordinates, but airports are isolated instead of connected points. When an airport is mapped, a corresponding terminal is also mapped. Terminals have a road connecting to a city that is already mapped. After an airport is mapped, other terminals corresponding to that airport may also be mapped. To access an airport, you must first travel to one of its terminals. From the terminal, you travel directly to the airport, taking the shortest path, i.e. a straight line. Note that there is no road between the airport and the terminal (pretend there is some sort of shuttle service). Your adjacency list becomes more complicated compared to part 2, so implementing it as a separate class is more attractive.

Rather than write shortest path again, you will construct a minimum spanning tree for the graph consisting of all things mapped. You must use Prim's algorithm. Using another algorithm may not produce the same output. To break ties in the priority queue, always choose the city that comes last in asciibetical order. When outputting the tree, the children of a node should appear in reverse asciibetical order.

While finding nearest cities and airports are restricted to a specific metropole, ranging cities will encompass all possible cites in Part 3. Given remote coordinates x,y, you must return all cities part of any metropole whose remote coordinates are in range of that point.