How to calculate the area of multiple overlapping right-angled polygons?

Question

I am looking for a way to calculate the common areas covered by multiple overlapping polygons. The polygons are all right-angled, if that helps makes things easier.

So for example:

   BBBBB
   BBBBB
AAA---BB
AAA---BB
AAAAAA
AA--AA
AA--AA
  LL
  LL
  LLLLLL
  LLLLLL

I would like to find the common area covered by A, B and L, which would equal: B = 5x4 = 20 + A = 6x5 = 30 + L = 4x2 + 6x2 = 20 = 70 minus overlapping areas: - 10 = 60 (common area covered by all polygons)

I need to be able to cater for situations where 3 or more polygons occupy the same area. Is there a suitable algorithm for this, which could take arrays of arrays of x/y co-ordinates as inputs? (sample Java source code would be very welcome).

Answer 1

Another way to do it would be to calculate area using a contour integral. Walk around the perimeter of the area and calculate area using Green's theorem and numerical quadrature. Easy peasy.

Answer 2

If you can represent the polygons as 2D int or bool arrays (A[i][j] == 1 if the ijth slot is contained in the polygon, 0 otherwise) then you can create the union of the polygons on a larger 2D "bounding" array.

The algorithm is something like this:

// get your polygons, each represented by a 2D array as described above

// create a "bounding" array B that can contain all polygons (watch out for
// sparsely spaced polygons in which case B could be large)

// populate B s.t. B[i][j] == 1 if ijth slot is contained in 
// the union of all polygons

// count all slots in B where B[i][j] == 1 (this will be the "common" area)

Thinking about the run time and space requirements: need to traverse every slot of every polygon. Need to traverse every slot of the bounding array B. Worst case for space is when the intersection of all polygons is empty (and perhaps they are sparsely spaced). Might be worthwhile to check the empty intersection case first... then if the intersection is empty the "common" area is just the sum of the individual areas.

Answer 3

A classical way of computing such an area is to use a sweep algorithm. You can have a look at question Area of overlapping rectangles to get a description of the algorithm in the simpler case of rectangles.

Then you can either decompose your polygons into rectangles, or adapt the sweep algorithm so that this decomposition is done implicitly during the sweep.