CODEWITHSUNDEEP
c#javacompressioncollision-detection
William Morrison
William Morrison

Reputation: 11006

Combining many rectangles into fewer rectangles

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.

Upvotes: 2

Views: 2720

Answers (1)

Ted
Ted

Reputation: 3260

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

Upvotes: 5

Related Questions