Frequently Asked Questions |

**Is a point on the boundary of a rectangle considered inside it?
Do two rectangle intersect if they have just one point in common?**
Yes, and yes.

**
Can I add extra public methods to the Point and RectHV
APIs?**
You are permitted (and encouraged) to add a

**What should I do if a point is inserted twice in the data structure?**
The data structure represents a set of points, so you should only keep one copy.

**What should I do if a point has the same x-coordinate as the point
in a node when inserting / searching?**
Go the right subtree.

**
Can I assume that all x- or y-coordinate will be between 0 and 1?**
Yes.

**How should I scale the coordinate system when drawing?**
Don't, please keep the default range of 0 to 1.

**How should I set the size and color of the points and rectangles when drawing?**
Your `Point` and `RectHV` data types should draw points
and lines using `StdDraw.point()` and `StdDraw.line()` as usual.
They should not all `StdDraw.setPenColor()` or `StdDraw.setPenRadius()`.
In the *client code*, use `StdDraw.setPenColor()` before drawing
the points and rectangles. Also use `StdDraw.setPenRadius(.01)` before
drawing the points and `StdDraw.setPenRadius()` before drawing the lines.

**With the distance methods in RectHV there are 9 different
possible calculations. Is this the correct approach?**
This is perfectly acceptable. Alternatively, there is another approach
which requires only 5-6 lines of code.

**What should nearest() return if the set of points in
the data structure is empty?**
Return

Testing and Submitting |

**Testing.**
We highly recommend testing each method in each data type.
Catching mistakes in `Point` and `RectHV` early
will save you significant time when debugging later.
A good way to test your `KdTree` data type is to perform
the same sequence of operations on both the `PointSET` and
`KdTree` data types and identify any discrepancies.

**Sample input files.**
We provide some input files for testing

`circleN.txt`contains`N`points on the circumference of the circle centered on (0.5, 0.5) of radius 0.5.

Possible Progress Steps |

These are purely suggestions for how you might make progress. You do not have to follow these steps.

**Getting started.**Download the directory kdtree to your system. It contains some sample input files and test clients that you will use.**Node data type.**There are several reasonable ways to represent a node in a 2d-tree. One approach is to include the point, a link to the left/bottom subtree, a link to the right/top subtree, and an axis-aligned rectangle corresponding to the node.private class Node { private Point p; // the point private RectHV rect; // the axis-aligned rectangle corresponding to this node private Node lb; // the left/bottom subtree private Node rt; // the right/top subtree }

Optimizations |

These are some ways to speed up your 2d-tree.

**Range search.**Instead of checking whether the query rectangle intersects the rectangle in a node, it suffices to check only whether the query rectangle intersects the splitting line segment: if it does, then recursively search both subtrees; otherwise, recursively search the one subtree where points intersecting the query rectangle could be.