Finding Overlap of polygons in 3D space

Question

I'm trying to find the amount of "overlap" between two (or more) polygons in a 3D space.

The planes all have vector normals pointing in the same direction, so they are guaranteed to be parallel to each other.

The concrete example I can think of is as following:

if arranging playing cards perpendicular to a light source such as the sun, where some may overlap, "What is the total area of the shadow they cast?"

Visual example is given below with two "overlapping" polygons:

overlapping polygons

For instance, if the z-axis is shown vertically, the planes might be stacked something like this:

____________________
     |
     |
     |
_________
     |
     |
_____________

Or viewing the X-Y plane, where - represents areas of overlap which should be counted only once in a final area measurement:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC

Is there an algorithm that can determine the total area "shadow cast" of these polygons? They may not be rectangles, so the data I have to work with will be simply the points of each polygon (and which polygon it belongs to), represented as (x,y,z) digits.

Answer 1

You can use a "scanline" approach. Consider drawing an horizontal line by every vertex. Two successive lines cut trapeziums (trapezia ?) or triangles out of the polygons. If the input polygons are convex, there is never more than one trapezium per slab.

It is a relatively easier matter to check if two trapeziums overlap or not, and if they overlap, what is their union (in the worst case, there are four side/side intersections to be considered).

Depending on your application, you can just compute the areas of the unions, or reconstruct the global polygon. There are classical algorithms to achieve this, but they are difficult. https://en.wikipedia.org/wiki/Vatti_clipping_algorithm