CGAL users discussion list

[Andreas Fabri <>]

You can also use the Segment Trees

https://doc.cgal.org/latest/SearchStructures/index.html#secsegment_trees

They have a poly logarithmic query time, but the constants in the  O() are rather high.

Best,

Andreas

On 10/24/2018 8:59 AM, Sebastien Loriot (GeometryFactory) wrote:

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

HTH,

Sebastien.

On 10/24/2018 01:27 AM, vokuheila wrote:

Hi CGAL discuss!

I have a task on hand: Given a set of axis-aligned 2D rectangles and a query
axis-aligned 2D rectangle, efficiently (better than O(n)) *find the subset
of rectangles that intersect the query rectangle*.

Is there some data structure in CGAL that can help with this? I looked over
the documentation and it seems that most of the search/indexing structures
work with *point sets* and not more general shapes.

I heard there is *R-tree* that can do this kind of polygon indexing for fast
intersection queries. Does CGAL have something like that or equivalent? Or
is some other approach available?

Thanks guys!!

Duane



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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

phone: +33.492.954.912    skype: andreas.fabri