5

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.

dermoritz
  • 12,519
  • 25
  • 97
  • 185
  • I recommend you restate the problem, being as detailed as you can. If you can't state the problem, the solution is very hard to see. – Tony Ennis Feb 15 '12 at 15:20
  • are the edges of the rectangles parallel to the x/y axis or can they be in any orientation? – PeskyGnat Feb 15 '12 at 15:46
  • the edges are parallel and the rectangle to be filled is defined by the span of all x-ranges and all y-ranges. – dermoritz Feb 15 '12 at 15:56
  • Is your current solution of checking all (x,y) positions not working then? Do you need to support so large (x,y) coordinates that filling the 2d array would be too slow? – han Feb 15 '12 at 18:43
  • the areas are small and contain allways less than 1000 rectangles - i talk about tables that are read by humans. – dermoritz Feb 16 '12 at 07:42

1 Answers1

6

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

Community
  • 1
  • 1
Igor ostrovsky
  • 7,282
  • 2
  • 29
  • 28
  • could you please provide a reference to a book or inetlink that describes this kind of problem and it's solutions - you made me curious. In my special case i don't have to deal with much rectangles (some 100) but i can't resist to try a better/the best algorithm as long as i know there are better algorithms – dermoritz Feb 16 '12 at 07:47
  • 1
    I added a "More Info" section to my response - hopefully that helps. Have fun learning about the algorithms. :) – Igor ostrovsky Feb 16 '12 at 18:48
  • 1
    @Igor is right on. Bentley wrote a lot of the classic and seminal papers in this area. His papers have been invaluable to me. Don't minimize the fact that your are concerned with orthogonal boundaries. That is a huge deal as there has been a lot of work done in this area. The sweep line approach is pretty simple to implement for this problem just choose an axis and project the orthogonal edge to that axis and the event line on that axis would signify either the beginning or end of a rectangle. See chapter 8 of Computational Geometry: An Introduction by Preparata and Shamos. – babernathy Feb 16 '12 at 19:06