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






Archive powered by MHonArc 2.6.18.

Top of Page