CGAL users discussion list

[Sebastien Loriot <>]

You can also use this package:
https://doc.cgal.org/latest/Interval_skip_list/index.html

to filter out segments that are relevant for the ray shooting instead
of using the AABB-tree.

Andreas did use that for the code shipped in 
https://github.com/CGAL/cgal/pull/6377, but for some reason the code is 
not in the
PR (missing git add?)

Best,

Sebastien.

On 6/14/22 17:50, Andrew Cunningham wrote:
> Hi,
> I had to deal with a similar issue. I treated this as a 3D ray tracing 
> problem as the technique is very robust.
>
> - triangulate the polygons ( remembering which polygon the triangles 
> belong to)
> - Add the triangles to a 3D AABB tree with z=0
> - shoot a ray from say z=1 in the direction 0,0,-1 using x,y of your 
> query point
> - first_intersection() will return the triangle
>
> https://doc.cgal.org/latest/AABB_tree/index.html#aabb_ray_shooting 
> <https://doc.cgal.org/latest/AABB_tree/index.html#aabb_ray_shooting>
>
> If this is a performance critical application you could use embree ( 
> open source, very high performance ray tracer) instead of CGAL for 
> raytracing. Also if you can search multiple points in parallel then it's 
> a trivially parallel problem for which you can use, say, OpenMP
>
> Andrew
> > On Jun 10, 2022, at 1:04 PM, Renato Silveira < 
> > <>> wrote:
> >
> > 
> > Dear all,
> >
> > I need to query if a point is inside any polygon from a list of many 
> > polygons. Is there a spatial search tree that speeds up this process?
> >
> > Thanks for any insight
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://sympa.inria.fr/sympa/info/cgal-discuss 
> > <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