How can I calculate the intersection hypervolume of two N-dimensional regions, given their defining coordinates?

Question

I'm storing hyper-regions as vectors in an SQL table like so:

region1: D1, D1', D2, D2', D3, D3'...DN, DN'
region2: D1, D1', D2, D2', D3, D3'...DN, DN'

It's relatively easy to find regions that are non-intersecting, or entirely overlap. (select from regions where D1 > foo, D2 < bar, etc). How can I determine the volume of intersection, in SQL, between two regions?

In three dimensions the calculation would look something like the following:

r1: X:0, X':2, Y:0, Y':2, Z:0, Z':2
r2: X:1, X':3, Y:1, Y':3, Z:0, Z':2

SELECT (mathmagic)

result: 2 (I have defined 2 cubes, 2x2x2, but the second cube is shifted 1 unit on both x and y axes, so the overlap is a 2x1 area)

Edit: A general formula would be fine too, doesn't have to be in SQL.

Answer 1

I think the answer can be constructed as follows (pseudocode). Each dimension has its own intersection, and the volume is simply the product of all intersections. If there is no overlap in a particular dimension, then the volume will be 0.

The intersection of a 1D region with another can have 2 cases:

1) no overlap at all, answer = 0

2) some overlap, answer = as follows:

If there is some overlap, then take the 4 points involved in the intersection and sort them and take the inner-most pair of 2, which will be the min and max of the intersection.

intersect(amin,amax,bmin,bmax):
   if (amin < bmax && amax > bmin)
     l = sort(amin,amax,bmin,bmax)
     return l[3] - l[2]  //  [1] is first element, R notation)
   else:
     return 0

v = 1
foreach n in 1,2,3...N:
  d = intersect( region0.Dn, region0.Dn',  region1.Dn, region1.Dn')
  v *= d