0

Help please. I'm working on an algorithm with this requirement.

Given 4 "right" rectangles (right rectangles have edges parallel to x or y), find the area that is covered by any of them

For example, the area in grey are covered by any of those 4 rectangles in the picture below.enter image description here

I am not quite understand the question. Could someone help me please?

daeril
  • 9
  • 1
  • 1
    Do you need the area of _any_ rectangle or the area of _all_ rectangles combined? The first would be easy, it's just the height of one rectangle times its width. The second is a rather complex question. What do you have so far? – PMF Jan 09 '18 at 10:32
  • "I am not quite understand the question" - I don't think we'll be able to give an answer if you don't understand what you are asking. What are the expected inputs and outputs? Can you put a specific example? (not just a picture, but an example input to the algorithm and its corresponding output). – jdehesa Jan 09 '18 at 11:00
  • One possibility: sum of the areas of the 4 rectangles - sum of the intersections of 2 rectangles + sum of the intersections of 3 rectangles - the intersection of all 4 rectangles – maraca Jan 09 '18 at 11:29
  • Possible duplicate of [What is an Efficient algorithm to find Area of Overlapping Rectangles](https://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles) – user3483203 Jan 09 '18 at 11:30

1 Answers1

1

One way would be to use the Inclusion-Exclusion principle applied to areas. Here is the 3 rectangle case:

A = Area( R[0]) + Area( R[1]) + Area( R[2])
  - ( Area( inter( R[0], R[1])) 
    + Area( inter( R[0], R[2]))
    + Area( inter( R[1], R[2]))
    )
  + Area( inter( inter( R[0], R[1]), R[2]))

where 

Area(R) gives the area of a rectangle R, and 
inter( R, S) is the rectangle that is the intersection of R and S

The 4 rectangle case will be a little tedious, but I suspect it would still be easier to program long-hand rather than using loops.

dmuir
  • 4,211
  • 2
  • 14
  • 12