adapted to new storage location
[feisty_meow.git] / 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 }