Common Volume/Intersection Volume between two Delaunay Triangulations

Hello Everyone

I am creating a bunch of 3D Delaunay Triangulations from the different set of points and for any pair of 3D Delaunay Triangulations, I need to calculate the volume which is common to both 3D Delaunay Triangulations. There are number of pairs which share volume and I need to calculate the values of these shared volumes.

Does anyone have a quick and nice method to calculate this ?

Answer 1

[Teja Muppirala]

Sounds like a difficult problem to do exactly/analytically. I think you can get a very good approximation using a much simpler method.

1. Make a regular 3d grid of points using NDGRID that spans the box containing both of your triangulations.

2. For each point in the 3d grid, see if it is inside both triangulations. (The file exchange has fast algorithms for testing this)

3. Count the number of points from step 2, divide by the total number of points in the grid, and scale it by the volume of the box.

4. Go back to #1, increase the number of points, repeat until you verify convergence.

You could also use random numbers instead of a regular grid.

Answer 2

[Mathematical Science]

Thanks for the message.

I had been doing this rather the crude way. I am generating more than 5000 random points [RANDOM! so points are obviously not evenly distributed inside the Delaunay Triangulation] inside my Delaunay Triangulations and hoping that this would generate enough number of points so that I could find out points common to both the volumes and then create a Delaunay Triangulation of these common points and gets it volume from creating a Convex Hull of it.

This is crude ...very crude and it is incredibly slow. I was hoping to get some insights about solving this mathematically.

But I could also do with another solution which is to generate a small number of points inside the Delaunay and but that they should be very evenly and uniformly distributed in the Delaunay Triangulation, this would ensure that I do not loose a lot on the common volume because of the sparse nature of the distribution of points.

Is there any method where I can create say for example 500 uniformly distributed points inside the Delaunay Triangulation ? I think TriScatteredInterp can do that but I am confused about its exact usage.