Clever Geek Handbook

Find all rectangles in a given rectangle that do not intersect with an arbitrary shape

I need to find an algorithm to find the smallest number of overlapping rectangles within a given rectangle R that do not intersect with the union of many other rectangles contained within R. These inner rectangles can overlap. Here's a terrible ASCII drawing of the R example:

A-----------------B-------------------------+
|                                           |
|                                           |
|                                           |
|                                           |
|                 +--------+                |
|                 |........|                |
|                 |........|                |
C             +---D........|                |
|             |.........+--+                |
|             |.........|                   |
|             ++........+------+            |
|              |...............|            |
G              +---H...........|            |
|                  |...........|            |
|                  |...........|            |
|                  |...........|            |
|                  +-----------+            |
|                                           |
|                                           |
|                                           |
E-------------I----F------------------------+

The rectangles here will include (A, D), (A, I), (G, F). This looks like a problem for which the solution is well understood, but for which I just don't have enough vocabulary. Any replies, pointers, RTFM were welcomed and received with gratitude. Thank!

EDIT: As per @Paul's observation below, I am trying to find a set of rectangles that cover a space in R without covering any of the polygons made up of the union of the inner set. If that makes sense.

+3


source to share


2 answers


I believe this is one of the possible solutions.

I will refer to the overlapping rectangles as "white" and those in the solution as "black"

First of all, suppose we have a data structure suitable for intersection searches. One possible data structure is an Interval Tree , using points in one of the coordinates as intervals (for example, if a rectangle is defined by two points (x0, y0) and (x1, y1), use (x0, y1) as an interval. The link also explains, how to go to higher dimensions (in your case you need 2).

I won't go into detail on the implementation of such a data structure, but suppose we have one called Rectangles

with the following API:



  • void add(Rectangle r)

  • void remove(Rectangle r)

  • Rectangle[] getIntersecting(Rectangle r)

  • Rectangle[] getAdjacent(Rectangle r)

So now create two instances Rectangles

called black

and white

. Initialize white

with all white rectangles. Initializie black

with rectangle R

(whole domain).

  • For each rectangle rw

    in, white

    we get an array of arr

    intersecting rectangles from black.
  • For each rectangle rb

    in, black

    define the result rw-rb

    . It is a set set

    of 0, 1, 2, 3, or 4 rectangles, depending on how the two rectangles intersect.
  • remove rw

    from white

    and add content to it set

    . This may require merging rectangles from set

    with a rectangle already in white

    , if such rectangles together form a larger rectangle (they are adjacent on one side)
  • remove rb

    fromblack

  • repeat from 1 until there are black

    no more rectangles in it.
0


source


Using some basic math, we can say that the solution to your problem is to decompose a rectilinear polygon R \ union(rs)

, where union(rs)

is the polygon inside R

. The computation R \ union(rs)

can be done with the Greiner-Hormann-algorithm . Note that this step will result in a polygon with holes and - only if the inner polygon contains holes - several other polygons. The decomposition is described here (this is only an approximation, but so far I have not been able to find the exact algorithm).



0


source






More articles:


All Articles