Write a data type using a

**Geometric primitives.**
To get started, implement two geometric primitives:
one for points in the plane and one for axis-aligned rectangles in the plane.

Write an immutable data type `Point.java` that implements the following API.

Write an immutable data typepublic class Point implements Comparable<Point> { public Point(double x, double y) // construct the point (x, y) public double x() // x-coordinate public double y() // y-coordinate public double distanceTo(Point that) // Euclidean distance between two points public double distance2To(Point that) // square of Euclidean distance between two points public int compareTo(Point that) // for use in a symbol table public boolean equals(Object that) // does this point equal that? public void draw() // draw to standard draw public String toString() // string representation }

Thoroughly test your data types before proceeding.public class RectHV { public RectHV(double xmin, double ymin, // construct the rectangle [xmin, ymin] x [xmax, ymax] double xmax, double ymax) // throw an exception if (xmin > xmax) or (ymin > 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(Point p) // does this rectangle contain p? public boolean intersects(RectHV that) // do the two rectangles intersect? public double distanceTo(Point p) // Euclidean distance from p to closest point in rectangle public double distance2To(Point p) // square of Euclidean distance from p to closest point in rectangle public boolean equals(Object that) // does this rectangle equal that? public void draw() // draw to standard draw public String toString() // string representation }

**Brute-force implementation.**
Write a data type `PointSET.java` that represents a set of
points in the unit square. Implement the following API by using a
red-black tree (using either `SET` or `TreeSet`).

Your implementation should supportpublic class PointSET { public PointSET() // construct an empty set of points public boolean isEmpty() // is the set empty? public int size() // number of points in the set public void insert(Point p) // add the point p to the set public boolean contains(Point p) // does the set contain p? public void draw() // draw all of the points to standard draw public Iterable<Point> range(RectHV rect) // points in the set that are in the rectangle public Point nearest(Point p) // nearest neighbor in the set to p (null if set is empty) }

**2d-tree implementation.**
Write a data type `KdTree.java` that implements the same API
as `PointSET`, but using a 2d-tree instead of a red-black tree.
A *2d-tree* is a generalization of a binary search tree to two-dimensional keys.
The idea is to build a binary search tree with points in the nodes,
using the *x*- and *y*-coordinates of the points
as keys in strictly alternating sequence.

*Search and insert.*The algorithms for search and insert are similar to those for binary search trees, but at the root we use the*x*-coordinate (if the point to be inserted has a smaller*x*-coordinate than the point at the root, go left; otherwise go right); then at the next level, we use the*y*-coordinate (if the point to be inserted has a smaller*y*-coordinate than the point in the node, go left; otherwise go right); then at the next level the*x*-coordinate and so forth.

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)

*Draw.*A 2d-tree divides the unit square in a simple way: all the points to the left of the root go in the left subtree; all those to the right go in the right subtree; and so forth, recursively. Your`draw()`method should draw all of the points to standard draw in black and the subdivisions in red (for vertical splits) and blue (for horizontal splits). This method need not be efficient—it is primarily for debugging.

The prime advantage of a 2d-tree over a binary search tree
is that it supports efficient
implementation of range search and nearest neighbor search.
Each node corresponds to an axis-aligned rectangle in the unit square,
which encloses all of the points in its subtree.
The root corresponds to the unit square; the left and right children
of the root corresponds to the two rectangles
split by the *x*-coordinate of the point at the root; and so forth.

*Range search.*To find all points contained in a given query rectangle, start at the root and recursively search for points in both subtrees using the following*pruning rule*: if the query rectangle does not intersect the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). A subtree is searched only if it might contain a point contained in the query rectangle.*Nearest neighbor search.*To find the closest point to a given query point, start at the root and recursively search in both subtrees using the following*pruning rule*: if the closest point discovered so far is closer than the distance between the query point and the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). A subtree is searched only if it might contain a point that is closer than the best one found so far. The effectiveness of the pruning strategy depends on quickly finding a nearby point. To do this,*organize your recursive method so that it begins by moving down the 2d-tree by considering the same sequence of nodes that would be considered if you were inserting the query point*.

**Clients.**
You may use the following interactive client programs to test and debug your code.

- KdTreeVisualizer.java computes and draws the 2d-tree that results from the sequence of points clicked by the user in the standard drawing window.
- RangeSearchVisualizer.java reads a sequence of points from standard input and inserts those points into a 2d-tree. Then, it performs range searches on the axis-aligned rectangles dragged by the user in the standard drawing window.
- NearestNeighborVisualizer.java reads a sequence of points from standard input and inserts those points into a 2d-tree. Then, it performs nearest neighbor queries on the point corresponding to the location of the mouse in the standard drawing window.

**Analysis.**
Analyze your approach to this problem giving estimates of
its time and space requirements by answering the relevant questions
in the readme.txt
file. In particular:

- Give the total memory usage in bytes (using tilde notation)
of your 2d-tree data structure as a function of the
number of points
*N*. Count all memory that is used by your 2d-tree, including memory for the nodes, points, and rectangles. - Give the expected running time in seconds (using tilde notation)
to build a 2d-tree on
*N*random points in the unit square. (Do not count the time to read in the points from standard input.) - How many nearest neighbor calculations can your 2d-tree implementation perform per second for input100K.txt (100,000 points) and input1M.txt (1 million points), where the query points are random points in the unit square? (Do not count the time to read in the points or to build the 2d-tree.) Repeat the question but with the brute-force implementation.

**Submission.**
Submit `Point.java`, `RectHV.java`, `PointSET.java`,
and `KDTree.java` and any other files needed by your program (excluding those
in `stdlib.jar` and `algs4.jar`).
Finally, submit a
readme.txt file and answer the questions.

This assignment was developed by Kevin Wayne.