4

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

Sam Carlson
  • 1,891
  • 1
  • 17
  • 44
  • Are the rectangles axis aligned? – funie200 Nov 30 '20 at 14:03
  • Yes, they will always be aligned. I edited the question. – Sam Carlson Nov 30 '20 at 14:03
  • If all corners cordinates are solely integers this might be of use to you: https://stackoverflow.com/a/25355331 – Daweo Nov 30 '20 at 14:09
  • can you give coordinates for all four triangles so we can work with them – coderoftheday Nov 30 '20 at 14:11
  • 1
    You can use the answer from [how to calculate the overlapped area between two rectangles](https://stackoverflow.com/questions/27152904/calculate-overlapped-area-between-two-rectangles) to subtract the overcounting from simply summing the area of all rectangles individually. If you give us coords for all the rectangles and the expected output, it'll help more. – Reti43 Nov 30 '20 at 14:19
  • https://stackoverflow.com/questions/55702005/area-of-union-of-rectangles-using-segment-trees – HEKTO Dec 11 '20 at 04:46

3 Answers3

3

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.

thshea
  • 1,048
  • 6
  • 18
  • 1
    The cited website also includes a writeup of the method and more diagrams, so I would argue that it is still relevant. I updated the post to reflect this. – thshea Nov 30 '20 at 14:25
  • @funie200: very negative comment. IMO the link adds a lot. –  Dec 03 '20 at 19:19
  • @YvesDaoust After the edit, I should have removed the comment, forgot that. Before the edit, IMO the reference to the link was not helpful. – funie200 Dec 03 '20 at 19:49
0

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.

dmuir
  • 4,211
  • 2
  • 14
  • 12
0

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

Cait
  • 1
  • 4