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