CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 07/11/2012 10:25 AM, Benjamin SCHWARZ wrote:
> Hello Sebastien, and thanks for the answer
>
>       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 take the cell of the facet (facet.first).

>       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.
Then, I think you just need to check whether the edge is singular (if 
the edge is in the 0-complex).

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