KiCad PCB EDA Suite
view_rtree.h
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2013 CERN
5 * Copyright (C) 2020 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
27#ifndef __VIEW_RTREE_H
28#define __VIEW_RTREE_H
29
30#include <math/box2.h>
31
32#include <geometry/rtree.h>
33
34namespace KIGFX
35{
36typedef RTree<VIEW_ITEM*, int, 2, double> VIEW_RTREE_BASE;
37
42{
43public:
49 void Insert( VIEW_ITEM* aItem )
50 {
51 const BOX2I& bbox = aItem->ViewBBox();
52 const int mmin[2] = { bbox.GetX(), bbox.GetY() };
53 const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
54
55 VIEW_RTREE_BASE::Insert( mmin, mmax, aItem );
56 }
57
63 void Remove( VIEW_ITEM* aItem )
64 {
65 // const BOX2I& bbox = aItem->ViewBBox();
66
67 // FIXME: use cached bbox or ptr_map to speed up pointer <-> node lookups.
68 const int mmin[2] = { INT_MIN, INT_MIN };
69 const int mmax[2] = { INT_MAX, INT_MAX };
70
71 VIEW_RTREE_BASE::Remove( mmin, mmax, aItem );
72 }
73
78 template <class Visitor>
79 void Query( const BOX2I& aBounds, Visitor& aVisitor ) const
80 {
81 int mmin[2] = { aBounds.GetX(), aBounds.GetY() };
82 int mmax[2] = { aBounds.GetRight(), aBounds.GetBottom() };
83
84 // We frequently use the maximum bounding box to recache all items
85 // or for any item that overflows the integer width limits of BBOX2I
86 // in this case, we search the full rtree whose bounds are absolute
87 // coordinates rather than relative
88 BOX2I max_box;
89 max_box.SetMaximum();
90
91 if( aBounds == max_box )
92 {
93 mmin[0] = mmin[1] = INT_MIN;
94 mmax[0] = mmax[1] = INT_MAX;
95 }
96
97 VIEW_RTREE_BASE::Search( mmin, mmax, aVisitor );
98 }
99
100private:
101};
102} // namespace KIGFX
103
104#endif
void SetMaximum()
Definition: box2.h:57
coord_type GetY() const
Definition: box2.h:174
coord_type GetX() const
Definition: box2.h:173
coord_type GetRight() const
Definition: box2.h:182
coord_type GetBottom() const
Definition: box2.h:183
An abstract base class for deriving all objects that can be added to a VIEW.
Definition: view_item.h:77
virtual const BOX2I ViewBBox() const =0
Return the bounding box of the item covering all its layers.
Implement an non-owning R-tree for fast spatial indexing of VIEW items.
Definition: view_rtree.h:42
void Insert(VIEW_ITEM *aItem)
Insert an item into the tree.
Definition: view_rtree.h:49
void Remove(VIEW_ITEM *aItem)
Remove an item from the tree.
Definition: view_rtree.h:63
void Query(const BOX2I &aBounds, Visitor &aVisitor) const
Execute a function object aVisitor for each item whose bounding box intersects with aBounds.
Definition: view_rtree.h:79
The Cairo implementation of the graphics abstraction layer.
Definition: color4d.cpp:243
RTree< VIEW_ITEM *, int, 2, double > VIEW_RTREE_BASE
Definition: view_rtree.h:36