1 package org.feistymeow.algorithms;
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Comparator;
6 import java.util.Vector;
8 import org.feistymeow.algorithms.RectangleIntersector.SortedElement;
9 import org.feistymeow.algorithms.RectangleIntersector.SortedElementComparator;
12 * reports if any two rectangles in a list intersect. uses screen coordinates.
14 public class RectangleIntersector
16 public RectangleIntersector()
21 public static class Point
23 Point(double x, double y)
32 public static class Rectangle
34 Rectangle(Point ul, Point lr)
43 public static boolean doesPointOverlap(Point p, Rectangle r)
45 return p.x <= r.lr.x && p.x >= r.ul.x && p.y <= r.lr.y && p.y >= r.ul.y;
48 public static boolean doRectanglesOverlap(Rectangle r1, Rectangle r2)
50 return doesPointOverlap(r1.ul, r2) || doesPointOverlap(r1.lr, r2) || doesPointOverlap(r2.ul, r1) || doesPointOverlap(r2.lr, r1);
54 * find any overlapping pair of rectangles in the list provided.
56 public static Vector<Rectangle> findOverlapBruteForce(Vector<Rectangle> list)
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));
71 public static class SortedElement
73 double value; // the key.
74 boolean lowerEdge; // is this the left side?
75 Rectangle source; // where did this value come from.
77 public SortedElement(double value, boolean lowerEdge, Rectangle source)
80 this.lowerEdge = lowerEdge;
85 public static class SortedElementComparator implements Comparator<SortedElement>
88 public int compare(SortedElement k1, SortedElement k2)
90 SortedElementKey key1 = new SortedElementKey(k1.value);
91 return key1.compareTo(new SortedElementKey(k2.value));
97 public static class SortedElementKey implements Comparable<SortedElementKey>
99 public SortedElementKey(double key)
105 public int compareTo(SortedElementKey k2)
107 return (key == k2.key) ? 0 : (key < k2.key) ? -1 : 1;
114 * find any overlapping pair of rectangles in the list provided.
116 * this is classed as a good answer... if it works.
118 public static Vector<Rectangle> findOverlap(Vector<Rectangle> list)
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));
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());
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
134 BinarySearchTree<SortedElementKey, SortedElement> bst = new BinarySearchTree<SortedElementKey, SortedElement>();
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.
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.
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.
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));
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));
171 public static void main(String[] argv)
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));
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));
182 RectangleIntersector secto = new RectangleIntersector();
184 Vector<Rectangle> answer1 = secto.findOverlap(list1);
185 Vector<Rectangle> answer2 = secto.findOverlap(list2);
186 Vector<Rectangle> answer3 = secto.findOverlap(list3);
188 if (answer1 == null) {
189 System.out.println("FAILURE: test 1 did not find intersection in list");
191 System.out.println("OKAY: test 1 found intersections " + answer1.get(0) + " " + answer1.get(1));
193 if (answer2 != null) {
194 System.out.println("FAILURE: test 2 found an intersection in list that has none");
196 System.out.println("OKAY: test 2 no intersections found");
198 if (answer3 != null) {
199 System.out.println("FAILURE: test 3 found an intersection in list that has none");
201 System.out.println("OKAY: test 3 no intersections found");