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

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.

Answer 2

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 3

I recently had the same problem and found the following approach easy to implement and working for n dimensions.

First build a grid and then check for each cell in the grid whether it overlaps with a cuboid or not. The volume of overlapping cuboids is the sum of the volumes for those cells which are included in one or more cuboids.

• Describe your cuboids with their min/max value for each dimension.
• For each dimension store min/max values of each cuboid in an array. Sort this array and remove duplicates.
• Now you have grid points of a non-equidistant grid. Each cell of the grid is either completely inside one or more cuboids or not.
• Iterate over the grid cells and count the volume for those cells which overlap with one or more cuboids.

You can get all grid cells by using the Cartesian Product.

Answer 4

I tried the cellular approach suggested by @ccssmnn; it worked but was way too slow. The problem is that the size of the array used for "For each dimension store min/max values of each cuboid in an array." is O(n), so the number of cells (hence, the execution time) is n^d, e.g., n^3 for three dimensions.

Next, I tried a nested sweep-line algorithm, as suggested by @krjampani; much faster but still too slow. I believe the complexity is n^2*log^3(n).

So now, I'm wondering if there's any recourse. I've read several postings that mention the use of interval trees or augmented interval trees; might this approach have better complexity, e.g., n*log^3(n)?

Also, I'm trying to get my head around what would be the augmenting value in this case? In the case of point or range queries, I can see sorting the cuboids by their (xlo,ylo,zlo) and using max(xhi,yhi,zhi) for each subtree as the augmenting value, but can't figure out how to extend this to keep track of the union of the cuboids and its volume.