Skip to Content.
Sympa Menu

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

Subject: CGAL users discussion list

List archive

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


Chronological Thread 
  • From: "Sebastien Loriot (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] Find intersecting rectangles from a set of rectangles given query rectangle
  • Date: Wed, 24 Oct 2018 08:59:45 +0200
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-phdr: 9a23:7xhVFxEpo7n//KLPMs3rqJ1GYnF86YWxBRYc798ds5kLTJ7zocmwAkXT6L1XgUPTWs2DsrQY07WQ6/iocFdDyK7JiGoFfp1IWk1NouQttCtkPvS4D1bmJuXhdS0wEZcKflZk+3amLRodQ56mNBXdrXKo8DEdBAj0OxZrKeTpAI7SiNm82/yv95HJbAhEmDiwbaluIBmqsA7cqtQYjYx+J6gr1xDHuGFIe+NYxWNpIVKcgRPx7dqu8ZBg7ipdpesv+9ZPXqvmcas4S6dYDCk9PGAu+MLrrxjDQhCR6XYaT24bjwBHAwnB7BH9Q5fxri73vfdz1SWGIcH7S60/VDK/5KlpVRDokj8KOSMn/mHZisJ+j6xVrxyuqBN934Hab5qYNOZ8c67HYd8WWWRMU8RXWidcAo28dYwPD+8ZMOpWsofyuUABogGlBQmwBePg1DlIjWLw0609yeQhEAbG3BA9FN4KsXrbstL1NKIMXuCp1qnJzTXNYOlK1jfh74jIaBAgrfSCUbltdsfR0k0vFwTfjlWRrozlIymZ1uEJs2WA4OpgUPigi28jqw1rvjevwcIsh5DPi4kIxF7E8iB5z5w0Jd2+UEN7Z8SrH4BLuCGeKYR6WN8tQ2ZtuCoi1rIGtoS0fCwQxJQg3R7fZPqKeJWL7BL7TOudPyt0iXZ/dL+8hxu+61WsxvP/W8Wu31tHrDJJn9vPu3wXyRDe5cmKRuFg8kql1zuDzQLe5+FCLEspj6TUMYQhzaQ1lpcLsUTMACv2mELuga+TbEok++yo5/3pY7Xju5OQLoF0hw78P6g0lcy/BuM4MgcKX2eF4+izyLrj/UjhTLVLiP05jLXZvYjEKcgHoqO1GQxY34Y55xqiETur084UkHYFIV5dfRKIlYnpO1XAIPDiCve/hkyhkCxvx/DBJL3hA5LNLmTZnLfkebZw8EFcyA8pwtBe45JYEK0OIPX2WkPprtzXEgc5MxCow+bgENhyyoweVniLAqOALazSsESI6f4yI+mXf48Yoy39Kvgg5/72l3A1g14dfa+z3ZsWcn+0BPpmI1/KKUbr19wOGGNPsgslR/Hxk3WDVyRSbjC8RfES/DY+XcidAI3KXZysjbrJ+CChH5pKLiBpB1eJHGvyZquNUOsLcjPTaIc1iTgDT7mmV8kk0TmhsQb7z/xsKe+CqX5Qjo7qyNUgv76brho17zEhV53MgVHIdHl9myYzfxFz2al+pUJnzVLaiPp3hvVZEZpY4PYbC15mZ66Z9PRzDpXJYiyEZs2AEQ/0TdCvADV3RdU0kYdXPhRNXu66hxWG5BKERr8Yk7vRWc4x+6PYmmf0foNzlymA264mgF0rBMBIMD/+iw==
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/


Archive powered by MHonArc 2.6.18.

Top of Page