Find intersecting rectangles from a set of rectangles given query rectangle

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Find intersecting rectangles from a set of rectangles given query rectangle

vokuheila
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


Reply | Threaded
Open this post in threaded view
|

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

Sebastien Loriot (GeometryFactory)
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/
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

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

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
Reply | Threaded
Open this post in threaded view
|

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

vokuheila
Thanks for the suggestions Andreas and Sebastien! I will try them.



--
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