Region Unions

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!

First attempt

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).

Second attempt

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:

regions.png

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.

Notes

  • 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.

Add a New Comment