From d1bc81087c8f6fab5836f73a2f0ce7ad2d92e48e Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Tue, 3 Jan 2017 16:02:50 -0500 Subject: [PATCH] nice implementations and bad implem the binary search tree is probably ready for general purpose use. the rectangle intersector "good answer" is totally hosed still; need to mentally process the algorithm. also need a better description of how to search the BST appropriately for y values. postponing for now. --- .../algorithms/BinarySearchTree.java | 170 +++++++++++++++ .../algorithms/RectangleIntersector.java | 205 ++++++++++++++++++ 2 files changed, 375 insertions(+) create mode 100644 kona/src/org/feistymeow/algorithms/BinarySearchTree.java create mode 100644 kona/src/org/feistymeow/algorithms/RectangleIntersector.java diff --git a/kona/src/org/feistymeow/algorithms/BinarySearchTree.java b/kona/src/org/feistymeow/algorithms/BinarySearchTree.java new file mode 100644 index 00000000..07cb3e6b --- /dev/null +++ b/kona/src/org/feistymeow/algorithms/BinarySearchTree.java @@ -0,0 +1,170 @@ +package org.feistymeow.algorithms; + + +//hmmm: move to better folder path. + +// inspired by http://pages.cs.wisc.edu/~cs367-1/readings/Binary-Search-Trees/ + +/** + * The type of node held in our binary search tree. + */ +class TreeNode +{ + private K key; + private V value; + private TreeNode left, right; + + public TreeNode(K key, V value, TreeNode left, TreeNode right) { + this.key = key; + this.value = value; + this.left = left; + this.right = right; + } + + public K getKey() { return key; } + public V getValue() { return value; } + + + public TreeNode getLeft() { return left; } + public TreeNode getRight() { return right; } + + public void setKey(K newK) { key = newK; } + public void setLeft(TreeNode newL) { left = newL; } + public void setRight(TreeNode newR) { right = newR; } + + public void setValue(V newV) { value = newV; } +} + +class DuplicateException extends RuntimeException +{ + private static final long serialVersionUID = 1L; + DuplicateException() {} +} + +/** + * A binary search tree implementation. + * + * Insert, Delete and Search are done in O(n log(n)) time. + */ +public class BinarySearchTree, V> +{ + private TreeNode root; // ptr to the root of the BinarySearchTree + + public BinarySearchTree() { root = null; } + + + // add key and associated value to this BinarySearchTree; + // error if key is already there + public void insert(K key, V value) throws DuplicateException { + root = insert(root, value, key); + } + + private TreeNode insert(TreeNode n, V value, K key) throws DuplicateException { + if (n == null) { + return new TreeNode(key, value, null, null); + } + + if (n.getKey().equals(key)) { + throw new DuplicateException(); + } + + if (key.compareTo(n.getKey()) < 0) { + // add key to the left subtree + n.setLeft( insert(n.getLeft(), value, key) ); + return n; + } + + else { + // add key to the right subtree + n.setRight( insert(n.getRight(), value, key) ); + return n; + } + } + + // remove the node containing key from this BinarySearchTree if it is there; + // otherwise, do nothing + public void delete(K key) { + root = delete(root, key); + } + + + private K smallest(TreeNode n) + // precondition: n is not null + // postcondition: return the smallest value in the subtree rooted at n + + { + if (n.getLeft() == null) { + return n.getKey(); + } else { + return smallest(n.getLeft()); + } + } + + private TreeNode delete(TreeNode n, K key) + { + if (n == null) { + return null; + } + + if (key.equals(n.getKey())) { + + if (n.getLeft() == null && n.getRight() == null) { + return null; + } + if (n.getLeft() == null) { + return n.getRight(); + } + if (n.getRight() == null) { + return n.getLeft(); + } + + // if we get here, then n has 2 children + K smallVal = smallest(n.getRight()); + n.setKey(smallVal); + n.setRight( delete(n.getRight(), smallVal) ); + return n; + } + + else if (key.compareTo(n.getKey()) < 0) { + n.setLeft( delete(n.getLeft(), key) ); + return n; + } + + else { + n.setRight( delete(n.getRight(), key) ); + return n; + } + } + + + // if key is in this BinarySearchTree, return its associated value; otherwise, return null + public boolean lookup(K key) { + return lookup(root, key); + } + + private boolean lookup(TreeNode n, K key) { + if (n == null) { + return false; + } + + if (n.getKey().equals(key)) { + return true; + } + + if (key.compareTo(n.getKey()) < 0) { + // key < this node's key; look in left subtree + return lookup(n.getLeft(), key); + } + + else { + // key > this node's key; look in right subtree + return lookup(n.getRight(), key); + } + } + +// // print the values in this BinarySearchTree in sorted order (to p) +// public void print(PrintStream p) { +// +// } +} + diff --git a/kona/src/org/feistymeow/algorithms/RectangleIntersector.java b/kona/src/org/feistymeow/algorithms/RectangleIntersector.java new file mode 100644 index 00000000..e177621f --- /dev/null +++ b/kona/src/org/feistymeow/algorithms/RectangleIntersector.java @@ -0,0 +1,205 @@ +package org.feistymeow.algorithms; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; +import java.util.Vector; + +import org.feistymeow.algorithms.RectangleIntersector.SortedElement; +import org.feistymeow.algorithms.RectangleIntersector.SortedElementComparator; + +/** + * reports if any two rectangles in a list intersect. uses screen coordinates. + */ +public class RectangleIntersector +{ + public RectangleIntersector() + { + + } + + public static class Point + { + Point(double x, double y) + { + this.x = x; + this.y = y; + } + + double x, y; + } + + public static class Rectangle + { + Rectangle(Point ul, Point lr) + { + this.ul = ul; + this.lr = lr; + } + + Point ul, lr; + } + + public static boolean doesPointOverlap(Point p, Rectangle r) + { + return p.x <= r.lr.x && p.x >= r.ul.x && p.y <= r.lr.y && p.y >= r.ul.y; + } + + public static boolean doRectanglesOverlap(Rectangle r1, Rectangle r2) + { + return doesPointOverlap(r1.ul, r2) || doesPointOverlap(r1.lr, r2) || doesPointOverlap(r2.ul, r1) || doesPointOverlap(r2.lr, r1); + } + + /** + * find any overlapping pair of rectangles in the list provided. + */ + public static Vector findOverlapBruteForce(Vector list) + { + // terrible brute force algorithm below. + for (int i = 0; i < list.size(); i++) { + for (int j = i; j < list.size(); j++) { + if (doRectanglesOverlap(list.get(i), list.get(j))) { + ArrayList toReturn = new ArrayList(); + toReturn.add(list.get(i)); + toReturn.add(list.get(j)); + } + } + } + return null; + } + + public static class SortedElement + { + double value; // the key. + boolean lowerEdge; // is this the left side? + Rectangle source; // where did this value come from. + + public SortedElement(double value, boolean lowerEdge, Rectangle source) + { + this.value = value; + this.lowerEdge = lowerEdge; + this.source = source; + } + } + + public static class SortedElementComparator implements Comparator + { + @Override + public int compare(SortedElement k1, SortedElement k2) + { + SortedElementKey key1 = new SortedElementKey(k1.value); + return key1.compareTo(new SortedElementKey(k2.value)); + } + + Double value; + } + + public static class SortedElementKey implements Comparable + { + public SortedElementKey(double key) + { + this.key = key; + } + + @Override + public int compareTo(SortedElementKey k2) + { + return (key == k2.key) ? 0 : (key < k2.key) ? -1 : 1; + } + + double key; + } + + /** + * find any overlapping pair of rectangles in the list provided. + * + * this is classed as a good answer... if it works. + */ + public static Vector findOverlap(Vector list) + { + // first phase, produce a sorted list of the x coordinates of the rectangles. + // this completes in O(n log(n)) time. + ArrayList xEdges = new ArrayList(); + for (Rectangle r : list) { + xEdges.add(new SortedElement(r.lr.x, true, r)); + xEdges.add(new SortedElement(r.ul.x, false, r)); + } + // we're assuming this is an efficient sort; i've heard rumors that it's a heapsort. + // if so we're good. if not, we'd write our own heapsort (see feisty meow nucleus sorts.h). + xEdges.sort(new SortedElementComparator()); + + // second phase, crawl across the sorted list and build up a binary search tree + // with the y coordinates from the rectangles. we will use this to check for + // intersections. + BinarySearchTree bst = new BinarySearchTree(); + + for (SortedElement scanner : xEdges) { + Rectangle source = scanner.source; + if (scanner.lowerEdge) { + // for x, this is the left edge. + // search for compatible top and bottom. + +//that means what? a value that is less than or equal the top and gte the bottom? +//we can traverse the tree manually, looking for any in the range we want, but that means + //digging in and changing the bst to allow us to single step downwards, or some such. + + //hmmm: POSTPONE. i want to do more things on the board, and this problem's gone WAY overtime. +//hmmm: need to fix this implementation; it is bustard. + + + // we want to add the two y components of the rectangle to our tree. + bst.insert(new SortedElementKey(source.lr.y), new SortedElement(source.lr.y, true, source)); + bst.insert(new SortedElementKey(source.ul.y), new SortedElement(source.ul.y, false, source)); + } else { + // for x, this is the right edge. + // we will remove from the bst the two values for our top and bottom y. + bst.delete(new SortedElementKey(source.lr.y)); + bst.delete(new SortedElementKey(source.ul.y)); + + + } + +//what is missing? + + + } + + + return null; + } + + public static void main(String[] argv) + { + Rectangle r1 = new Rectangle(new Point(0, 0), new Point(1, 1)); + Rectangle r2 = new Rectangle(new Point(3, 2), new Point(4, 3)); + Rectangle r3 = new Rectangle(new Point(2, 3), new Point(3, 4)); + Rectangle r4 = new Rectangle(new Point(5, 6), new Point(7, 9)); + + Vector list1 = new Vector(Arrays.asList(r1, r2, r3)); + Vector list2 = new Vector(Arrays.asList(r1, r2)); + Vector list3 = new Vector(Arrays.asList(r1, r3, r4)); + + RectangleIntersector secto = new RectangleIntersector(); + + Vector answer1 = secto.findOverlap(list1); + Vector answer2 = secto.findOverlap(list2); + Vector answer3 = secto.findOverlap(list3); + + if (answer1 == null) { + System.out.println("FAILURE: test 1 did not find intersection in list"); + } else { + System.out.println("OKAY: test 1 found intersections " + answer1.get(0) + " " + answer1.get(1)); + } + if (answer2 != null) { + System.out.println("FAILURE: test 2 found an intersection in list that has none"); + } else { + System.out.println("OKAY: test 2 no intersections found"); + } + if (answer3 != null) { + System.out.println("FAILURE: test 3 found an intersection in list that has none"); + } else { + System.out.println("OKAY: test 3 no intersections found"); + } + } + +} -- 2.34.1