import java.awt.geom.Point2D; import java.awt.geom.Rectangle2D; import java.util
ID: 3784200 • Letter: I
Question
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;
public class SplitTree {
private final SplitTreeNode root;
public SplitTree(List points) {
root = buildSplitTree(points, true);
}
// TODO: Finish the implementation of this method. Feel free to modify its arguments.
private SplitTreeNode buildSplitTree(List points, boolean splitX) {
if (points == null || points.isEmpty()) {
return null;
}
// TODO: Find the median point
Point2D p = null;
// TODO: Split the point set the right way
List first = null;
List second = null;
SplitTreeNode node = new SplitTreeNode(p);
node.child1 = buildSplitTree(first, !splitX);
node.child2 = buildSplitTree(second, !splitX);
return node;
}
public int countPointsInRectangle(Rectangle2D rect) {
return countPointsInRectangle(rect, root, true);
}
// TODO: implement
private int countPointsInRectangle(Rectangle2D rect, SplitTreeNode subtree, boolean splitX) {
return 0;
}
private class SplitTreeNode {
Point2D point;
SplitTreeNode child1, child2;
private SplitTreeNode(Point2D point) {
this.point = point;
}
}
public static void main(String[] args) {
// This performs a small test
List points = new ArrayList<>();
points.add(new Point2D.Double(192, 656));
points.add(new Point2D.Double(224, 720));
points.add(new Point2D.Double(320, 688));
SplitTree tree = new SplitTree(points);
System.out.print("Testing basic correctness: ");
if (tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 1000)) != 3
|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 300, 1000)) != 2
|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 200, 1000)) != 1
|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 700)) != 2
|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 660)) != 1
|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 600)) != 0) {
System.out.println("SplitTree counts points incorrectly!");
} else {
System.out.println("Everything seems fine so far.");
}
System.out.println("Testing basic efficiency: this should take less than a second...");
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
points.add(new Point2D.Double(1000 * Math.random(), 1000 * Math.random()));
}
tree = new SplitTree(points);
for (int i = 0; i < 100000; i++) {
tree.countPointsInRectangle(new Rectangle2D.Double(1000 * Math.random(), 1000 * Math.random(), 50, 50));
}
System.out.println("Done. That took " + ((System.currentTimeMillis() - start) / 1000.0) + " seconds.");
}
}
Explanation / Answer
public class KdTree {
private static final RectHV UNIT_SQUARE = new RectHV(0.0, 0.0, 1.0, 1.0);
private Node root;
private int size;
private static class Node {
private Point2D p;
private Node left;
private Node right;
private boolean vertical = true;
public Node(Point2D p, Node left, Node right, boolean vertical) {
this.p = p;
this.left = left;
this.right = right;
this.vertical = vertical;
}
}
public KdTree() {
root = null;
size = 0;
}
public boolean isEmpty() {
return (size == 0);
}
public int size() {
return size;
}
public void insert(Point2D p) {
root = doInsert(root, p, true);
}
private Node doInsert(Node node, Point2D p, boolean vertical) {
if (node == null) {
size++;
return new Node(p, null, null, vertical);
}
if (p.equals(node.p)) {
return node;
}
if (isSmallerThanPointInNode(p, node)) {
node.left = doInsert(node.left, p, !node.vertical);
} else {
node.right = doInsert(node.right, p, !node.vertical);
}
return node;
}
private boolean isSmallerThanPointInNode(Point2D p, Node node) {
int cmp = node.vertical ? Point2D.X_ORDER.compare(p, node.p) : Point2D.Y_ORDER.compare(p, node.p);
return (cmp < 0);
}
public boolean contains(Point2D p) {
Node node = root;
while (node != null) {
if (p.equals(node.p)) {
return true;
}
node = isSmallerThanPointInNode(p, node) ? node.left : node.right;
}
return false;
}
public void draw() {
StdDraw.setScale(0.0, 1.0);
doDraw(root, UNIT_SQUARE);
}
private void doDraw(Node node, RectHV nodeRect) {
if (node == null) {
return;
}
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(0.01);
node.p.draw();
Point2D fromPoint, toPoint;
if (node.vertical) {
StdDraw.setPenColor(StdDraw.RED);
fromPoint = new Point2D(node.p.x(), nodeRect.ymin());
toPoint = new Point2D(node.p.x(), nodeRect.ymax());
} else {
StdDraw.setPenColor(StdDraw.BLUE);
fromPoint = new Point2D(nodeRect.xmin(), node.p.y());
toPoint = new Point2D(nodeRect.xmax(), node.p.y());
}
fromPoint.drawTo(toPoint);
doDraw(node.left, leftNodeRect(node, nodeRect));
doDraw(node.right, rightNodeRect(node, nodeRect));
}
private RectHV leftNodeRect(Node node, RectHV nodeRect) {
return node.vertical
? new RectHV(nodeRect.xmin(), nodeRect.ymin(), node.p.x(), nodeRect.ymax())
: new RectHV(nodeRect.xmin(), nodeRect.ymin(), nodeRect.xmax(), node.p.y());
}
private RectHV rightNodeRect(Node node, RectHV nodeRect) {
return node.vertical
? new RectHV(node.p.x(), nodeRect.ymin(), nodeRect.xmax(), nodeRect.ymax())
: new RectHV(nodeRect.xmin(), node.p.y(), nodeRect.xmax(), nodeRect.ymax());
}
public Iterable<Point2D> range(RectHV rect) {
Queue<Point2D> pointsInRect = new Queue<Point2D>();
doRange(root, UNIT_SQUARE, rect, pointsInRect);
return pointsInRect;
}
private void doRange(Node node, RectHV nodeRect, RectHV queryRect, Queue<Point2D> pointsInRect) {
if (node == null) {
return;
}
if (queryRect.intersects(nodeRect)) {
if (queryRect.contains(node.p)) {
pointsInRect.enqueue(node.p);
}
doRange(node.left, leftNodeRect(node, nodeRect), queryRect, pointsInRect);
doRange(node.right, rightNodeRect(node, nodeRect), queryRect, pointsInRect);
}
}
public Point2D nearest(Point2D p) {
return doNearest(root, UNIT_SQUARE, p, null);
}
private Point2D doNearest(Node node, RectHV nodeRect, Point2D queryPoint, Point2D nearestPoint) {
if (node == null) {
return nearestPoint;
}
Point2D nearestPointCandidate = nearestPoint;
double nearestDist = (nearestPointCandidate != null)
? queryPoint.distanceSquaredTo(nearestPointCandidate)
: Double.MAX_VALUE;
if (nearestDist > nodeRect.distanceSquaredTo(queryPoint)) {
double dist = queryPoint.distanceSquaredTo(node.p);
if (dist < nearestDist) {
nearestPointCandidate = node.p;
}
RectHV leftNodeRect = leftNodeRect(node, nodeRect);
RectHV rightNodeRect = rightNodeRect(node, nodeRect);
if (isSmallerThanPointInNode(queryPoint, node)) {
nearestPointCandidate = doNearest(node.left, leftNodeRect, queryPoint, nearestPointCandidate);
nearestPointCandidate = doNearest(node.right, rightNodeRect, queryPoint, nearestPointCandidate);
} else {
nearestPointCandidate = doNearest(node.right, rightNodeRect, queryPoint, nearestPointCandidate);
nearestPointCandidate = doNearest(node.left, leftNodeRect, queryPoint, nearestPointCandidate);
}
}
return nearestPointCandidate;
}
}
public class KdTree {
private static final RectHV UNIT_SQUARE = new RectHV(0.0, 0.0, 1.0, 1.0);
private Node root;
private int size;
private static class Node {
private Point2D p;
private Node left;
private Node right;
private boolean vertical = true;
public Node(Point2D p, Node left, Node right, boolean vertical) {
this.p = p;
this.left = left;
this.right = right;
this.vertical = vertical;
}
}
public KdTree() {
root = null;
size = 0;
}
public boolean isEmpty() {
return (size == 0);
}
public int size() {
return size;
}
public void insert(Point2D p) {
root = doInsert(root, p, true);
}
private Node doInsert(Node node, Point2D p, boolean vertical) {
if (node == null) {
size++;
return new Node(p, null, null, vertical);
}
if (p.equals(node.p)) {
return node;
}
if (isSmallerThanPointInNode(p, node)) {
node.left = doInsert(node.left, p, !node.vertical);
} else {
node.right = doInsert(node.right, p, !node.vertical);
}
return node;
}
private boolean isSmallerThanPointInNode(Point2D p, Node node) {
int cmp = node.vertical ? Point2D.X_ORDER.compare(p, node.p) : Point2D.Y_ORDER.compare(p, node.p);
return (cmp < 0);
}
public boolean contains(Point2D p) {
Node node = root;
while (node != null) {
if (p.equals(node.p)) {
return true;
}
node = isSmallerThanPointInNode(p, node) ? node.left : node.right;
}
return false;
}
public void draw() {
StdDraw.setScale(0.0, 1.0);
doDraw(root, UNIT_SQUARE);
}
private void doDraw(Node node, RectHV nodeRect) {
if (node == null) {
return;
}
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(0.01);
node.p.draw();
Point2D fromPoint, toPoint;
if (node.vertical) {
StdDraw.setPenColor(StdDraw.RED);
fromPoint = new Point2D(node.p.x(), nodeRect.ymin());
toPoint = new Point2D(node.p.x(), nodeRect.ymax());
} else {
StdDraw.setPenColor(StdDraw.BLUE);
fromPoint = new Point2D(nodeRect.xmin(), node.p.y());
toPoint = new Point2D(nodeRect.xmax(), node.p.y());
}
fromPoint.drawTo(toPoint);
doDraw(node.left, leftNodeRect(node, nodeRect));
doDraw(node.right, rightNodeRect(node, nodeRect));
}
private RectHV leftNodeRect(Node node, RectHV nodeRect) {
return node.vertical
? new RectHV(nodeRect.xmin(), nodeRect.ymin(), node.p.x(), nodeRect.ymax())
: new RectHV(nodeRect.xmin(), nodeRect.ymin(), nodeRect.xmax(), node.p.y());
}
private RectHV rightNodeRect(Node node, RectHV nodeRect) {
return node.vertical
? new RectHV(node.p.x(), nodeRect.ymin(), nodeRect.xmax(), nodeRect.ymax())
: new RectHV(nodeRect.xmin(), node.p.y(), nodeRect.xmax(), nodeRect.ymax());
}
public Iterable<Point2D> range(RectHV rect) {
Queue<Point2D> pointsInRect = new Queue<Point2D>();
doRange(root, UNIT_SQUARE, rect, pointsInRect);
return pointsInRect;
}
private void doRange(Node node, RectHV nodeRect, RectHV queryRect, Queue<Point2D> pointsInRect) {
if (node == null) {
return;
}
if (queryRect.intersects(nodeRect)) {
if (queryRect.contains(node.p)) {
pointsInRect.enqueue(node.p);
}
doRange(node.left, leftNodeRect(node, nodeRect), queryRect, pointsInRect);
doRange(node.right, rightNodeRect(node, nodeRect), queryRect, pointsInRect);
}
}
public Point2D nearest(Point2D p) {
return doNearest(root, UNIT_SQUARE, p, null);
}
private Point2D doNearest(Node node, RectHV nodeRect, Point2D queryPoint, Point2D nearestPoint) {
if (node == null) {
return nearestPoint;
}
Point2D nearestPointCandidate = nearestPoint;
double nearestDist = (nearestPointCandidate != null)
? queryPoint.distanceSquaredTo(nearestPointCandidate)
: Double.MAX_VALUE;
if (nearestDist > nodeRect.distanceSquaredTo(queryPoint)) {
double dist = queryPoint.distanceSquaredTo(node.p);
if (dist < nearestDist) {
nearestPointCandidate = node.p;
}
RectHV leftNodeRect = leftNodeRect(node, nodeRect);
RectHV rightNodeRect = rightNodeRect(node, nodeRect);
if (isSmallerThanPointInNode(queryPoint, node)) {
nearestPointCandidate = doNearest(node.left, leftNodeRect, queryPoint, nearestPointCandidate);
nearestPointCandidate = doNearest(node.right, rightNodeRect, queryPoint, nearestPointCandidate);
} else {
nearestPointCandidate = doNearest(node.right, rightNodeRect, queryPoint, nearestPointCandidate);
nearestPointCandidate = doNearest(node.left, leftNodeRect, queryPoint, nearestPointCandidate);
}
}
return nearestPointCandidate;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.