Re: Finding lines surrounding set of rectangles
- From: Gene <gene.ressler@xxxxxxxxx>
- Date: Fri, 3 Jul 2009 14:53:51 -0700 (PDT)
On Jul 3, 4:47 pm, Gert Vierman <gert.vie...@xxxxxxxxx> wrote:
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.
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.
.
- Follow-Ups:
- References:
- Finding lines surrounding set of rectangles
- From: Gert Vierman
- Finding lines surrounding set of rectangles
- Prev by Date: Re: maintenance of hash tables.
- Next by Date: Re: maintenance of hash tables.
- Previous by thread: Finding lines surrounding set of rectangles
- Next by thread: Re: Finding lines surrounding set of rectangles
- Index(es):
Relevant Pages
|
