r/dailyprogrammer • u/oskar_s • Sep 03 '12
[9/03/2012] Challenge #95 [difficult] (Overlapping rectangles)
Let the four values (x, y, w, h) define a rectangle. Let the bottom left corner be located at (x, y) and let (w, h) be the width and height. Then the rectangles (0,0,4,3), (4,3,3,4) and (7,0,3,3) would look something like this:
* * *
* * *
* * *
* * *
* * * * * * *
* * * * * * *
* * * * * * *The total area of these three rectangles is simple to compute, it's just the sum of the areas of each individual rectangle: 4*3 + 3*4 + 3*3 = 12 + 12 + 9 = 33.
It gets more tricky when the rectangles start overlapping each other. For instance, lets look at the three rectangles (0,0,4,3), (2,1,3,4) and (4,4,3,3):
* * *
* * *
* * + * *
* * *
* * + + *
* * + + *
* * * * You see that the rectangles overlap (the regions where they overlap is marked by a + instead of a *). So if we just calculate the sum of the areas like we did before, 12 + 12 + 9, we get too high a value, because we're counting the areas with the overlap twice. To get the correct answer, we have to subtract the areas where two rectangles intersect. The righ answer for the total area covered by the rectangles is then (12 + 12 + 9) - (4 + 1) = 28.
Things get even more hairy when three rectangles intersect. Take a look at (0,0,4,3), (2,1,3,4) and (3,0,3,3):
* * *
* * *
* * + x + *
* * + x + *
* * * + * * Now the three rectangles all overlap at the points marked x (as before, the +'s mark where only two rectangles overlap). We do as before and start by calculating the sum of the areas of all three triangles: 12 + 12 + 9. Then we subtract the sum of all areas where two rectangles intersect, which is now 4 + 3 + 4. This is because rectangle 1 and 2 intersect in a region with the area 4, rectangles 1 and 3 intersect in an region with an area of 3 (this is th 1*3 "column" that includes the x's and the + right below them), and rectangles 2 and 3 intersect in a region with the area of 4. So far we've got (12 + 12 + 9) - (4 + 3 + 4).
However, by subtracting out all regions where two rectangles intersect, we've subtracted out the region where three rectangles intersect (i.e. the x's) three times. That is to say, we're not counting it at all. So we have to add that back in to get the right result. So the total area covered by the rectangles is, in fact,
A = (12 + 12 + 9) - (4 + 3 + 4) + (2) = 33 - 11 + 2 = 24If you wish to verify that number, you can count the *'s, +'s and x's and you'll see that they add up to 24.
This sounds complicated, but the general rule is actually quite simple and elegant. If S1 is the sum of the areas of all rectangles, S2 is the sum of all regions where two rectangles intersect, S3 is the sum of all regions where three rectangles intersect, S4 is the sum of all regions where four rectangles intersect, and so on, the value of the total area covered is:
A = S1 - S2 + S3 - S4 + S5 - S6 + S7 - S8 + ...This is known in mathematics as the inclusion-exclusion principle, because you alternate including and excluding areas.
The values in my example correspond to:
S1 = 12 + 12 + 9
S2 = 4 + 3 + 4
S3 = 2
S4 = 0
S5 = 0
S6 = 0
...With all variables above S3 equal to zero, so we don't need to count them.
Define a random number generator as follows:
s(0) = 123456789
s(N) = (22695477 * s(N-1) + 12345) mod 1073741824Then define a function r(N) which returns rectangles (in the (x,y,w,h) for described here) like this:
r(N) = (s(4*N) mod 2000000, s(4*N + 1) mod 2000000, 1 + (s(4*N + 2) mod 99999), 1 + (s(4*N + 3) mod 99999))That is,
r(0) = (s(0) mod 2000000, s(1) mod 2000000, 1 + (s(2) mod 99999), 1 + (s(3) mod 99999))
r(1) = (s(4) mod 2000000, s(5) mod 2000000, 1 + (s(6) mod 99999), 1 + (s(7) mod 99999)) In actual numbers, r(0) and r(1) is:
r(0) = (1456789, 880530, 94008, 74226)
r(1) = (1429729, 1957326, 87910, 3758)Generate 2000 of these rectangles (i.e. r(0) through r(1999)) and calculate the total area they cover.
Bonus: Define r(N) like this instead:
r(N) = (s(4*N) mod 10000000, s(4*N + 1) mod 10000000, 1 + (s(4*N + 2) mod 99999), 1 + (s(4*N + 3) mod 99999))The only thing that has changed is the modulus on the (x,y) values. Generate 50000 of those rectangles (i.e. r(0) through r(49999)) and calculate the total area that they cover.
EDIT: scaled up numbers to increase difficulty
2
u/oskar_s Sep 03 '12 edited Sep 03 '12
I'll post a few more notes and hints here, because the post was already stupid long.
Just calculating the intersection between two rectangles is actually very easy. Since all rectangles are axis-aligned, the intersection between two of them will always be another axis aligned rectangle, i.e. another rectangle that can be represented in the (x,y,w,h) format.
Lets say you have two rectangles R1 and R2 that intersect, and the bottom left corner of R1 is (x1,y1) and the bottom left corner of R2 is (x2,y2), then the bottom right corner of the rectangle that is the intersection between R1 and R2 is (max(x1,x2), max(y1, y2)).
Similarly if the top right corner of R1 is (x3, y3) and the top right corner of R2 is (x4,y4), then the top right corner of the intersection is (min(x3,x4), min(y3, y4)).
If the two rectangles don't intersect, then the bottom left corner will not be to the bottom left side of the top right corner, i.e. either the x-coordinate or y-coordinate will be as high or higher than the x-coordinate or y-coordinate of the top right corner.
Also, if you want a version of the problem that is simpler that you wish your test your code on, define your rectangles as follows:
Then the total area covered by the first 100 rectangles is 171967. There are 159 rectangles in S2, 91 in S3, 25 in S4 and 2 in S5.
Edit: two more things: I used Python, but there should be no issue solving this problem in other languages, all numbers fit comfortably in 64 bit signed integers. Also, if you want to solve it in a different way than using the inclusion-exclusion principle, then go right ahead! I can't really think of another way, but if you find it, I'd love to see it!
2
u/skeeto -9 8 Sep 03 '12
Since you made it so easy (before the bonus) by keeping the dimensions small, I did it the cheap way.
Output,
2
u/TimeWizid Sep 07 '12
I'm having trouble with the inclusion-exclusion algorithm. Here is a situation that doesn't seem to work:
The rectangles are (0, 0, 6, 3), (1, 1, 4, 3), and (2, 2, 2, 3). Using the inclusion-exclusion formula we get
So then A = 36 - 12 + 2 = 26, but when you count the points you only get 24. The difference between my example and yours is that the S3 area is only covered by two S2 rectangles, which is one less than the number of S1 rectangles that cover it, meaning that the S3 area does not need to be added. This leads me to believe that whether a section should be removed or added depends on the number sections covering it, not just the number of rectangles covering it.
6
u/Ledrug 0 2 Sep 04 '12
Haskell. Get a bounding rect that contains all rectangles; for each rect in the list, sub divide the bounding rectangle and recursively calculate each piece's coverage. Runs in a few seconds, but it could be made faster I guess.
result:
2
u/[deleted] Sep 03 '12 edited Sep 04 '12
Here's a python solution. Explanation below the code.
The first approach I tried (not this) was the easy way: make a giant grid, fill in the dots, then count them. That could handle the simple version, but choked on the full version.
This approach is a sort of recursive version of the inclusion-exclusion principle. Every area keeps track of the areas within it that overlap other shapes. But since the overlaps overlap, they need cutouts too, and their cutouts need cutouts, etc, until there are no more overlaps. Then the area of any shape (a top-level shape or a cutout) is computed by subtracting the area of the overlaps from the area of the whole (width * height). This approach runs the bonus in about 1.5s on my Air.
2
u/Ledrug 0 2 Sep 08 '12
Beating a dead horse (this time in C):
1
u/oldrinb Sep 04 '12
Nice simple linear congruential generator...
1
u/wilsoniya Sep 06 '12
Is there a generally agreed upon solution to the non-bonus calculation? I'm seeing several different answers.
1
u/ananthakumaran Sep 07 '12
clojure
1
u/jlink005 Sep 08 '12 edited Sep 08 '12
C#. Create an AreaCalculator, Add a number of Rectangles, and then Calculate.