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 <tomasz.wlostowski@cern.ch>
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 
34 namespace KIGFX
35 {
36 typedef RTree<VIEW_ITEM*, int, 2, double> VIEW_RTREE_BASE;
37 
42 {
43 public:
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 
100 private:
101 };
102 } // namespace KIGFX
103 
104 #endif
The Cairo implementation of the graphics abstraction layer.
Definition: color4d.cpp:236
coord_type GetX() const
Definition: box2.h:173
coord_type GetRight() const
Definition: box2.h:182
void Remove(VIEW_ITEM *aItem)
Remove an item from the tree.
Definition: view_rtree.h:63
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:81
void Insert(VIEW_ITEM *aItem)
Insert an item into the tree.
Definition: view_rtree.h:49
void SetMaximum()
Definition: box2.h:57
Implement an non-owning R-tree for fast spatial indexing of VIEW items.
Definition: view_rtree.h:41
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
coord_type GetY() const
Definition: box2.h:174
RTree< VIEW_ITEM *, int, 2, double > VIEW_RTREE_BASE
Definition: view_rtree.h:36
virtual const BOX2I ViewBBox() const =0
Return the bounding box of the item covering all its layers.