Geometric primitives.
To get started, use the following geometric primitives for points and
axis-aligned rectangles in the plane.
Use the immutable data type Point2D.java (part of algs4.jar) for points in the plane. Here is the subset of its API that you may use:
public class Point2D implements Comparable<Point2D> {
public Point2D(double x, double y) // construct the point (x, y)
public double x() // x-coordinate
public double y() // y-coordinate
public double distanceSquaredTo(Point2D that) // square of Euclidean distance between two points
public int compareTo(Point2D that) // for use in an ordered symbol table
public boolean equals(Object that) // does this point equal that object?
public String toString() // string representation
}
Use the immutable data type RectHV.java
(not part of algs4.jar) for axis-aligned rectangles.
Here is the subset of its API that you may use:
public class RectHV {
public RectHV(double xmin, double ymin, // construct the rectangle [xmin, xmax] x [ymin, ymax]
double xmax, double ymax)
public double xmin() // minimum x-coordinate of rectangle
public double ymin() // minimum y-coordinate of rectangle
public double xmax() // maximum x-coordinate of rectangle
public double ymax() // maximum y-coordinate of rectangle
public boolean contains(Point2D p) // does this rectangle contain the point p (either inside or on boundary)?
public boolean intersects(RectHV that) // does this rectangle intersect that rectangle (at one or more points)?
public double distanceSquaredTo(Point2D p) // square of Euclidean distance from point p to closest point in rectangle
public boolean equals(Object that) // does this rectangle equal that object?
public String toString() // string representation
}
You may not modify these data types.
Brute-force implementation. Write a mutable data type PointST.java that is symbol table with Point2D. Implement the following API by using a red-black BST (using either RedBlackBST from algs4.jar or java.util.TreeMap); do not implement your own red-black BST.
public class PointST<Value> {
public PointST() // construct an empty symbol table of points
public boolean isEmpty() // is the symbol table empty?
public int size() // number of points
public void put(Point2D p, Value val) // associate the value val with point p
public Value get(Point2D p) // value associated with point p
public boolean contains(Point2D p) // does the symbol table contain point p?
public Iterable<Point2D> points() // all points in the symbol table
public Iterable<Point2D> range(RectHV rect) // all points that are inside the rectangle
public Point2D nearest(Point2D p) // a nearest neighbor to point p; null if the symbol table is empty
public static void main(String[] args) // unit testing of the methods (not graded)
}
Corner cases.
Throw a java.lang.NullPointerException if any argument is null.
Performance requirements.
Your implementation should support put(), get() and contains() in time
proportional to the logarithm of the number of points in the set in the worst case; it should support
points(), nearest(), and range() in time proportional to the number
of points in the symbol table.
2d-tree implementation. Write a mutable data type KdTreeST.java that uses a 2d-tree to implement the same API (but renaming PointST to KdTreeST). A 2d-tree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using the x- and y-coordinates of the points as keys in strictly alternating sequence, starting with the x-coordinates.
insert (0.7, 0.2) insert (0.5, 0.4) insert (0.2, 0.3) insert (0.4, 0.7) insert (0.9, 0.6)
The prime advantage of a 2d-tree over a BST is that it supports efficient implementation of range search and nearest neighbor search. Each node corresponds to an axis-aligned rectangle, which encloses all of the points in its subtree. The root corresponds to the infinitely large square from [(-∞, -∞), (+∞, +∞ )]; the left and right children of the root correspond to the two rectangles split by the x-coordinate of the point at the root; and so forth.
Clients. You may use the following two interactive client programs to test and debug your code.
Analysis of running time and memory usage. Analyze the effectiveness of your approach to this problem by giving estimates of its time and space requirements.
Challenge for the bored. Create a new data type EnhancedKdTreeST.java that contains one additional method:
This method should return the k points that are closest to the query point (in any order); return all N points in the data structure if N ≤ k. It should do this in an efficient manner, i.e. using the technique from kd-tree nearest neighbor search, not from brute force. Once you've completed this class, you'll be able to run BoidSimulator.java (which depends upon both Boid.java and Hawk.java). Behold their flocking majesty.public Iterable<Point2D> nearest(Point2D p, int k)
Submission. Submit only PointST.java and KdTreeST.java. Each of the two data types should include their own main() that thoroughly tests the associated operations. We will supply Point2D.java, RectHV.java, stdlib.jar, and algs4.jar. You may not call any library functions other than those in java.lang, java.util, stdlib.jar, and algs4.jar. Finally, submit a readme.txt file and answer the questions.
This assignment was developed by Kevin Wayne, with boid simulation by Josh Hug.
