Prev: values saved to workspace while using Simulink
Next: plotting multiple functions in same axis, 2D.
From: Tania on 27 Nov 2009 07:47
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
From: Thomas Clark on 27 Nov 2009 17:46
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
From: Thomas Clark on 27 Nov 2009 17:47
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
 | 
Pages: 1
Prev: values saved to workspace while using Simulink
Next: plotting multiple functions in same axis, 2D.