CODEWITHSUNDEEP
pythoncomputational-geometry
Aleks Vujic
Aleks Vujic

Reputation: 2251

Total area of overlapping rectangles

Let's say that we have the following 4 rectangles which are all defined with x and y coordinates of all their vertices (starting from upper left in clock-wise direction). All rectangles have their sides parallel to x and y axis. Note: I am open about using any existing library if it exists.

enter image description here

Example for blue rectangle:

[(20, 50), (40, 50), (40, 110), (20, 110)]

How can I calculate the total area that they cover (marked below with blue)?

enter image description here

Upvotes: 4

Views: 3433

Answers (3)

Cait
Cait

Reputation: 1

You use a sweep line algorithm to maintain a horizontal projection for each rectangle. Here's a library with multiple solutions: https://jilljenn.github.io/tryalgo/_modules/tryalgo/union_rectangles.html#union_rectangles

Upvotes: 0

dmuir
dmuir

Reputation: 4431

An easy coding, though not super efficient, way to do this is to use the inclusion-exclusion principal, which in its simplest form says that for any two (measureable) subsets A and B

area( A union B) = area( A) + area( B) - area( A inter B)

We are only concerned with unions of axis aligned rectangles, and the intersection of a rectangle with a union of rectangles is itself a union of rectangles. So to find the area of the union of rectangles R1, .. Rn we get the recursive function (in pseudo code as I don't know python, sorry)

area ( R1 union R2 union .. Rn )
 = rectarea( R1) + area( R2 union .. Rn) 
 - area( (R1 inter R2) union (R1 inter R3) .. (R1 inter Rn)

If we know xmin,xmax,ymin,ymax for a rectangle then its area is

(xmax-xmin)*(ymax-ymin)

If we have two rectangles R and S, their intersection is

  (RinterS).xmin = max( R.xmin, S.xmin)
  (RinterS).xmax = min( R.xmax, S.xmax)
  (RinterS).ymin = max( R.ymin, S.ymin)
  (RinterS).ymax = min( R.ymax, S.ymax)

When computing (R1 inter R2) etc you have to do that in a copy of the inputs not the inputs themselves (as the inputs may be used by a recursive call that comes later). Its worth eliminating the empty resulting rectangles (ie those with xmin>=xmax or ymin>=ymax). If you don't eliminate them you have to ensure that their areas are computed as 0.

I have C code that implements this, which I'll post if you're interested.

Upvotes: 0

thshea
thshea

Reputation: 1087

Here are some random rectangles I drew up: Random rectangles on an image

To visualize this method, if you draw a vertical line that spans the whole screen over each vertical edge of a rectangle, you can see that each marks out a new rectangle. You can find these points by creating a sorted list of the x-coordinates of all the points and removing duplicates.

Rectangles with vertical lines over all vertical edges

And with the new rectangles shaded:

New rectangles shaded in

Now your problem becomes finding the area of each rectangle in the region by multiplying the width and height.

This method solves the problem where three rectangles overlap - if you used an inclusion-exclusion method (adding the areas and subtracting the overlap) you would then need to add back the areas where three overlap, subtract where four overlap, etc.

Note that there are cases (visible in the last photo) where two rectangles are present in one region. You will need to check the case where one rectangle ends before the next begins. You could also solve this by dividing the grid in the y-axis as well, but then you have to test if each region has part of a rectangle in it which takes time.

Here is one example of this, the code itself is done in Swift, not Python, but there are diagrams and a writeup that may be helpful.

Upvotes: 3

Related Questions