CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

I think for each cell you only need to consider the triangle facet that
is opposite to q in all your intersection queries.

Sebastien.

On 07/28/2014 11:17 AM, Cedric Doucet wrote:
> Hello Sébastien,
>
> thank you very much for your answer.
>
> My problem is the following: given two points p and q, find the cells which 
> are
> 1. incident to q,
> 2. intersected by ray (p,q)
> 3. NOT intersected by segment [p,q].
>
> I do not exactly how to do that efficiently.
>
> My (naive) algorithm is the following:
> 1. create a ray (p,q) and find cells incident to q which are intersected by 
> (p,q)
> 2. create a segment [p,q] and find cells incident to q which are intersected 
> by [p,q]
> 3. compute the topological intersection of sets from 1 and 2.
>
> I managed to find cells which are incident to q using incident_cells function 
> from CGAL.
> I also managed to construct a ray and a segment from p and q.
>
> I now have to find which cells are intersected by (p,q) and not [p,q].
> My naive algorithm consist in
> 1. intersectedCells = std::vector(number of incident cells to q);
> 2. for each incidentCellToQ do
> 3.   for vertexIndex = 0 to 3 do
> 4.     Triangle t = triangle(incidentCellToQ,vertexIndex);
> 5.     if intersection(segment,t).empty() do
> 6.       if ! intersection(segment,t).empty() do
> 7.         intersectedCells.pushback(incidentCellToQ)
> 8.       end if
> 9.     end if
> 10.  end for
> 11. end for
>
> The above algorithm is not very well written (and maybe false) because I have 
> not finished to implement it and test it.
>
> However, I feel that I will compute to many things.
> Having a function to compute intersection between a ray and a cell could be 
> useful here.
>
> Do you think there exist a more simple solution in CGAL?
>
> Best,
>
> Cédric
>
>
>
>
> ----- Mail original -----
> > De: "Sebastien Loriot (GeometryFactory)" 
> > <>
> > À: 
> >
> > Envoyé: Lundi 28 Juillet 2014 10:42:27
> > Objet: Re: [cgal-discuss] Intersection between a ray and a cell
> >
> > It's not clear to me what you are looking for (what you say about nodes
> > confuses me).
> >
> > Is the ray arbitrary and do you want to know all the finite cells
> > intersected by that ray?
> >
> > Sebastien.
> >
> > On 07/28/2014 10:22 AM, cdoucet wrote:
> > > Hello,
> > >
> > > In a 3D Delaunay triangulation, I would like to know which tetraedra
> > > (indicent to the same node) are intersected by a given ray (passing through
> > > this node).
> > >
> > > I found in the documentation that intersections between rays and other
> > > cells
> > > can be computed:
> > > http://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html
> > > However, it does not seem possible to call intersection function for a ray
> > > and a tetrahedron (or a Cell_handle).
> > >
> > > How could I perform such an intersection with CGAL?
> > >
> > > Thank you very much for your help.
> > >
> > > Cédric Doucet
> > > Inria Paris-Rocquencourt
> > >
> > >
> > >
> > > --
> > > View this message in context:
> > > http://cgal-discuss.949826.n4.nabble.com/Intersection-between-a-ray-and-a-cell-tp4659619.html
> > > Sent from the cgal-discuss mailing list archive at Nabble.com.
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://sympa.inria.fr/sympa/info/cgal-discuss