CGAL users discussion list

[Cedric Doucet <>]

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