CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 07/28/2014 01:01 PM, Cedric Doucet wrote:
> 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?
return type is a boost::optional< boost:variant<..> > which can be 
evaluated to bool.

Sebastien.

> 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