calculate the "complete area" of n overlapping rectangles with delphi

[Nico S. Beck]

Hi,

i've a more mathematical problem. I need to calculate the "complete (total?)
area" (don't know the right english word yet) of any number of overlapping
rectangles (result must be a flooting-point-value). The user draws some
overlapping rectangles on my form (it's no problem to get the coordinates of
them - i've put them in a dynamic list). I think i've to find a recursively
algorithm, because the formula is enough complex with 3 or 4 rectangles.

So far i've functions to calculate the points of intersection and the plane
of section for two rects.

Who can help me? Someone knows an alorithm for this problem?

Thanks in advance,
Nico

--
__________________________
Nico S. Beck
www.NSBnet.de
n...@NSBnet.de

[Une-V]

I suppose you only have to consider rectangles whose the edges are parallel
to the X- or Y-axis;
otherwise the common surface isn't a rectangle anymore (in general) and the
algorithm will be much more difficult.

I think tail-recursion is the easiest way to achieve this:

@pre: length of list>=2; all elements of the list are effective (<>nil)
function getCommonRectangle(rectangles: array of TRectangle): TRectangle;
var
...
begin
if length(rectangles)=2 then
begin
//Calculate (X1, Y1), (X2, Y2): common Rectangle of
rectangles[0] and rectangles[1]
result:=TRectangle.create(X1, Y1, X2, Y2);
end
else begin
setlength(newList, length(rectangles)-1);
for(i:=1 to length(rectangles)-1) newList[i-1]:=rectangles[i];//Copy
rectangles into new list, EXCEPT first rectangle
tempRect:=getCommonRectangle(newList);
setlength(newList, 2);
newList[0]:=rectangles[0];
newList[1]:=tempRect;
result:=getCommonRectangle(newList);
end;
end;

function getCommonArea(rectangles: array of TRectangle): extended;
begin
result:=getCommonRectangle(rectangles).getSurfaceArea();
end;

"Nico S. Beck" <n...@NSBnet.de> schreef in bericht news:3cd5052d_2@dnews...

[Rafael Cotta]

I'll try to find a solution for this, but maybe using Google to post on an
algorithms newsgroup will give you better answers.

Rafael

"Nico S. Beck" <n...@NSBnet.de> escreveu na mensagem news:3cd5052d_2@dnews...

[Alejandro Triaca]

"Nico S. Beck" <n...@NSBnet.de> escribió en el mensaje
news:3cd5052d_2@dnews...

> them - i've put them in a dynamic list). I think i've to find a
recursively
> algorithm, because the formula is enough complex with 3 or 4 rectangles.
> So far i've functions to calculate the points of intersection and the
plane
> of section for two rects.

I don't know what you are trying to do. If you have n rectangles and you
have it solved for two of them, then you can Add all the values you are
getting, using the combinations of all of rectangles taken in pairs (If you
have 3 rectangles (A,B,C) then you need to sum the intersections of AB, AC
and BC?)

You can have a double loop that takes care of this... But I´m afraid I´m not
getting you quite right...
Smth like (not tested)...

{-------------------------------------}
TotalArea := 0;
if Rects.Count >= 2 then
for I := 0 to Rects.Count - 2 do
for J := (I+1) to Rects.Count - 1 do
TotalArea := TotalArea + OverlappedArea(Rects[I], Rects[j]);
{-------------------------------------}

¿Did this help you a bit?

=========
Good Luck,
Alejandro.

[Rafael Cotta]

Imagine A B and C overlap, creating four areas: AB, AC, BC and ABC. So,
you'll need to do A+B+C-AB-AC-BC+ABC. As many more rectangles the longer is
the formula.

Here we call this "princípio da inclusão e exclusão", may be "inclusion and
exclusion principle" in English.

Rafael

"Alejandro Triaca" <atr...@XXX-NOSPAM-XXXadinet.com.uy> escreveu na
mensagem news:3cd814c8$1_2@dnews...

[Nico S. Beck]

Hi,

> Imagine A B and C overlap, creating four areas: AB, AC, BC and ABC. So,
> you'll need to do A+B+C-AB-AC-BC+ABC. As many more rectangles the longer
is
> the formula.

thats the problem. If i've 5 rectangles, I need to do this:

(A+B+C+D+E)

- AB - AC - AD - AE
- BC - BD - BE
- CD - CE
- DE

+ ABC + ABD + ABE
+ ACD + ACE
+ BCD + BCE + BDE
+ CDE

- ABCD - ABCE
- BCDE

+ ABCDE

(hope i don't forgot one :-) )

This is a realy problem with n rectangles!

Nico

[Alejandro Triaca]

I'm afraid I didn't quite get you at the beggining <g>.

I'll try to look up an answer later (if I have one!) ;) But it really seems
to be a "messy" thing.

=======
Good luck,
Ale.

[Volker W. Walter]

> i've a more mathematical problem. I need to calculate the "complete (total?)

> area" ... of any number of overlapping

> rectangles (result must be a flooting-point-value).

> You can have a double loop that takes care of this...

> {-------------------------------------}
> TotalArea := 0;
> if Rects.Count >= 2 then
> for I := 0 to Rects.Count - 2 do
> for J := (I+1) to Rects.Count - 1 do
> TotalArea := TotalArea + OverlappedArea(Rects[I], Rects[j]);
> {-------------------------------------}

If n is the number of rectangles then
first calculatating the sum of all rectangels
second subtracting the overlapping areas
will be an algorithm with time complexity n^2.

Therefore I try to suggest an n * log (n) approach.

A----------B
! !
! i----3---------J
! ! ! !
C-----0----d !
! !
! !
E---1------f !
! k------2-------I
! !
G----------H

In the example there are only n= 3 rectangles
abcd, efgh, jklm
with m=4*3=12 points

First
find the convex hull of your points "ACEGHIJB"
time complexity m * log(m)
cited in sedgewick; Algorithms
use packge-wrapping, graham scan, interior elimination

Second
walk around this polygon
and calculate the area of this polygon
time complexity m

Third
walk around this polygon again
and calculate the area which has to be subtracted
this has to be done if adjacent points of the convex hull
are not connected be horizontal or vertical lines.
CE10
HI2

[Nico S. Beck]

Hi,

thank you, I try that!

Bye,
Nico