CGAL users discussion list

[Mariette Yvinec <>]

Hi Benjamin

I think we don't have in Triangulation_3 the kind of line-walk you are looking for.
In fact, for location we are using a zig-zag walk that
is more efficient and avoid
dealing with special cases where the line goes through a vertex of the triangulation
or intersect an edge.

Mariette

Le 11/07/12 10:25, Benjamin SCHWARZ a écrit :

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.

     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.

         --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

-- 
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis