Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Intersection between a ray and a cell

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Intersection between a ray and a cell


Chronological Thread 
  • From: Cedric Doucet <>
  • To:
  • Subject: Re: [cgal-discuss] Intersection between a ray and a cell
  • Date: Mon, 28 Jul 2014 13:01:02 +0200 (CEST)


Thank you very much!

I am sorry I have a last question about intersection.
Return types are defined in a table at
http://doc.cgal.org/latest/Kernel_23/group__intersection__linear__grp.html.

But what is the return type when two objects do not intersect?
How can we test if two objects intersect from the return type?

Cédric

----- Mail original -----
> De: "Sebastien Loriot (GeometryFactory)"
> <>
> À:
>
> Envoyé: Lundi 28 Juillet 2014 11:52:13
> Objet: Re: [cgal-discuss] Intersection between a ray and a cell
>
> On 07/28/2014 11:50 AM, Cedric Doucet wrote:
> >
> >
> > Good! That's the case for me!
> > Is there a CGAL function which returns the opposite facet to a given
> > vertex
> > in a cell?
> >
>
> cell->index(v) gives you the index of the vertex_handle v in cell.
>
> Sebastien.
>
> > Have a good day,
> >
> > Cédric
> >
> >
> > ----- Mail original -----
> >> De: "Sebastien Loriot (GeometryFactory)"
> >> <>
> >> À:
> >>
> >> Envoyé: Lundi 28 Juillet 2014 11:35:01
> >> Objet: Re: [cgal-discuss] Intersection between a ray and a cell
> >>
> >> On 07/28/2014 11:30 AM, cdoucet wrote:
> >>>
> >>> Thank you, that's a good idea!
> >>> Do you think it will work even in special cases, such as as when the ray
> >>> lies inside a facet shared by two of incident cells to q?
> >>>
> >> If you have exact predicates yes, the ray go through the edge shared by
> >> two facets.
> >>
> >> Sebastien.
> >>
> >>> Best,
> >>>
> >>> Cédric
> >>>
> >>>
> >>> ------------------------------------------------------------------------
> >>>
> >>> *De: *"Sebastien Loriot (GeometryFactory) [via cgal-discuss]"
> >>> <[hidden email] </user/SendEmail.jtp?type=node&node=4659624&i=0>>
> >>> *À: *"cdoucet" <[hidden email]
> >>> </user/SendEmail.jtp?type=node&node=4659624&i=1>>
> >>> *Envoyé: *Lundi 28 Juillet 2014 11:26:01
> >>> *Objet: *Re: Intersection between a ray and a cell
> >>>
> >>> 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)" <[hidden email]
> >>> </user/SendEmail.jtp?type=node&node=4659623&i=0>>
> >>> >> À: [hidden email]
> >>> >> </user/SendEmail.jtp?type=node&node=4659623&i=1>
> >>> >> 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
> >>> >>
> >>> >>
> >>> >>
> >>> >
> >>>
> >>> --
> >>> You are currently subscribed to cgal-discuss.
> >>> To unsubscribe or access the archives, go to
> >>> https://sympa.inria.fr/sympa/info/cgal-discuss
> >>>
> >>>
> >>>
> >>>
> >>>
> >>> ------------------------------------------------------------------------
> >>> If you reply to this email, your message will be added to the
> >>> discussion below:
> >>>
> >>> http://cgal-discuss.949826.n4.nabble.com/Intersection-between-a-ray-and-a-cell-tp4659619p4659623.html
> >>>
> >>> To unsubscribe from Intersection between a ray and a cell, click
> >>> here.
> >>> NAML
> >>>
> >>> <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
> >>>
> >>>
> >>>
> >>>
> >>> ------------------------------------------------------------------------
> >>> View this message in context: Re: Intersection between a ray and a cell
> >>> <http://cgal-discuss.949826.n4.nabble.com/Intersection-between-a-ray-and-a-cell-tp4659619p4659624.html>
> >>> Sent from the cgal-discuss mailing list archive
> >>> <http://cgal-discuss.949826.n4.nabble.com/> 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
> >>
> >>
> >>
> >
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>
>



Archive powered by MHonArc 2.6.18.

Top of Page