Finding lines surrounding set of rectangles

[Gert Vierman]

Hello,

Can anybody point me to an algorithm to find the set of lines which
circumvent a set of rectangles, which are optionally adjacent ? A small
picture to explain :

http://zevv.nl/div/lijntjes.png

The input of the algorithm I'm looking for consists of the coordinates
of the three blue rectangles, the output would be the set of coordinates
of the 12 red lines.

Thank you very much,

Gert

[Gene]

You're trying to compute the boundary polygon of the union of
rectangles. It's standard computational geometry. The CGAL library
will handle it easily. I'm a bit surprised that it's not easy to
find code on line, but here are some places to look.

This particular problem was studied long ago in conjunction with VLSI
design. See for example: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1585410&isnumber=33444

Line sweep algorithms are often used to solve problems like this
efficiently. So try searching for "line sweep rectangle union". or
"line sweep rectangle boolean operation".

There's code at

http://olympiad.cs.uct.ac.za/presentations/camp1_2009/linesweep_handout.pdf

for a tiny program to compute the area of a rectangle union. It will
not be too hard to modify this to get the boundary.

There's also an interesting-looking paper at

http://dml.cz/bitstream/handle/10338.dmlcz/104022/AplMat_28-1983-3_2.pdf

You might also search for "line sweep polygon union" or "line sweep
polygon boolean operation", which will give you the more general
algorithms that you can simplify for the case of rectangles.

[Ico]

Gene <gene.r...@gmail.com> wrote:

> On Jul 3, 4:47ï¿œpm, Gert Vierman <gert.vie...@gmail.com> wrote:
>
>> Can anybody point me to an algorithm to find the set of lines which
>> circumvent a set of rectangles, which are optionally adjacent ? A small
>> picture to explain :
>>

>> ï¿œhttp://zevv.nl/div/lijntjes.png

>>
>> The input of the algorithm I'm looking for consists of the coordinates
>> of the three blue rectangles, the output would be the set of coordinates
>> of the 12 red lines.
>
>
> You're trying to compute the boundary polygon of the union of
> rectangles. It's standard computational geometry. The CGAL library
> will handle it easily. I'm a bit surprised that it's not easy to
> find code on line, but here are some places to look.

Yes, I suspected this was plain-simple-out-of-the-mathbook-stuff, but
I also had a hard time finding appropriate solutions.

> This particular problem was studied long ago in conjunction with VLSI
> design. See for example: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1585410&isnumber=33444
>
> Line sweep algorithms are often used to solve problems like this
> efficiently. So try searching for "line sweep rectangle union". or
> "line sweep rectangle boolean operation".
>
> There's code at
>
> http://olympiad.cs.uct.ac.za/presentations/camp1_2009/linesweep_handout.pdf
>
> for a tiny program to compute the area of a rectangle union. It will
> not be too hard to modify this to get the boundary.
>
> There's also an interesting-looking paper at
>
> http://dml.cz/bitstream/handle/10338.dmlcz/104022/AplMat_28-1983-3_2.pdf
>
> You might also search for "line sweep polygon union" or "line sweep
> polygon boolean operation", which will give you the more general
> algorithms that you can simplify for the case of rectangles.

Ok, thank you for the numerous pointers, I'll study them to see what's
the best way to get things done.

Thanks,