## Computing a set overlapping rectangles

### Computing a set overlapping rectangles

I'm trying to do some hand-coded sprite stuff, and am a little stumped.

I have a large set of rectangles, R. I am trying to rapidly compute a
subset of R, "Overlap(r)", where Overlap(r) is the set of all rectangles
in R that overlap an arbitrary rectangle r. The rectangles are of
arbitrary size.

I'm looking for an alghorithm or indexing mechanism that can sort the
rectangles in such a way that I don't have to iterate through all the
rectangles in R to computer Overlap(r). Note that because the rectangles
in R could potentially move around, the cost of maintaining the index
can't be prohibitive, either.

Chris

### Computing a set overlapping rectangles

Quote:>I'm trying to do some hand-coded sprite stuff, and am a little stumped.

>I have a large set of rectangles, R. I am trying to rapidly compute a
>subset of R, "Overlap(r)", where Overlap(r) is the set of all rectangles
>in R that overlap an arbitrary rectangle r. The rectangles are of
>arbitrary size.

>I'm looking for an alghorithm or indexing mechanism that can sort the
>rectangles in such a way that I don't have to iterate through all the
>rectangles in R to computer Overlap(r). Note that because the rectangles
>in R could potentially move around, the cost of maintaining the index
>can't be prohibitive, either.

>Chris

One of the easiest and in some cases the fastest solution is to maintain
two sorted lists of coordinates, one for the endpoints of the x-projections
of the rectangles and one for the y-projections. This would work especially
well in situations where the query rectangle is one of the rectangles of R
and there is some frame-to-frame coherence, ie. rectangles move smoothly.
The sorting method you should use is insertion sort, which would take
expected linear time in cases with a lot of frame-to-frame coherence. After
each move of rectangles the lists are sorted. During the sorting phase the
changes in overlap status of rectangles are recorded. By maintaining a list
of overlapping pairs or an overlap matrix, the overlapping rectangles can
easily be retrieved. There you have it, in expected linear time.

The algorithms described in computational geometry literature which are
based on trees of interval trees are monsters to update in case of moving
rectangles, so I would not recommend using them.

This method is used in incremetal collision detection algorithms. Check out
I_COLLIDE, at http://www.cs.unc.edu/~manocha/collide.html. Also, look at
articles by David Baraff.

Gino

--
Gino

### Computing a set overlapping rectangles

Quote:>One of the easiest and in some cases the fastest solution is to maintain
>two sorted lists of coordinates, one for the endpoints of the x-projections
>of the rectangles and one for the y-projections. [..]
>There you have it, in expected linear time.

While I don't question the merits of this approach, I'm not sure that it's
the best solution to the problem. I think that the original poster was
after an algorithm that finds all rectangles overlapping *one* query
rectangle. That can of course trivially be done in linear time by just
testing all rectangles. So "efficient" for this problem would be
logarithmic time, which you achieve with a multidimensional search tree.
The above sounds like an algoritm for finding *all* overlaps in a set
of rectangles.

Quote:>The algorithms described in computational geometry literature which are
>based on trees of interval trees are monsters to update in case of moving
>rectangles, so I would not recommend using them.

Moving rectangles in an n-D tree probably means deleting and re-inserting
nodes. While insertion is trivial and well treated in the text books,
deletion is indeed much more difficult. I do it by removing the whole
partial tree* below the node to delete, and re-inserting all of
these nodes. While this sounds costly, it's relatively simple, it works,
and it's efficient enough for my purpose. Since a tree naturally has
the property that most nodes are close to the leaves, the partial tree
is normally small.
--

The problem:  given an arbitrary bit map, find a set of filled
rectangles that matches the bitmap while *minimizing the number of rectangles
used*.

An example:  the bits

ABCDEFGH

u 00000000
v 00111100
w 00111100
x 00000110
y 00000110
z 00000000

are matched by two filled rectangles, the first running from row v to row w and
from column C to column F, the second running from run x to row y and from
column F to column G.

If you've got a pointer to the solution, I'd appreciate hearing from you by
mail.
--