Inverse Rectangle Intersection In JavaScript

February 2012

Given a parent rectangle and a collection of children rectangles on a 2D plane, how do you find a collection of non-overlapping rectangles that cover the inverse of the original set?

For instance, given the container rectangle along with the set [A, B] -> we want an output similar to [1, 2, 3, 4, 5].

+----------------------------------------------------------------+
         |                                                                |
         |                                                                |
         |       +------------------+        +--------------------+       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |        A         |        |        B           |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       +------------------+        +--------------------+       |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+


         +----------------------------------------------------------------+
         |                                                                |
         |                               1                                |
         +-------+------------------+--------+--------------------+-------+
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |   2   |                  |   3    |                    |       |
         |       |                  |        |                    |   4   |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         +-------+------------------+--------+--------------------+-------+
         |                                                                |
         |                                                                |
         |                              5                                 |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+

Solution

Enter the inverse-intersection JavaScript project. It is a kind of micro library. No dependancies, just the math required to solve this problem!

You can grab the JavaScript file from Github.