Subject: CGAL users discussion list
List archive
- From: Cedric Doucet <>
- To:
- Subject: Re: [cgal-discuss] Intersection between a ray and a cell
- Date: Mon, 28 Jul 2014 11:17:02 +0200 (CEST)
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
>
>
>
- [cgal-discuss] Intersection between a ray and a cell, cdoucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, cdoucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, cdoucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Cedric Doucet, 07/28/2014
- Re: [cgal-discuss] Intersection between a ray and a cell, Sebastien Loriot (GeometryFactory), 07/28/2014
Archive powered by MHonArc 2.6.18.