CGAL users discussion list

[Andreas Fabri <>]

Let me add my 10 cents for yet more alternatives.

You can put the polygons in a constrained triangulation and mark all triangular faces which are inside a polygon.
You then perform a hilbert_sort on your points, and  perform the point location of the triangulation,
and for the i-th point you give the location of the (i-1)-th point as hint to accelerate the traversal.

In case you know all polygons and all points at the beginning, a plane sweep should do it,
that is there should be no need for an arrangement or triangulation.    A point event of the
sweep should be able to determine if on the sweepline you are inside or outside.
This does not exist out of the box though.

Best,

Andreas

On 6/14/2022 5:50 PM, 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

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

        -- 
        You are currently subscribed to cgal-discuss.
        To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        
      
    
-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project