CSSE 230
2D Tree Programming Assignment

Instructions

The purpose of this exercise is to understand in detail the mechanics of insertion, search, and finding the nearest neighbor in 2D Trees.

This is an individual assignment, Two2Trees, in your individual repository. All the methods you are to write are in the TwoDTree class, but you may modify other classes if you like.

We discussed how to build 2D trees in class using the insert(point, label) algorithm. Start by implementing this. 

Commit your code now and regularly as you work, at least after finishing each method. 

Next, write a contains() method to see if a point is stored in a 2D tree.

Finally, write nearestNeighbor(). 

Each of these three algorithms must operate in O(log n) time on a collection of n points. This will be true if you follow the algorithms given in class.

Your final submission will be tested using the given unit tests, and probably some more. You should write as many additional unit tests as you need to show that your algorithms work. We may also test it using the given visualizer. We recommend doing the same, and if you find any case that breaks an algorithm, turning it into a unit test that you submit.

For more details, we'd recommend these sources:

1. The slides (details of nearest neighbor search)
2. The template code in your repo. 
3. The Wikipedia article. This shows how to build a balanced tree if you start with the whole collection. A nice idea, but we are adding points one at a time. Implementing rotations in 2D trees is beyond the scope of this assignment. You're welcome.

Hints:

1. The direction of each node is given in an enumeration called Direction. The root always splits the plane depending on its point's x-coordinate, so has direction of Direction.X. This is shown using a vertical line (see node A below) since splitting based on X splits the plane using a vertical line. The root's children split the plane depending on the y-coordinate, so will be of type Direction.Y (the horizontal lines on E and B below).
2. The given RectHV class stores rectangle bounds. You'll probably want each node to store the rectangle it is part of. For example, the root could have been a point from anywhere on the plane, so it store the rectangle from (0,0) - (1,1). Say the root is at (0.3, 0.6). Then any node inserted to its left needs to have an x-coordinate < 0.3. So when inserted, this left child will store the rectangle bounds (0,0) - (0.3, 1). If a right child is inserted, it will store the bounds (0.3, 0) - (1, 1). It requires some work to store the correct rectangle bounds. But if you do, then in the nearestNeighbor algorithm, when you want to check to see if a point could be closer before recursing to a node, you can just call the RectHV's distanceTo(Point2) method to do the calculation of the distance from the point to the rectangle.        
3. You can use and modify the visualizer if you like. (We won't run it when we test your code.) If you do,
   1. When you add a node, store it's depth in the given field. This will let the tree visualizer (on the left side of the screenshot below) to place the nodes correctly.
   2. Left-clicking inserts a point.
   3. Right-clicking adds a query point for the nearest neighbor algorithm. This point will be blue. If you want it to highlight the nearest point found in red, then set the nearestFound field in TwoDTree to be the closest point you found.