convex hull intersection volume
Sven Van Poucke
I am looking for a way to calculate the volume of the intersection
between two convhulln generated spaces (from which the volumes have
already been calculated). As a novice in matlab, I can not find the
right approach.
Hoping someone is able to help me.
Good luck in 2007!
Sven Van Poucke, MD
John D'Errico
I did write some code for this, but its
not available for distribution, and its
not even remotely fast in 3d or above.
I'll describe the alternatives (that I
know of) though.
An "exact" solution uses another tool
that I wrote, a truncation operator.
Given a tessellation of one domain, it
can "slice" off that part which remains
on one side of a plane in that space.
Since a convex set can be represented
using a list of planar (linear)
inequalities, simply repeat this step
until done. (I don't know if I explained
this well, but it works, and is exact.
It can even be made to work for more
more general, non-convex regions.)
The alternative is to generate many
randomly sampled points from the
surface of each convex domain. Then
test to see if the points from set1
lie inside hull2 and if the points
from set2 lie inside hull1. Keep ALL
of the points which lie inside both
convex hulls. Form the convex hull
of that list of points. It will be
a reasonable approximation to the
exact solution I described above,
although much depends on the size
of these random samples. There are
some tricks that can be applied to
improve this scheme of course.
If you wish, I can probably put the
second option together relatively
quickly.
HTH,
John D'Errico
Michael Garrity
news:ef498...@webcrossing.raydaftYaTP...
Because both of your volumes are convex, there is an approach
that is theoretically pretty simple.
The Sutherland-Hodgman clipping algorithm is really easy to
implement. It can clip a polygon against a plane. Once you've
implemented this, use it to clip each of the polygons in one hull against
each of the planes defined by the polygons in the second volume. Keep
the portions of the polygons that are on the inside of each plane. Now
do the same thing with the polygons of the second hull and the planes
defined by the polygons of the first hull. The union of the two sets of
polygons is the intersection of the two hulls.
However, you should note that I said "theoretically". In practice you're
going to have problems whenever a polygon in one hull is nearly coplanar
with a polygon in the other hull. A solution that is robust in the presence
of this sort of input is quite a bit hairier.
Still worth reading up on Sutherland-Hodgman though. It might provide
some useful insight.
-Mike Garrity
Tania
I am new to matlab and I would like to know how can I in matlab deal with the union and intersection of a convex hulls or meshes?
Thank you.
Regards,
Tania
Thomas Clark
If you have R2009a or later, you have access to the DelaunayTri routine and it's associates. You can do the following with earlier versions of MATLAB them, its just a little more involved / computationally intensive.
So, what I would do:
- Build a delaunay triangulation DT1 of the points (x1, y1, z1) from your first volume.
- Build a second delaunay triangulation, DT2 of the points (x2, y2, z2) which make up your second volume.
- Use TriScatteredInterp (which usefully returns NaN where points are outside the hull) or some other method (there might be a dedicated one for this) to determine whether each point (x2, y2, z2) is inside or outside the convex hull DT1.
- Same again to determine whether each point (x1, y1, z1) is inside or outside the convex hull of DT2.
- Take all points (x1 y1 z1) which lie inside (or on) the convex hull of DT2 and group them with all points in (x2 y2 z2) which lie inside or on the convex hull DT1.
- This list comprises all points which make up the intersecting volume. Compute its convex hull, from which you can determine volume fairly easily.
** NOTE **
This method is a good approximation, unless data are very coarsely spaced. It isn't exact unless points on one or other of DT2 or DT1 lie exactly on the line of volume intersection.
To make it exact, if necessary, take the triangular simplices which make the convex hulls of DT1 and DT2, determine which simplices from CHDT1 cross through simplices from CHDT2. Where they cross, solve for the intersection points, giving you a series of points around the border of the intersection. Then add these into the final list above before computing the convex hull of the intersecting volumes.
Note that this method may become confusing if there is more than one 'borderline' of intersection - which can occur where the volumes are a different shape (e.g. one convex hull is a long ellipse, the other is a sphere whose diameter is between the major and minor lengths of the ellipsoid).
Hope this helps
Tom Clark
Thomas Clark
Mathematical Science
"Thomas Clark" wrote in message <hepkrb$2th$1...@fred.mathworks.com>...
I am perhaps taking you to very old question here. 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.
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
Does anyone have a quick and nice method to calculate this ?