dle Process: Finding Overlapping Rectangles in a given set of Axis aligned rectagles
Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis. You can assume that each rectangle object has two variables in it: the x-y coordinates of the upper-left corner and the bottom-right corner.
We can use Sweep Line algorithm for this. Create a sorted array of the x-coordinates of the left and the right edges of all the rectangles. The x-coordinates should be annotated with the rectangles they belong and whether they are the left or the right edge of the rectangle. Now, scan the sorted list from left to right, adding each rectangle to a balanced BST when you encounter the left edge of a rectangle and removing the rectangle from the balanced BST when you encounter the right edge of the rectangle. The solution requires the usage of one dimensional range search tree. A range search tree is a tree which is capable of performing range search queries efficiently. The time complexity of a range search query in a range search tree is O(R + logN), where N is the number of nodes in the tree and R is the number of elements in the result set.
Now lets see the detailed algorithm of the original problem:
http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
Read full article from Idle Process: Finding Overlapping Rectangles in a given set of Axis aligned rectagles
Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis. You can assume that each rectangle object has two variables in it: the x-y coordinates of the upper-left corner and the bottom-right corner.
We can use Sweep Line algorithm for this. Create a sorted array of the x-coordinates of the left and the right edges of all the rectangles. The x-coordinates should be annotated with the rectangles they belong and whether they are the left or the right edge of the rectangle. Now, scan the sorted list from left to right, adding each rectangle to a balanced BST when you encounter the left edge of a rectangle and removing the rectangle from the balanced BST when you encounter the right edge of the rectangle. The solution requires the usage of one dimensional range search tree. A range search tree is a tree which is capable of performing range search queries efficiently. The time complexity of a range search query in a range search tree is O(R + logN), where N is the number of nodes in the tree and R is the number of elements in the result set.
Now lets see the detailed algorithm of the original problem:
1) Sort all left and right rectange edges, according to their X value, into list L.
2) Create a new empty range search tree T, for Y ordering of rectangle tops/bottoms
3) Create a new empty result set RS of unique rectangle pairs
4) Traverse L in ascending order. For all V in L:
If V.isRightEdge()
T.remove(V.rectangle.top)
T.remove(V.rectangle.bottom)
else
For all U in T.getRange(V.rectangle.top, V.rectangle.bottom)
RS.add(<V.rectangle, U.rectangle>)
T.add(V.rectangle.top)
T.add(V.rectangle.bottom)
5) return RS
Time complexity is O(R + N log N) where R is the actual number of intersections.
http://stackoverflow.com/questions/3324880/axis-aligned-rectangles-intersectionTime complexity is O(R + N log N) where R is the actual number of intersections.
http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
Read full article from Idle Process: Finding Overlapping Rectangles in a given set of Axis aligned rectagles
