Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Find intersecting rectangles from a set of rectangles given query rectangle

Subject: CGAL users discussion list

List archive

[cgal-discuss] Find intersecting rectangles from a set of rectangles given query rectangle


Chronological Thread 
  • From: vokuheila <>
  • To:
  • Subject: [cgal-discuss] Find intersecting rectangles from a set of rectangles given query rectangle
  • Date: Tue, 23 Oct 2018 18:27:43 -0500 (CDT)
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=SoftFail ; spf=Pass
  • Ironport-phdr: 9a23:vhC6CBYhAFCCcMzGTY6w6ff/LSx+4OfEezUN459isYplN5qZoMy5bnLW6fgltlLVR4KTs6sC17KJ9fi4EUU7or+5+EgYd5JNUxJXwe43pCcHRPC/NEvgMfTxZDY7FskRHHVs/nW8LFQHUJ2mPw6arXK99yMdFQviPgRpOOv1BpTSj8Oq3Oyu5pHfeQpFiCa/bL9oMBm6sRjau9ULj4dlNqs/0AbCrGFSe+RRy2NoJFaTkAj568yt4pNt8Dletuw4+cJYXqr0Y6o3TbpDDDQ7KG81/9HktQPCTQSU+HQRVHgdnwdSDAjE6BH6WYrxsjf/u+Fg1iSWIdH6QLYpUjmk8qxlSgLniD0fOjA38G/ZlM9+gr9Urx29qBJy2JLUbYOJOPZiYq/RYc0WSGxcVchRTSxBBYa8YpMRD+oGPuZYson9qEUPrRu6HwanGeTiyiFPhn/1wK060/ouEQDC3AM6BN8Ov3HUo8/0NKcWS+y60K7IzTDaYv5QxDzz5o/IchU7rvGNW7J9aczRxlM0GAzeilWft5bpMC+S1uQItWWQ8uluVfq3hmI6rwx8piKjy8kvh4XThY8Yy0rI+CR4zYszONa2UlR0YcS+H5tVryyaN5V5QsclQ2xwviY3xacKuZihcycR05snwwDQZ+abfIiP5xLvTOeRITFmi3J5YL+zmhK//Ey6xuDyVcS4ylVHoytfntTNt30BzxnT5dKGSvt58EehwzGP1wXL5+FaJkA0lrfbK54/zb4xkpocq1/OHiDzmErsja+Wcl8o9fSv6+TiernmvIOTN5doigHiNaQjgtCwAesiPQgKRmSU5OW81Kb/8k3kW7VKleY7krLZsZDfPcQUvLS1Aw5T0oY56hawFS2q0NoCnSpPEFUQcx2Oi83lOkrFPevjJfa5mVWl1jlxlN7cObi0HJLOM3jOkbPoNeJj7E1ByAcyydl36JddC7VHK/X2DByi/OfEBwM0ZlTni93sD89wg9tHCDC/R5SBOaaXimemo+cmIu2CfogQ4W+vJP0s5vqohng8ywREIfuZmKAPYXX9JcxIZl2DaCO10NgEGGYO+AE5Sb6y0QDQYXtof3+3GpkEyHQ7BYahVNqRQNzrhrWL1iO2WJZRYzIfBw==
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/

Archive powered by MHonArc 2.6.18.

Top of Page