Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices
Chronological Thread
- From: "Sebastien Loriot (GeometryFactory)" <>
- To:
- Subject: Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices
- Date: Wed, 11 Jul 2012 10:31:34 +0200
On 07/11/2012 10:25 AM, Benjamin SCHWARZ wrote:
Hello Sebastien, and thanks for the answerThen take the cell of the facet (facet.first).
Basically, I am more interested in the set of cells that are
intersected by the segment joining two distant vertices v1 and v2 of the
triangulation T.
Then, I think you just need to check whether the edge is singular (if the edge is in the 0-complex).
I can imagine how to code something using functions such as the one you
suggested, probably with special cases to handle (when the segment is embeded
in the plan of a facet that it crosses, or when it crosses an edge). Now, I
have the feeling my problematics might have already been addressed in CGAL
and I wanted to know if there is already some code at hand.
As far as I know when one builds a Delaunay triangulation by iterative
insertion of points, one of the steps consists in finding the existing cell C
of T that contains the point to insert P. This step is achieved by choosing a
random cell C0 in T, and walk through the triangulation, crossing a
succession of cells Ci, towards P, until C is found... Which resembles a lot
to the task I want to achieve.
Maybe I should precise my motivation : I work with an Alpha_Shape_3, and I want to
decide wether the segment S joining two vertices of the dual shape (alpha=0) is totally
outside the shape or if it intersects it, which I wanted to assess by probing the
"classification" (INTERIOR or EXTERIOR) of the cells crossed by S.
Sebastien.
--Ben
Le 11 juil. 2012 à 09:00, Sebastien Loriot (GeometryFactory) a écrit :
Hi Ben,
If I understand your question correctly, you need to do:
Cell_handle c;
int i,j;
T.is_edge(v1,v2,c,i,j);
Facet_circulator fcirc=t.incident_facets(c,i,j);
See
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3_ref/Class_Triangulation_3.html
for the details.
Sebastien.
On 07/10/2012 11:56 AM, Benjamin SCHWARZ wrote:
Hi list,
Given a Regular_triangulation_3 T, and two vertices v1 and v2 of T,
I'd like to be able to visit all simplices on the segment joining v1 to v2.
I can imagine a recursive algorithm progressing from simplex to simplex,
each time tracing the next intersection of the beam through the surrounding
simplices. I have the feeling this is a common problematics, related with the
construction of a Delaunay triangulation, hence I'd like to know if there is
already some code to do that.
--Ben
- [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Benjamin SCHWARZ, 07/10/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Sebastien Loriot (GeometryFactory), 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Benjamin SCHWARZ, 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Sebastien Loriot (GeometryFactory), 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Mariette Yvinec, 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Benjamin SCHWARZ, 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Benjamin SCHWARZ, 07/11/2012
- Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices, Sebastien Loriot (GeometryFactory), 07/11/2012
Archive powered by MHonArc 2.6.18.