Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices


Chronological Thread 
  • From: Benjamin SCHWARZ <>
  • To:
  • Subject: Re: [cgal-discuss] Triangulation_3 : collecting all simplices joining two distant vertices
  • Date: Wed, 11 Jul 2012 10:25:56 +0200

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




Archive powered by MHonArc 2.6.18.

Top of Page