How to calculate total volume of multiple overlapping cuboids

Question

I have a list of Cuboids, defined by their coordinates of their lower-left-back and upper-right-front corners, with edges parallel to the axis. Coordinates are double values. These cuboids are densely packed, will overlap with one or more others, or even fully contain others.

I need to calculate the total volume encompassed by all the given cuboids. Areas which overlap (even multiple times) should be counted exactly once.

For example, the volumes:

1. ((0,0,0) (3,3,3))
2. ((0,1,0) (2,2,4))
3. ((1,0,1) (2,5,2))
4. ((6,6,6) (8,8,8))

The total volume is 27 + 1 + 2 + 8 = 38. Is there an easy way to do this ( in O(n^3) time or better?) ?

Answer 1

How about maintaining a collection of non-intersecting cuboids as each one is processed?

This collection would start empty.

The first cuboid would be added to the collection – it would be the only element, therefore guaranteed not to intersect anything else.

The second and subsequent cuboids would be checked against the elements in the collection. For each new cuboid N, for each element E already in the collection:

• If N is totally contained by E, discard N and resume processing at the next new cuboid.
• If N totally contains E, remove E from the collection and continue testing N against the other elements in the collection.
• If N intersects E, split N into up to five (see comment below) smaller cuboids (depending on how they intersect) representing the volume that does not intersect and continue testing these smaller cuboids against the other elements in the collection.

If we get to the end of the tests against the non-intersecting elements with one or more cuboids generated from N (representing the volume contributed by N that wasn't in any of the previous cuboids) then add them all to the collection and process the next cuboid.

Once all the cuboids have been processed, the total volume will be the sum of the volumes in the collection of non-intersecting cuboids that has been built up.

Answer 2

This can be solved efficiently using a plane-sweep algorithm, that is a straightforward extension of the line-sweep algorithm suggested here for finding the total area of overlapping rectangles.

For each cuboid add it's left and right x-coordinate in an event queue and sort the queue. Now sweep a yz-plane (that has a constant x value) through the cuboids and record the volume between any two successive events in the event queue. We do this by maintaining the list of rectangles that intersect the plane at any stage

As we sweep the plane we encounter two types of events:

(1) We see the beginning of new cuboid that starts intersecting the sweeping plane. In this case a new rectangle intersects the plane, and we update the area of the rectangles intersecting the sweeping plane.

(2) The end of an existing cuboid that was intersecting with the plane. In this case we have to remove the corresponding rectangle from the list of rectangles that are currently intersecting the plane and update the new area of the resulting rectangles.

The volume of the cuboids between any two successive events q_i and q_i+1 is equal to the horizontal distance between the two events times the area of the rectangles intersecting the sweep line at q_i.

By using the O(nlogn) algorithm for computing the area of rectangles as a subroutine, we can obtain an O(n²logn) algorithm for computing the total volume of the cuboids. But there may be a better way of maintaining the rectangles (since we only add or delete a rectangle at any stage) that is more efficient.