While solving one of those online programming puzzles1 I needed to compute all points in a collection of rectangles. Note that these rectangles can overlap!
One quick way to solve this is to maintain a Set (as opposed to a List) of points belonging to each rectangle. This would have been nice, since I anyway needed to iterate over these set of points.
However, for large rectangles, the set quickly becomes huge and unmanageable (number of points is proportional to square of rectangle width).
To reduce the memory requirement, I thought of maintaining a set of non overlapping rectangles (instead of individual points). perhaps a diagram will make it clear:
The rectangles on the left are the input. Note how they overlap.
The rectangles on the right are the output.
The algorithm in pseudo-pseudo-code is:
- Add the input rectangles one by one to the result list
- While adding, clip the new rectangle (A) by each rectangle in the result list (B)
- Clipping is done by
- Chopping A with each line segment of B
- The resulting list of chopped rectangles is then filtered such that they don't lie within B
The Scala code for this is attached to this page Region.scala. Feel free to use it as you like.
- The co-ordinates are integer based, but can be easily extended to reals
- I haven't optimised for the number of resulting rectangles. For example, it might be possible to coalesce adjoining rectangles into a single one. (The number of resulting rectangles didn't matter for my problem)
- The result is not unique. Multiple correct solutions are possible and the chosen one depends on the order in which rectangles are added.
- If you ever happen to use this piece of code, please drop me a note/comment.