how to check a collection of rectangles for holes and intersctions?

Question

I am searching for a way to check a collection (Java TreeSet) of rectangles - implemented by a "comparable" Java class using google guavas Range for x and y range - for intersections and holes. i know that an option could be to use kd-trees, but I have no idea how to build such an kd-tree (for rectangles it should be 4d, shouldn't it?) and how to get the problem solved (intersection, holes).

the sorting prioritizes the x-axis over y-axis.

EDIT: (try to restate the problem): the use case is to create arbitrary tables (consisting of 2 or 3 blocks of rectangles "header","pre column","data"). i have to guarantee that there are no intersections and holes (i.e. provided by invalid html or other sources of table data) in each block (besides this the blocks must fit together). Currently (just got an idea) i try to save in a 2d-array which positions (x,y) are occupied. at the end all position must be occupied exactly once.

Answer 1

There are quite a few of approaches to solving this type of a problem, each with different pros and cons. Here are some of them:

Rectangle Pair Intersection + Area Sum

Look at every pair of rectangles - if the two rectangles intersect, there is an overlap. Add up the rectangle areas and check whether the sum matches the canvas area - if the areas don't match, there is a gap.

Painting

This is the approach you mentioned: create a 2D array that has the dimensions of your canvas. Then, iterate over rectangles and "paint" them into the array.

One optimization to this approach is coordinate compression. Let's say that you have rectangles [(10,20), (15,25)] and [(7,3), (15, 25)]. You can look at the distinct x-coordinates (7, 10, 15) and remap them to (0, 1, 2), and the distinct y-coordinates (3, 20, 25) and remap them to (0, 1, 2). Then, you are left with rectangles [(1, 1), (2, 2)] and [(0,0), (2,2)], so you only need a 3x3 array for the painting, instead of a 26x26 array.

Sweep Line Algorithm

Sweep a line from left to right, stopping at 'interesting' points, and keeping track of which areas are occupied.

2D Range Trees

A data structure that can efficiently perform queries over rectangle ranges.

Which One to Pick?

It depends on the number of rectangles you have, how they are distributed in the area, how fast your algorithm must be, how much complexity you are willing to take on, etc. The first two algorithms that I mentioned are much simpler than the latter two, so I'd recommend starting there.

More Info

If you want learn more about these algorithms, try searching for "rectangle union" online. The most efficient solution is the sweep line algorithm.

Here are a couple of references on the sweep line algorithm:

1. What is an Efficient algorithm to find Area of Overlapping Rectangles
2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
3. J. L. Bentley, Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University, 1977

Reference 3. is usually given as the original source of the line sweep algorithm for rectangle union, but I have to admit that I didn't actually find the paper online, perhaps because it is "Unpublished"...