COS 226 Programming Assignment Checklist: K-d Trees

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 main() test client, but do not add other public methods.

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 null.

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.

Kevin Wayne