2

I want to compress many non-overlapping rectangles into larger rectangles When they are adjacent.

Pseudo-code for my current algorithm:

do
   compress horizontally using sweep and prune
   compress horizontal output vertically using sweep and prune
while (this output is small than previous output)

Here's a link to sweep and prune.

This is working well, but I want to know if there are approaches which result in fewer rectangles output. I figure there's more sophisticated than what I'm doing now.

William Morrison
  • 10,953
  • 2
  • 31
  • 48

1 Answers1

5

So it sounds like your problem is that you have small gaps between the rectangles preventing them from being collected together into a single piece. If you have access to the source code for the sweep and prune method, you can add a buffer to the "overlap" test, but I think it would be more optimal to consider using an R-Tree. This will index the rectangular spaces without messing with limits on gaps etc.

R-Tree Wiki

Here is a relevant paper by Sellis et. al. describing the R+ tree:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&rep=rep1&type=pdf

here is a C# implementation of an R-Tree

http://sourceforge.net/projects/cspatialindexrt/

[Edit - After Comment 1]

So let me see if I can capture the current problem.

  • Rectangles are joined in passes of horizontal/vertical adjacency tests.
  • Rectangles are only joined if the adjacent boundary for both is equal.
  • The intermediate result of any join must also form a valid rectangle.
  • The result is non-optimal because the sequence of joining.

I think you're actually looking for the minimum dissection into rectangles of a rectilinear polygon. The first step would be to join ALL the touching rectangles together, regardless of whether they form a rectangle or not. I think you are getting caught up in problems with the intermediate stages of each step in the process also needing to be complete rectangle deconstructions, leading to a sub-optimal result. If you merge them together into a single rectilinear polygon, you can use graph theory mechanisms.

Minimum Dissection into Rectangles of a Rectilinear Polygon

You can check out Graph-Theoretic Solutions to Computational Geometry Problems by David Eppstein

Or investigate Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping by Gareth Rees

Community
  • 1
  • 1
Ted
  • 3,212
  • 25
  • 20
  • Thanks for the reply! Rtree looks interesting but i dont think it will work for me. Here if there is a gap the rectangles cannot be combined. The output should have the same area as the input and cover exactly the same ground. – William Morrison Jul 21 '13 at 17:58
  • The second link sounds like exactly what I'm looking for. Once I've had time to read it I'll reply or accept. I appreciate your time here. – William Morrison Jul 21 '13 at 21:23
  • This is precisely what I was looking for, I can't thank you enough. Hopefully the solution is not out of my depth. Complex stuff. – William Morrison Jul 22 '13 at 13:51