How To Draw Kd Tree Princeton Assignment 5

http://coursera.cs.princeton.edu/algs4/assignments/kdtree.html
http://coursera.cs.princeton.edu/algs4/checklists/kdtree.html
Write a information type to represent a set of points in the unit square (all points acceptx- andy-coordinates between 0 and 1) using a2d-tree to support efficientrange search (find all of the points contained in a query rectangle) andnearest neighbor search (find a closest point to a query betoken). 2d-trees accept numerous applications, ranging from classifying astronomical objects to computer animation to speeding upwardly neural networks to mining data to image retrieval.

Geometric primitives. To get started, use the following geometric primitives for points and axis-aligned rectangles in the plane.

Utilize the immutable information blazon Point2D (office of

algs4.jar

) for points in the plane. Here is the subset of its API that y'all may use:

            public class Point2D implements Comparable<Point2D> {                          public Point2D(double ten, double y)                        // construct the signal (x, y)                          public  double 10()                        // 10-coordinate                          public  double y()                        // y-coordinate                          public  double distanceTo(Point2D that)                        // Euclidean distance between ii points                          public  double distanceSquaredTo(Point2D that)                        // foursquare of Euclidean distance between two points                          public     int compareTo(Point2D that)                        // for employ in an ordered symbol table                          public boolean equals(Object that)                        // does this indicate equal that object?                          public    void draw()                        // depict to standard draw                          public  String toString()                        // string representation            }

Use the immutable information blazon RectHV (part of

algs4.jar

) for centrality-aligned rectangles. Here is the subset of its API that you may employ:

            public class RectHV {                          public    RectHV(double xmin, double ymin,                        // construct the rectangle [xmin, xmax] 10 [ymin, ymax]                          double xmax, double ymax)                        // throw a coffee.lang.IllegalArgumentException 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(Point2D p)                        // does this rectangle contain the point p (either within or on purlieus)?                          public boolean intersects(RectHV that)                        // does this rectangle intersect that rectangle (at one or more points)?                          public  double distanceTo(Point2D p)                        // Euclidean distance from bespeak p to closest point in rectangle                          public  double distanceSquaredTo(Point2D p)                        // square of Euclidean distance from indicate p to closest point in rectangle                          public boolean equals(Object that)                        // does this rectangle equal that object?                          public    void draw()                        // draw to standard depict                          public  Cord toString()                        // cord representation            }

Practise not modify these information types.
Brute-force implementation. Write a mutable data type

PointSET.java

that represents a set of points in the unit of measurement square. Implement the following API by using a red-black BST (using either

SET

from

algs4.jar

coffee.util.TreeSet

            public class PointSET {                          public         PointSET()                        // construct an empty fix of points                          public           boolean isEmpty()                        // is the fix empty?                          public               int size()                        // number of points in the set                          public              void insert(Point2D p)                        // add together the betoken to the set (if information technology is not already in the set)                          public           boolean contains(Point2D p)                        // does the set contain point p?                          public              void describe()                        // describe all points to standard draw                          public Iterable<Point2D> range(RectHV rect)                        // all points that are inside the rectangle                          public           Point2D nearest(Point2D p)                        // a nearest neighbor in the fix to point p; null if the fix is empty                          public static void chief(Cord[] args)                        // unit testing of the methods (optional)            }

Corner cases. Throw a

java.lang.NullPointerException

if any argument is null.Performance requirements. Your implementation should support

insert()

and

contains()

in fourth dimension proportional to the logarithm of the number of points in the set in the worst case; it should back up

nearest()

and

range()

in fourth dimension proportional to the number of points in the gear up.
second-tree implementation. Write a mutable information blazon

KdTree.java

that uses a 2d-tree to implement the same API (only supercede

PointSET

with

KdTree

). A2d-tree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using thex- andy-coordinates of the points as keys in strictly alternating sequence.

Search and insert. The algorithms for search and insert are similar to those for BSTs, but at the root we use thex-coordinate (if the betoken to exist inserted has a smallerx-coordinate than the bespeak at the root, go left; otherwise get right); then at the side by side level, we utilise they-coordinate (if the point to be inserted has a smallery-coordinate than the point in the node, go left; otherwise go right); then at the next level thex-coordinate, and and then along.

insert (0.vii, 0.2)
insert (0.five, 0.4)
insert (0.2, 0.3)
insert (0.4, 0.7)
insert (0.9, 0.half dozen)

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

The prime advantage of a 2d-tree over a BST is that it supports efficient implementation of range search and nearest neighbour 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 of measurement square; the left and right children of the root corresponds to the two rectangles split by thex-coordinate of the point at the root; so along.

Range search. To observe all points contained in a given query rectangle, start at the root and recursively search for points inboth subtrees using the followingpruning rule: if the query rectangle does non 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 independent in the query rectangle.
Nearest neighbor search. To find a closest point to a given query betoken, offset at the root and recursively search inboth subtrees using the post-obitpruning rule: if the closest bespeak discovered so far is closer than the distance between the query betoken and the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, a node is searched only if information technology might contain a point that is closer than the best one institute so far. The effectiveness of the pruning dominion depends on quickly finding a nearby bespeak. To do this, organize your recursive method and so that when there are two possible subtrees to become downwards, yous e'er choosethe subtree that is on the aforementioned side of the splitting line as the query point as the start subtree to explore—the closest point establish while exploring the first subtree may enable pruning of the 2nd subtree.

http://www.cs.princeton.edu/courses/archive/spr13/cos226/lectures/99GeometricSearch.pdf
1d range search
Range search: detect all keys between k1 and k2.
Range count: number of keys between k1 and k2.
Unordered list. Fast insert, slow range search.
Ordered array. Deadening insert, binary search for k1 and k2 to exercise range search.
N = number of keys
R = number of keys that lucifer
public int size(Key lo, Key hi)
{
if (contains(hi)) return rank(hi) - rank(lo) + 1;
else return rank(how-do-you-do) - rank(lo);
}

2-d orthogonal range search
Find/count points in a given h-v rectangle

2d orthogonal range search: grid implementation
Grid implementation.
ɾDivide space into M-by-M grid of squares.
ɾCreate list of points contained in each square.
ɾUse 2nd array to straight index relevant square.
ɾInsert: add together (x, y) to list for corresponding square.
ɾRange search: examine only squares that intersect 2d range query.

Space-time tradeoff.
ɾSpace: K 2 + N.
ɾTime: ane + N / Thou 2 per square examined, on average.
Choose grid foursquare size to melody performance.
ɾToo small: wastes space.
ɾToo large: too many points per square.
ɾRule of thumb: √Northward-past-√Due north grid.
Running fourth dimension. [if points are evenly distributed]
ɾInitialize data structure: N.
ɾInsert point: ane.
ɾRange search: i per point in range

Grid implementation. Fast, elementary solution for evenly-distributed points.
Problem. Clustering a well-known phenomenon in geometric data.
ɾLists are besides long, even though average length is short.
ɾNeed data construction that adapts gracefully to information.

2d tree. Recursively divide space into 2 halfplanes.
Quadtree. Recursively divide infinite into 4 quadrants.
BSP tree. Recursively divide space into ii regions.

2d tree implementation
Data structure. BST, only alternate using x- and y-coordinates as cardinal.
ɾSearch gives rectangle containing bespeak.
ɾInsert further subdivides the airplane.

Range search in a 2d tree demo
Find all points in a query centrality-aligned rectangle.
ɾCheck if indicate in node lies in given rectangle.
ɾRecursively search left/bottom (if any could fall in rectangle).
ɾRecursively search right/acme (if any could fall in rectangle)

https://segmentfault.com/a/1190000005345079
课程开始先讲解了2-three search trees，一种引入了新规则树型结构。这是一个"理解容易，实现复杂"的Symbol table方案，它可以对任何输入数据保证树形结构的平衡以达到保证各项操作logN的复杂度，而规则却足够简单到可以在课堂中很快描述清楚，可以算是课程中第一个令我惊艳的算法。
紧接着下一节就是我们的主角：左倾红黑二叉树(LLRB)。
它只做到了一件事：将2-3 tree带回了二叉树世界，却仅对朴素的二叉树做极其微小的改动——每个节点增加1 fleck，用以表示"颜色"，加之无比简洁的引导，便在现实世界中实现了原先只是构想的2-three tree几乎全部的优点。
红黑树本身就是70年代Sedgewick教授参与提出的，而LLRB是由他一手提出的极其简洁的红黑树实现版本，尤其是它的insertion，在课堂上作为重点讲解，仅在原朴素二叉树实现代码基础上，增加了3个小工具函数（左旋、右旋、翻转）和递归插入过程中的4行代码（如图），便完成了所有工作。

这次的作业同样包含了一个暴力算法的版本（使用默认的红黑树结构），除了在执行效率上可以做比较外，还提供了一个重要的软件工程思路：面临一个较为复杂，而优化空间很大的问题时，先实现一个最简单的暴力算法版本检测结果（往往可以非常简便地实现），再考虑进阶的算法与数据结构实现性能优化，并在实现期间，暴力算法可以作为检验算法正确性最直接的参考。
实现过程中值得提到的点：

节点的奇偶性是一个不小的麻烦，编写需要十分谨慎，我的做法是在Node类中添加了一个boolean用以表示奇偶，相信一定有更好的方法（不存储RectHV），还会回来探索；
Nearest Neighbor的查找过程需要思考清楚，剪枝的界限十分清晰，尤其是剪裁其中一个子树的条件：如果本子树中找到的最近点与给定点距离已小于给定点到另一子树矩形区域的距离（点到点距离比点到矩形距离还近时），才能跳过另一子树的遍历过程。

https://github.com/Revil/algs-kdtree
public grade KdTree {

private static class Node {
private Point2D p;
private RectHV rect;
individual Node left;
private Node right;

public Node(Point2D p, RectHV rect) {
RectHV r = rect;
if (r == null)
r = new RectHV(0, 0, 1, one);
this.rect = r;
this.p = p;
}
}

private Node root;
individual int size;

// construct an empty ready of points
public KdTree() {
root = nil;
size = 0;
}

// is the fix empty?
public boolean isEmpty() { return root == aught; }

// number of points in the set
public int size() { render size; }

// larger or equal keys become correct
private Node insertH(Node x, Point2D p, RectHV rect) {
if (ten == null) {
size++;
return new Node(p, rect);
}
if (x.p.equals(p)) return x;

RectHV r;
int cmp = Point2D.Y_ORDER.compare(10.p, p);
if (cmp > 0) {
if (ten.left == null)
r = new RectHV(rect.xmin(), rect.ymin(), rect.xmax(), ten.p.y());
else
r = x.left.rect;
ten.left = insertV(ten.left, p, r);
} else {
if (x.correct == null)
r = new RectHV(rect.xmin(), ten.p.y(), rect.xmax(), rect.ymax());
else
r = x.correct.rect;
ten.correct = insertV(x.correct, p, r);
}

render 10;
}

// larger or equal keys go correct
private Node insertV(Node 10, Point2D p, RectHV rect) {
if (10 == null) {
size++;
render new Node(p, rect);
}
if (x.p.equals(p)) render x;

RectHV r;
int cmp = Point2D.X_ORDER.compare(x.p, p);
if (cmp > 0) {
if (10.left == cipher)
r = new RectHV(rect.xmin(), rect.ymin(), x.p.x(), rect.ymax());
else
r = x.left.rect;
x.left = insertH(x.left, p, r);
} else {
if (x.right == null)
r = new RectHV(10.p.x(), rect.ymin(), rect.xmax(), rect.ymax());
else
r = ten.right.rect;
x.right = insertH(x.right, p, r);
}

return x;
}

// add the point p to the set (if information technology is not already in the gear up)
public void insert(Point2D p) {
if (isEmpty())
root = insertV(root, p, zero);
else
root = insertV(root, p, root.rect);
}

// larger or equal keys become right
private boolean contains(Node x, Point2D p, boolean vert) {
if (ten == null) return false;
if (ten.p.equals(p)) return true;
int cmp;
if (vert) cmp = Point2D.X_ORDER.compare(x.p, p);
else cmp = Point2D.Y_ORDER.compare(x.p, p);
if (cmp > 0) return contains(10.left, p, !vert);
else render contains(10.correct, p, !vert);
}

// does the gear up comprise the betoken p?
public boolean contains(Point2D p) {
return contains(root, p, true);
}

private void draw(Node 10, boolean vert) {
if (x.left != null) draw(10.left, !vert);
if (x.right != null) draw(x.correct, !vert);

// draw the point showtime
StdDraw.setPenColor(StdDraw.Black);
StdDraw.setPenRadius(.01);
StdDraw.signal(ten.p.x(), ten.p.y());

// draw the line
double xmin, ymin, xmax, ymax;
if (vert) {
StdDraw.setPenColor(StdDraw.RED);
xmin = x.p.x();
xmax = 10.p.x();
ymin = x.rect.ymin();
ymax = ten.rect.ymax();
} else {
StdDraw.setPenColor(StdDraw.BLUE);
ymin = 10.p.y();
ymax = ten.p.y();
xmin = x.rect.xmin();
xmax = x.rect.xmax();
}
StdDraw.setPenRadius();
StdDraw.line(xmin, ymin, xmax, ymax);
}

// depict all of the points to standard draw
public void depict() {
// describe the rectangle
StdDraw.rectangle(0.five, 0.5, 0.v, 0.5);
if (isEmpty()) return;
draw(root, true);
}

private void range(Node x, RectHV rect, Queue<Point2D> q) {
if (x == null)
return;
if (rect.contains(x.p))
q.enqueue(10.p);
if (x.left != null && rect.intersects(ten.left.rect))
range(x.left, rect, q);
if (x.right != null && rect.intersects(ten.right.rect))
range(ten.right, rect, q);
}

// all points in the set that are within the rectangle
public Iterable<Point2D> range(RectHV rect) {
Queue<Point2D> q = new Queue<Point2D>();
range(root, rect, q);
return q;
}

private Point2D nearest(Node x, Point2D p, Point2D mp, boolean vert) {
Point2D min = mp;

if (10 == cipher) return min;
if (p.distanceSquaredTo(10.p) < p.distanceSquaredTo(min))
min = ten.p;

// cull the side that contains the query point first
if (vert) {
if (x.p.x() < p.x()) {
min = nearest(x.right, p, min, !vert);
if (x.left != null
&& (min.distanceSquaredTo(p)
> x.left.rect.distanceSquaredTo(p)))
min = nearest(x.left, p, min, !vert);
} else {
min = nearest(x.left, p, min, !vert);
if (x.right != naught
&& (min.distanceSquaredTo(p)
> ten.right.rect.distanceSquaredTo(p)))
min = nearest(x.right, p, min, !vert);
}
} else {
if (10.p.y() < p.y()) {
min = nearest(10.right, p, min, !vert);
if (x.left != goose egg
&& (min.distanceSquaredTo(p)
> x.left.rect.distanceSquaredTo(p)))
min = nearest(10.left, p, min, !vert);
} else {
min = nearest(x.left, p, min, !vert);
if (x.right != nothing
&& (min.distanceSquaredTo(p)
> 10.right.rect.distanceSquaredTo(p)))
min = nearest(10.right, p, min, !vert);
}
}
return min;
}

// a nearest neighbor in the set to p: goose egg if set is empty
public Point2D nearest(Point2D p) {
if (isEmpty()) return aught;
return nearest(root, p, root.p, true);
}
}

Animal Forcefulness:
public class PointSET {

individual SET<Point2D> prepare;

// construct an empty set of points
public PointSET() { set = new SET<Point2D>(); }

// is the set empty?
public boolean isEmpty() { return set.isEmpty(); }

// number of points in the set up
public int size() { return prepare.size(); }

// add the signal p to the set (if it is not already in the set)
// proportional to logarithm of N in the worst example
public void insert(Point2D p) { fix.add(p); }

// does the set contain the point p?
// proportional to logarithm of Northward in the worst example
public boolean contains(Point2D p) { return prepare.contains(p); }

// describe all of the points to standard draw
public void draw() {
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);

for (Point2D p : set)
StdDraw.bespeak(p.x(), p.y());

StdDraw.show(0);
}

// all points in the set up that are inside the rectangle
// proportional to N in the worst instance
public Iterable<Point2D> range(RectHV rect) {
Stack<Point2D> s = new Stack<Point2D>();

for (Point2D p : ready)
if (rect.contains(p))
s.push(p);

return south;
}

// a nearest neighbor in the set to p: null if set is empty
// proportional to Northward
public Point2D nearest(Point2D p) {
if (isEmpty()) render cipher;

double dis, minDis = Double.MAX_VALUE;
Point2D q = null;

for (Point2D ip : prepare) {
dis = p.distanceSquaredTo(ip);
if (dis < minDis) {
minDis = dis;
q = ip;
}
}

return q;
}
}
https://github.com/Revil/algs-kdtree/hulk/master/RectHV.java
public double distanceTo(Point2D p) {
return Math.sqrt(this.distanceSquaredTo(p));
}

// distance squared from p to closest point on this axis-aligned rectangle
public double distanceSquaredTo(Point2D p) {
double dx = 0.0, dy = 0.0;
if (p.10() < xmin) dx = p.x() - xmin;
else if (p.10() > xmax) dx = p.ten() - xmax;
if (p.y() < ymin) dy = p.y() - ymin;
else if (p.y() > ymax) dy = p.y() - ymax;
render dx*dx + dy*dy;
}

// does this axis-aligned rectangle contain p?
public boolean contains(Point2D p) {
return (p.x() >= xmin) && (p.x() <= xmax)
&& (p.y() >= ymin) && (p.y() <= ymax);
}

https://github.com/iman89/princeton/hulk/master/KDTrees/src/KdTree.java