# Find intersecting rectangles from a set of rectangles given query rectangle

4 messages
Open this post in threaded view
|

## Find intersecting rectangles from a set of rectangles given query rectangle

 This post was updated on . 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/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Find intersecting rectangles from a set of rectangles given query rectangle

 You can use this package: https://doc.cgal.org/latest/Box_intersection_d/index.htmlHTH, 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/> -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
 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```