Detect Overlapping Rectangles in Javascript

Closed - This job posting has been filled.

Job Description

I would like a Javascript function that efficiently detects which of the rectangles in a given data structure overlap one another.

The input will look like this:
var boxes = [
{x: 0, y: 0, w: 4, h: 4, i: 0}
,{x: 5, y: 50, w: 30, h: 20, i: 1}
,{x: 5, y: 8, w: 20, h: 15, i: 2}
,{x: 50, y: 20, w: 30, h: 20, i: 3}
];

each object in the array represents a rectangle in 2d space -- (x,y) is its upper-left coordinate, and w and h are its width and height. i is an index.

The function should determine which of these boxes overlap with one another. This is straightforward, there are a number of stack overflow posts about it, e.g. http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other.

For improved efficiency, the function should not compare all rectangles with one another, but rather use a "plane-sweep" approach to more efficiently find those that intersect.

The output should be a two-dimensional array indicating which rectangles intersect, e.g. the following for the example above:

[[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]]