Caseless way of calculating volume of an intersection between an array and a square in multiple dimensions

Question

I have a multidimensional array and while iterating through its every element, I need to calculate the volume of the square, cube, or other respective objects in case of dimensions higher than 3, in each element, the size of 2r. If I'm iterating through elements near the boundaries of the array, part of that square/cube is going to stick outside the array - and I need the volume of the intersection between the array and the object.

This is how the problem looks in 2D - I need to calculate the red area.

I know two ways so far of doing that:

1. Cases and if-statements. For 2D, I could calculate the coordinates of the corners of the intersection, but since this isn't strictly a 2D problem, but a multidimensional one, where the number of dimensions is given on input, cases and if-statements and subsequent hardcoding are out of question.
2. Manually iterating through every element in the square and checking if it belongs to the array. While this is easy to do, it is also incredibly slow, even in 2D, because I'm iterating through an n-dimensional array, and in each iteration, I'm again doing n loops the size of 2r^n. Bigger the radius, slower the execution.

Is there any way that would allow me to calculate the volume of those intersections fast?

Answer 1

If I understand your question correctly, you want to calculate the intersection volume between two axis-aligned hyperrectangles.

The first rectangle (your array) is defined by the position of its lower corner (arrayLower, an nD vector) and its size (arraySize, again an nD vector). The second rectangle is defined by its center (p, an nD vector) and an extent of r units in each direction.

For given dimensionality d, this can be done in a very structured way since you only have to multiply the extents in each dimension:

volume = 1
for each d:
    lower = max(p[d] - r, arrayLower[d])
    upper = min(p[d] + r, arrayLower[d] + arraySize[d])
    if(lower > upper)
        volume = 0   //no intersection
    else
        volume *= upper - lower