# Intersection between Delaunay triangulations

5 messages
Open this post in threaded view
|

## Intersection between Delaunay triangulations

 Hi,       I have 2 triangulations (A and B) and I would like to compute the volume of the intersections between triangulation A and some cells of triangulation B. These intersecting cells are only a few.       The 3 cases are possible:             1 vertex of the cell is inside the triangulation A.             2 vertices of the cell is inside the triangulation A.             3 vertices of the cell is inside the triangulation A.       I'm wondering what would be the best approach:          -- Computing the intersection points to construct new polyhedrons and then calculate their volume?          -- Converting the intersecting cells (and the triangulation A) to Nef_Polyhedrons and then obtain the intersection, which may be converted back to a polyhedron to calculate its volume?          -- Any other option I'm not thinking of?     I started off with the 1st option, but since CGAL::intersection() does not take cells as inputs, and there is the chance that the intersecting cell traverse more than 1 cell of the triangulation A, I started doubting. Any help is appreciated.
Open this post in threaded view
|

## Re: Intersection between Delaunay triangulations

 Hello!   Just one question: are these 2D / surface mesh triangulations, with triangular cells, or 3D triangulations with tetrahedral cells? I've had to do something similar for my work for the 3D triangulations, and ended up using the second option: converting the cells to Nef_Polyhedrons and then obtaining their intersections. This works well, is very easy to code, and is easily adaptable to meshes with hexahedral or mixed cell types, but it's a bit expensive on time. If you already have the list of intersecting cells beforehand, this is not a big problem, though.   For the 2D triangulations, I think that you can use the 2D Nef polygons module to do something similar, but I have no ideas of how to do it for surface meshes.Thiago2016-11-26 4:36 GMT+01:00 pbarletta :Hi,       I have 2 triangulations (A and B) and I would like to compute the volume of the intersections between triangulation *A* and some cells of triangulation *B*. These intersecting cells are only a few.       The 3 cases are possible:             1 vertex of the cell is inside the triangulation *A*.             2 vertices of the cell is inside the triangulation *A*.             3 vertices of the cell is inside the triangulation *A*.       I'm wondering what would be the best approach:          -- Computing the intersection points to construct new polyhedrons and then calculate their volume?          -- Converting the intersecting cells (and the triangulation *A*) to Nef_Polyhedrons and then obtain the intersection, which may be converted back to a polyhedron to calculate its volume?          -- Any other option I'm not thinking of?     I started off with the 1st option, but since CGAL::intersection() does not take cells as inputs, and there is the chance that the intersecting cell traverse more than 1 cell of the triangulation *A*, I started doubting. Any help is appreciated. -- View this message in context: http://cgal-discuss.949826.n4.nabble.com/Intersection-between-Delaunay-triangulations-tp4662395.html Sent from the cgal-discuss mailing list archive at Nabble.com. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Intersection between Delaunay triangulations

 Hi, thanks for the reply. Yes, its 3D, I forgot to mention that.       I don't have the list of intersecting cells, I'd have to iterate over every vertex of every cell of the B triangulation to find out if its outside the  A triangulation, inside of it, or intersecting it; in which case I would then convert to Nef Polyhedron.       I'm dealing with triangulations of (2,000 - 20,000) points. How much time did it take you to perform these volume calculations from the intersections?      Do you think it would be (easier/faster/possible) to just convert both triangulations to Nef Polyhedrons and then calculate their intersection spaces, to then calculate its volume? Regards.