kona/src/org/feistymeow/algorithms/RectangleIntersector.java

   1 package org.feistymeow.algorithms;
   2
   3 import java.util.ArrayList;
   4 import java.util.Arrays;
   5 import java.util.Comparator;
   6 import java.util.Vector;
   7
   8 import org.feistymeow.algorithms.RectangleIntersector.SortedElement;
   9 import org.feistymeow.algorithms.RectangleIntersector.SortedElementComparator;
  10
  11 /**
  12  * reports if any two rectangles in a list intersect. uses screen coordinates.
  13  */
  14 public class RectangleIntersector
  15 {
  16         public RectangleIntersector()
  17         {
  18
  19         }
  20
  21         public static class Point
  22         {
  23                 Point(double x, double y)
  24                 {
  25                         this.x = x;
  26                         this.y = y;
  27                 }
  28
  29                 double x, y;
  30         }
  31
  32         public static class Rectangle
  33         {
  34                 Rectangle(Point ul, Point lr)
  35                 {
  36                         this.ul = ul;
  37                         this.lr = lr;
  38                 }
  39
  40                 Point ul, lr;
  41         }
  42
  43         public static boolean doesPointOverlap(Point p, Rectangle r)
  44         {
  45                 return p.x <= r.lr.x && p.x >= r.ul.x && p.y <= r.lr.y && p.y >= r.ul.y;
  46         }
  47
  48         public static boolean doRectanglesOverlap(Rectangle r1, Rectangle r2)
  49         {
  50                 return doesPointOverlap(r1.ul, r2) || doesPointOverlap(r1.lr, r2) || doesPointOverlap(r2.ul, r1) || doesPointOverlap(r2.lr, r1);
  51         }
  52
  53         /**
  54          * find any overlapping pair of rectangles in the list provided.
  55          */
  56         public static Vector<Rectangle> findOverlapBruteForce(Vector<Rectangle> list)
  57         {
  58                 // terrible brute force algorithm below.
  59                 for (int i = 0; i < list.size(); i++) {
  60                         for (int j = i; j < list.size(); j++) {
  61                                 if (doRectanglesOverlap(list.get(i), list.get(j))) {
  62                                         ArrayList<Rectangle> toReturn = new ArrayList<Rectangle>();
  63                                         toReturn.add(list.get(i));
  64                                         toReturn.add(list.get(j));
  65                                 }
  66                         }
  67                 }
  68                 return null;
  69         }
  70
  71         public static class SortedElement
  72         {
  73                 double value; // the key.
  74                 boolean lowerEdge; // is this the left side?
  75                 Rectangle source; // where did this value come from.
  76
  77                 public SortedElement(double value, boolean lowerEdge, Rectangle source)
  78                 {
  79                         this.value = value;
  80                         this.lowerEdge = lowerEdge;
  81                         this.source = source;
  82                 }
  83         }
  84
  85         public static class SortedElementComparator implements Comparator<SortedElement>
  86         {
  87                 @Override
  88                 public int compare(SortedElement k1, SortedElement k2)
  89                 {
  90                         SortedElementKey key1 = new SortedElementKey(k1.value);
  91                         return key1.compareTo(new SortedElementKey(k2.value));
  92                 }
  93
  94                 Double value;
  95         }
  96
  97         public static class SortedElementKey implements Comparable<SortedElementKey>
  98         {
  99                 public SortedElementKey(double key)
 100                 {
 101                         this.key = key;
 102                 }
 103
 104                 @Override
 105                 public int compareTo(SortedElementKey k2)
 106                 {
 107                         return (key == k2.key) ? 0 : (key < k2.key) ? -1 : 1;
 108                 }
 109
 110                 double key;
 111         }
 112
 113         /**
 114          * find any overlapping pair of rectangles in the list provided.
 115          *
 116          * this is classed as a good answer... if it works.
 117          */
 118         public static Vector<Rectangle> findOverlap(Vector<Rectangle> list)
 119         {
 120                 // first phase, produce a sorted list of the x coordinates of the rectangles.
 121                 // this completes in O(n log(n)) time.
 122                 ArrayList<SortedElement> xEdges = new ArrayList<SortedElement>();
 123                 for (Rectangle r : list) {
 124                         xEdges.add(new SortedElement(r.lr.x, true, r));
 125                         xEdges.add(new SortedElement(r.ul.x, false, r));
 126                 }
 127                 // we're assuming this is an efficient sort; i've heard rumors that it's a heapsort.
 128                 // if so we're good. if not, we'd write our own heapsort (see feisty meow nucleus sorts.h).
 129                 xEdges.sort(new SortedElementComparator());
 130
 131                 // second phase, crawl across the sorted list and build up a binary search tree
 132                 // with the y coordinates from the rectangles. we will use this to check for
 133                 // intersections.
 134                 BinarySearchTree<SortedElementKey, SortedElement> bst = new BinarySearchTree<SortedElementKey, SortedElement>();
 135
 136                 for (SortedElement scanner : xEdges) {
 137                         Rectangle source = scanner.source;
 138                         if (scanner.lowerEdge) {
 139                                 // for x, this is the left edge.
 140                                 // search for compatible top and bottom.
 141
 142 //that means what?  a value that is less than or equal the top and gte the bottom?
 143 //we can traverse the tree manually, looking for any  in the range we want, but that means
 144                                 //digging in and changing the bst to allow us to single step downwards, or some such.
 145
 146                                 //hmmm: POSTPONE.  i want to do more things on the board, and this problem's gone WAY overtime.
 147 //hmmm: need to fix this implementation; it is bustard.
 148
 149
 150                                 // we want to add the two y components of the rectangle to our tree.
 151                                 bst.insert(new SortedElementKey(source.lr.y), new SortedElement(source.lr.y, true, source));
 152                                 bst.insert(new SortedElementKey(source.ul.y), new SortedElement(source.ul.y, false, source));
 153                         } else {
 154                                 // for x, this is the right edge.
 155                                 // we will remove from the bst the two values for our top and bottom y.
 156                                 bst.delete(new SortedElementKey(source.lr.y));
 157                                 bst.delete(new SortedElementKey(source.ul.y));
 158
 159
 160                         }
 161
 162 //what is missing?
 163
 164
 165                 }
 166
 167
 168                 return null;
 169         }
 170
 171         public static void main(String[] argv)
 172         {
 173                 Rectangle r1 = new Rectangle(new Point(0, 0), new Point(1, 1));
 174                 Rectangle r2 = new Rectangle(new Point(3, 2), new Point(4, 3));
 175                 Rectangle r3 = new Rectangle(new Point(2, 3), new Point(3, 4));
 176                 Rectangle r4 = new Rectangle(new Point(5, 6), new Point(7, 9));
 177
 178                 Vector<Rectangle> list1 = new Vector<Rectangle>(Arrays.asList(r1, r2, r3));
 179                 Vector<Rectangle> list2 = new Vector<Rectangle>(Arrays.asList(r1, r2));
 180                 Vector<Rectangle> list3 = new Vector<Rectangle>(Arrays.asList(r1, r3, r4));
 181
 182                 RectangleIntersector secto = new RectangleIntersector();
 183
 184                 Vector<Rectangle> answer1 = secto.findOverlap(list1);
 185                 Vector<Rectangle> answer2 = secto.findOverlap(list2);
 186                 Vector<Rectangle> answer3 = secto.findOverlap(list3);
 187
 188                 if (answer1 == null) {
 189                         System.out.println("FAILURE: test 1 did not find intersection in list");
 190                 } else {
 191                         System.out.println("OKAY: test 1 found intersections " + answer1.get(0) + " " + answer1.get(1));
 192                 }
 193                 if (answer2 != null) {
 194                         System.out.println("FAILURE: test 2 found an intersection in list that has none");
 195                 } else {
 196                         System.out.println("OKAY: test 2 no intersections found");
 197                 }
 198                 if (answer3 != null) {
 199                         System.out.println("FAILURE: test 3 found an intersection in list that has none");
 200                 } else {
 201                         System.out.println("OKAY: test 3 no intersections found");
 202                 }
 203         }
 204
 205 }