Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
convex hull intersection volume

Subject: convex hull intersection volume

From: Sven Van Poucke

Date: 27 Dec, 2006 03:17:01

Message: 1 of 7

LS,

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

Subject: convex hull intersection volume

From: John D'Errico

Date: 27 Dec, 2006 05:53:46

Message: 2 of 7

Sven Van Poucke wrote:
>
>
> LS,
>
> 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

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

Subject: convex hull intersection volume

From: Michael Garrity

Date: 27 Dec, 2006 15:55:10

Message: 3 of 7

"Sven Van Poucke" <svanpoucke@zeelandnet.nl> wrote in message
news:ef4981d.-1@webcrossing.raydaftYaTP...
> LS,
>
> 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

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

Subject: convex hull intersection volume

From: Tania

Date: 27 Nov, 2009 12:47:04

Message: 4 of 7

Hi!

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

Subject: convex hull intersection volume

From: Thomas Clark

Date: 27 Nov, 2009 22:46:03

Message: 5 of 7

Rely on the geometrical precept that, if two volumes are convex, their intersecting volume (if they intersect) must also be convex.

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

Subject: convex hull intersection volume

From: Thomas Clark

Date: 27 Nov, 2009 22:47:00

Message: 6 of 7

Rely on the geometrical precept that, if two volumes are convex, their intersecting volume (if they intersect) must also be convex.

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

Subject: convex hull intersection volume

From: Mathematical Science

Date: 22 Feb, 2013 16:51:06

Message: 7 of 7



"Thomas Clark" wrote in message <hepkrb$2th$1@fred.mathworks.com>...
> Rely on the geometrical precept that, if two volumes are convex, their intersecting volume (if they intersect) must also be convex.
>
> 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
>


Hello Mr. Thomas

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 ?

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us