Covered area problem is a geometry problem represented in Cartesian product. Many rectangles are located in a two dimensional environment. Each rectangle has its upper-left coordinate and lower-right coordinate to indicate its position. One rectangle can be placed separated from other rectangles, can be placed inside some others, or can be placed where part of it overlaps other rectangles.
Covered Area Problem is a classic algorithm problem used for academic teaching purposes. The basic idea is to give several pairs of Cartesian coordinates as the input. Each pair of coordinate represents the upper-left corner and lower-right corner of a rectangle. The goal of the system is to find out the total area covered by all those rectangles. Please note that we can not just add all the covered area of each rectangles since the rectangles can be overlapped each other in any order.
Common solution usually implements two dimensional flag mapping. Each rectangle will map several flags covered by it into value 1 (covered). If the flag in a location is already 1, then no change needed. At the end of the process, the program will count how many flags have value 1 and that would be the answer.
This common solution has several weaknesses :
1. It consumes a huge size of memory, larger Cartesian coordinates can not be calculated.
2. Two dimensional array is very difficult to be implemented in logic and functional programming.
The algorithm used in this article will work on the all coordinates of integer numbers, meaning the top-left coordinate is (-32768,32767) and the lower-right coordinate is (32767,-32768). This algorithm will divide the region into 4 equal subsections. Instead of marking flags in a two dimensional array (65526 x 65536), this algorithm will compare each subsection with the rectangles. When a subsection is totally uncovered, the value 0 will be given. When a subsection is totally covered, the value 1 will be given. When a subsection is partially covered, the value 2 will be given and that subsection will be divided into 4 smaller equal subsections, and the same calculation will be performed recursively.
[toggle title=”C++ version”]
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
int CompareLine(int a,int b,int c,int d)
{
int pos=0;
if (c<a)
{
if (d=a) pos=0; else if ((d>a) && (d<b)) pos=2; else pos=1;
}
else if (c==a)
{
if (d>=b) pos=1; else pos=2;
}
else if ((c>a) && (c<b)) pos=2;
return pos;
}
int CompareTwoAreas(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
int dx; int dy;
dx=CompareLine(x1,x2,x3,x4);
dy=CompareLine(y2,y1,y4,y3);
if ((dx==0) || (dy==0)) return 0;
else if ((dx==1) && (dy==1)) return 1;
else return 2;
}
class cTree
{
char isCovered;
int x1,y1,x2,y2;
cTree * ChildArea;
public:
cTree(void);
void Init(int vx1, int vy1, int vx2, int vy2);
void AddRect(int vx1, int vy1, int vx2, int vy2);
long CountArea();
};
cTree::cTree (void)
{
isCovered=0;
}
void cTree::Init(int vx1, int vy1, int vx2, int vy2)
{
x1=vx1; y1=vy1; x2=vx2; y2=vy2;
}
void cTree::AddRect(int vx1, int vy1, int vx2, int vy2)
{
int i;
int oldValue, newValue;
oldValue=isCovered;
newValue=CompareTwoAreas(x1,y1,x2,y2,vx1,vy1,vx2,vy2);
if (newValue==1) isCovered=1;
if ((newValue==2) && (oldValue!=1)) isCovered=2;
if ((isCovered!=2) && (oldValue==2)) delete ChildArea;
if (isCovered==2)
{
if (oldValue2)
{
ChildArea = new cTree[4];
ChildArea[0].Init(x1,y1,(x1+x2)/2,(y1+y2)/2);
ChildArea[1].Init((x1+x2)/2,y1,x2,(y1+y2)/2);
ChildArea[2].Init(x1,(y1+y2)/2,(x1+x2)/2,y2);
ChildArea[3].Init((x1+x2)/2,(y1+y2)/2,x2,y2);
}
for (i=0;i4;i++) ChildArea[i].AddRect(vx1,vy1,vx2,vy2);
}
}
long cTree::CountArea()
{
long temp=0;
if (isCovered==1) temp=(x2-x1)*(y1-y2);
if (isCovered==2) temp=ChildArea[0].CountArea()+ChildArea[1].CountArea()+
ChildArea[2].CountArea()+ChildArea[3].CountArea();
return temp;
}
void main() {
int i, NumOfRect, x1, y1, x2, y2;
cTree WorkSpace;
clrscr();
WorkSpace.Init(-32768,32767,32767,-32768);
cout " Covered Area Calculator - programmed by Robert Setiadi\n";
cout << "===============================================================\n";
cout << "this program accept any number of rectangles as input\n";
cout << "and calculate total area covered by all those rectangles\n";
cout << "a rectangle is defined by top left and bottom right coordinates\n";
cout << "accepted range from -32768 to +32767\n\n";
cout << "Please input the number of rectangles : "; cin >> NumOfRect;
for (i=0; i<NumOfRect; i++)
{
cout "Rectangle " i+1 << " [x1,y1,x2,y2] = ";
scanf("%d,%d,%d,%d",&x1,&y1,&x2,&y2);
fflush(stdin);
WorkSpace.AddRect(x1,y1,x2,y2);
}
cout << "\nTotal covered area = " << WorkSpace.CountArea();
getch();
}[/toggle]
[toggle title=”Haskell version”]
compareLine :: Int -> Int -> Int -> Int -> Int
compareLine a b c d = if c < a
then if d <= a
then 0
else if d >= b
then 1
else 2
else if c == a
then if d >= b
then 1
else 2
else if (c > a) && (c < b)
then 2
else 0
compareTwoAreas :: Int -> Int -> Int -> Int -> Int -> Int -> Int -> Int -> Int
compareTwoAreas x1 y1 x2 y2 x3 y3 x4 y4
| ((compareLine x1 x2 x3 x4)==0) || ((compareLine y2 y1 y4 y3)==0) = 0
| ((compareLine x1 x2 x3 x4)==1) && ((compareLine y2 y1 y4 y3)==1) = 1
| otherwise = 2
data Rectangle = Rect Int Int Int Int
data CTree = Leaf Int Int Int Int Int | Branch Int Int Int Int Int CTree CTree CTree CTree
deriving (Show,Eq)
addRectangle :: CTree -> Int -> Int -> Int -> Int -> CTree
addRectangle (Leaf i x1 y1 x2 y2) nx1 ny1 nx2 ny2
| (compareTwoAreas x1 y1 x2 y2 nx1 ny1 nx2 ny2)==1 = Leaf 1 x1 y1 x2 y2
| ((compareTwoAreas x1 y1 x2 y2 nx1 ny1 nx2 ny2)==2) && (i/=1) =
Branch 2 x1 y1 x2 y2
(addRectangle (Leaf 0 x1 y1 (div (x1+x2) 2) (div (y1+y2) 2)) nx1 ny1 nx2 ny2)
(addRectangle (Leaf 0 (div (x1+x2) 2) y1 x2 (div (y1+y2) 2)) nx1 ny1 nx2 ny2)
(addRectangle (Leaf 0 x1 (div (y1+y2) 2) (div (x1+x2) 2) y2) nx1 ny1 nx2 ny2)
(addRectangle (Leaf 0 (div (x1+x2) 2) (div (y1+y2) 2) x2 y2) nx1 ny1 nx2 ny2)
| otherwise = Leaf i x1 y1 x2 y2
addRectangle (Branch i x1 y1 x2 y2 z1 z2 z3 z4) nx1 ny1 nx2 ny2
| (compareTwoAreas x1 y1 x2 y2 nx1 ny1 nx2 ny2)==1 = Leaf 1 x1 y1 x2 y2
| ((compareTwoAreas x1 y1 x2 y2 nx1 ny1 nx2 ny2)==2) && (i/=1) =
Branch 2 x1 y1 x2 y2
(addRectangle z1 nx1 ny1 nx2 ny2)
(addRectangle z2 nx1 ny1 nx2 ny2)
(addRectangle z3 nx1 ny1 nx2 ny2)
(addRectangle z4 nx1 ny1 nx2 ny2)
| otherwise = Branch i x1 y1 x2 y2 z1 z2 z3 z4
buildTree :: CTree -> [Rectangle] -> CTree
buildTree t [] = t
buildTree t ((Rect a b c d):zs) = buildTree (addRectangle t a b c d) zs
initTree :: [Rectangle] -> CTree
initTree t = buildTree (Leaf 0 (-32768) 32767 32767 (-32768)) t
privCountArea :: CTree -> Int
privCountArea (Leaf i x1 y1 x2 y2)
| i==1 = (x2-x1)*(y1-y2)
| otherwise = 0
privCountArea (Branch i x1 y1 x2 y2 a b c d) = (privCountArea a) + (privCountArea b) + (privCountArea c) + (privCountArea d)
countArea :: [Rectangle] -> Int
countArea i = privCountArea (initTree i)[/toggle]
[toggle title=”Prolog version”]
compareLine(A,B,C,D,Result) :-
( C < A ->
( D =< A -> Result is 0 ;
D > A, D < B -> Result is 2 ;
D >= B -> Result is 1
) ;
C = A ->
(
D >= B -> Result is 1 ;
D < B -> Result is 2
) ;
C > A ->
(
C < B -> Result is 2 ;
C >= B -> Result is 0
)
).
compareTwoAreas(X1,Y1,X2,Y2,X3,Y3,X4,Y4,Result) :-
compareLine(X1,X2,X3,X4,R1), compareLine(Y2,Y1,Y4,Y3,R2),
( ((R1 = 0); (R2 = 0)) -> Result is 0 ;
((R1 = 1), (R2 = 1)) -> Result is 1 ;
((R1 + R2) > 2) -> Result is 2).
leaf(_,_,_,_,_).
addRectangle(leaf(Filled,X1,Y1,X2,Y2),NX1,NY1,NX2,NY2,Result) :-
compareTwoAreas(X1,Y1,X2,Y2,NX1,NY1,NX2,NY2,R),
( R = 1 -> Result = leaf(1,X1,Y1,X2,Y2) ;
R = 2, Filled \= 1 ->
( Xm is (X1 + X2) // 2,
Ym is (Y1 + Y2) // 2,
addRectangle(leaf(0,X1,Y1,Xm,Ym),NX1,NY1,NX2,NY2,R1),
addRectangle(leaf(0,Xm,Y1,X2,Ym),NX1,NY1,NX2,NY2,R2),
addRectangle(leaf(0,X1,Ym,Xm,Y2),NX1,NY1,NX2,NY2,R3),
addRectangle(leaf(0,Xm,Ym,X2,Y2),NX1,NY1,NX2,NY2,R4),
Result = branch(2,X1,Y1,X2,Y2,R1,R2,R3,R4) );
R = 2, Filled = 1 -> Result = leaf(1,X1,Y1,X2,Y2) ;
R = 0 -> Result = leaf(Filled,X1,Y1,X2,Y2)).
addRectangle(branch(Filled,X1,Y1,X2,Y2,Z1,Z2,Z3,Z4),NX1,NY1,NX2,NY2,Result) :-
compareTwoAreas(X1,Y1,X2,Y2,NX1,NY1,NX2,NY2,R),
( R = 1 -> Result = leaf(1,X1,Y1,X2,Y2) ;
R = 2, Filled \= 1 ->
( addRectangle(Z1,NX1,NY1,NX2,NY2,R1),
addRectangle(Z2,NX1,NY1,NX2,NY2,R2),
addRectangle(Z3,NX1,NY1,NX2,NY2,R3),
addRectangle(Z4,NX1,NY1,NX2,NY2,R4),
Result = branch(2,X1,Y1,X2,Y2,R1,R2,R3,R4) );
R = 2, Filled = 1 -> Result = leaf(1,X1,Y1,X2,Y2) ;
R = 0 -> Result = branch(Filled,X1,Y1,X2,Y2,Z1,Z2,Z3,Z4)).
buildTree(T,[],T2) :- T2 = T.
buildTree(T,[rect(A,B,C,D)|ZS],T2) :-
addRectangle(T,A,B,C,D,T3),
buildTree(T3,ZS,T2).
initTree(L,Result) :- buildTree(leaf(0,(-32768),32767,32767,(-32768)),L,Result).
privCountArea(leaf(Filled,X1,Y1,X2,Y2), Result) :-
( Filled = 1 -> Result is (X2 - X1) * (Y1 - Y2) ;
Filled = 0 -> Result is 0 ).
privCountArea(branch(_,_,_,_,_,Z1,Z2,Z3,Z4), Result) :-
( privCountArea(Z1,Z1r),
privCountArea(Z2,Z2r),
privCountArea(Z3,Z3r),
privCountArea(Z4,Z4r),
Result is Z1r + Z2r + Z3r + Z4r).
countArea(A,Result) :-
initTree(A,Tree),
privCountArea(Tree,Result).[/toggle]
Just some simple codes, they calculate everything in recursion so the same algorithm can be implemented in imperative programming language (C++), functional programming language (Haskell) and logic programming language (Prolog).
C++ code is tested and compiled using Turbo C++ 3.
Haskell code is tested and compiled using Hugs98.
Prolog code is tested and compiled using SWI-Prolog.
Leave A Comment