CGAL users discussion list

[Andreas Fabri <>]

On 24/03/2016 13:19, Olivier Devillers wrote:
> On 24 Mar 2016, at 12:33, Pol Monsó Purtí Helimap 
> <
> <mailto:>>
>  wrote:
>
> > Hello all,
> >
> > How can I intersect a 3d ray with a 2D Constrained Delaunay
> > Triangulation created from 3d points using the project_xy traits?
> >
> > I've seen this post:
> > http://cgal-discuss.949826.n4.nabble.com/Intersection-segment-and-cells-from-3D-Delaunay-triangulation-td4660891.html
> >
> > But I don't understand andreas for the second approach.
> >
> > I don't have that many queries, around 200 of them. I might have,
> > however, lots of points, > 200 milion.
> >
> > Is it worth it to build a tree? what other approach could I follow?
> > Iterating over all the faces seems highly inefficient.
>
> for one ray, you could iterate on the faces intersecting the ray in
> projection using the line-face-circulator.

Look for
Line Face Circulator
http://doc.cgal.org/4.8/Triangulation_2/classCGAL_1_1Triangulation__2.html#ad720b1a9adc835ed1a27c228eea1e36c

It might still be a rather expensive operation, namely when
you only intersect very few triangles close to mountain peaks,
but traverse all the triangles in the vertical projection
(~sqrt(200 mio)).

Give the AABB tree a try. It will take you an hour to implement.


--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri