KiCad PCB EDA Suite
sch_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) 2019-2021 KiCad Developers, see AUTHORS.txt for contributors.
5 * Copyright (C) 2020 CERN
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 3
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-3.0.html
20 * or you may search the http://www.gnu.org website for the version 3 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
25#ifndef EESCHEMA_SCH_RTREE_H_
26#define EESCHEMA_SCH_RTREE_H_
27
28#include <core/typeinfo.h>
29#include <sch_item.h>
30#include <set>
31#include <vector>
32
33#include <geometry/rtree.h>
34
40{
41private:
42 using ee_rtree = RTree<SCH_ITEM*, int, 3, double>;
43
44public:
46 {
47 this->m_tree = new ee_rtree();
48 m_count = 0;
49 }
50
52 {
53 delete this->m_tree;
54 }
55
59 void insert( SCH_ITEM* aItem )
60 {
61 BOX2I bbox = aItem->GetBoundingBox();
62
63 // Inflate a bit for safety, selection shadows, etc.
64 bbox.Inflate( aItem->GetPenWidth() );
65
66 const int type = int( aItem->Type() );
67 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
68 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
69
70 m_tree->Insert( mmin, mmax, aItem );
71 m_count++;
72 }
73
78 bool remove( SCH_ITEM* aItem )
79 {
80 // First, attempt to remove the item using its given BBox
81 BOX2I bbox = aItem->GetBoundingBox();
82
83 // Inflate a bit for safety, selection shadows, etc.
84 bbox.Inflate( aItem->GetPenWidth() );
85
86 const int type = int( aItem->Type() );
87 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
88 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
89
90 // If we are not successful ( true == not found ), then we expand
91 // the search to the full tree
92 if( m_tree->Remove( mmin, mmax, aItem ) )
93 {
94 // N.B. We must search the whole tree for the pointer to remove
95 // because the item may have been moved before we have the chance to
96 // delete it from the tree
97 const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
98 const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
99
100 if( m_tree->Remove( mmin2, mmax2, aItem ) )
101 return false;
102 }
103
104 m_count--;
105 return true;
106 }
107
111 void clear()
112 {
113 m_tree->RemoveAll();
114 m_count = 0;
115 }
116
125 bool contains( const SCH_ITEM* aItem, bool aRobust = false ) const
126 {
127 BOX2I bbox = aItem->GetBoundingBox();
128
129 // Inflate a bit for safety, selection shadows, etc.
130 bbox.Inflate( aItem->GetPenWidth() );
131
132 const int type = int( aItem->Type() );
133 const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
134 const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
135 bool found = false;
136
137 auto search =
138 [&found, &aItem]( const SCH_ITEM* aSearchItem )
139 {
140 if( aSearchItem == aItem )
141 {
142 found = true;
143 return false;
144 }
145
146 return true;
147 };
148
149 m_tree->Search( mmin, mmax, search );
150
151 if( !found && aRobust )
152 {
153 // N.B. We must search the whole tree for the pointer to remove
154 // because the item may have been moved. We do not expand the item
155 // type search as this should not change.
156
157 const int mmin2[3] = { type, INT_MIN, INT_MIN };
158 const int mmax2[3] = { type, INT_MAX, INT_MAX };
159
160 m_tree->Search( mmin2, mmax2, search );
161 }
162
163 return found;
164 }
165
171 size_t size() const
172 {
173 return m_count;
174 }
175
176 bool empty() const
177 {
178 return m_count == 0;
179 }
180
181 using iterator = typename ee_rtree::Iterator;
182
191 struct EE_TYPE
192 {
193 EE_TYPE( ee_rtree* aTree, KICAD_T aType ) : type_tree( aTree )
194 {
195 KICAD_T type = BaseType( aType );
196
197 if( type == SCH_LOCATE_ANY_T )
198 m_rect = { { INT_MIN, INT_MIN, INT_MIN }, { INT_MAX, INT_MAX, INT_MAX } };
199 else
200 m_rect = { { type, INT_MIN, INT_MIN }, { type, INT_MAX, INT_MAX } };
201 };
202
203 EE_TYPE( ee_rtree* aTree, KICAD_T aType, const BOX2I& aRect ) : type_tree( aTree )
204 {
205 KICAD_T type = BaseType( aType );
206
207 if( type == SCH_LOCATE_ANY_T )
208 {
209 m_rect = { { INT_MIN, aRect.GetX(), aRect.GetY() },
210 { INT_MAX, aRect.GetRight(), aRect.GetBottom() } };
211 }
212 else
213 {
214 m_rect = { { type, aRect.GetX(), aRect.GetY() },
215 { type, aRect.GetRight(), aRect.GetBottom() } };
216 }
217 };
218
219 ee_rtree::Rect m_rect;
221
223 {
224 return type_tree->begin( m_rect );
225 }
226
228 {
229 return type_tree->end( m_rect );
230 }
231
232 bool empty()
233 {
234 return type_tree->Count() == 0;
235 }
236 };
237
238 EE_TYPE OfType( KICAD_T aType ) const
239 {
240 return EE_TYPE( m_tree, aType );
241 }
242
243 EE_TYPE Overlapping( const BOX2I& aRect ) const
244 {
245 return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
246 }
247
248 EE_TYPE Overlapping( const VECTOR2I& aPoint, int aAccuracy = 0 ) const
249 {
250 BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
251 rect.Inflate( aAccuracy );
252 return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
253 }
254
255 EE_TYPE Overlapping( KICAD_T aType, const VECTOR2I& aPoint, int aAccuracy = 0 ) const
256 {
257 BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
258 rect.Inflate( aAccuracy );
259 return EE_TYPE( m_tree, aType, rect );
260 }
261
262 EE_TYPE Overlapping( KICAD_T aType, const BOX2I& aRect ) const
263 {
264 return EE_TYPE( m_tree, aType, aRect );
265 }
266
277 {
278 return m_tree->begin();
279 }
280
286 {
287 return m_tree->end();
288 }
289
290
291 const iterator begin() const
292 {
293 return m_tree->begin();
294 }
295
296 const iterator end() const
297 {
298 return m_tree->end();
299 }
300
301
302private:
304 size_t m_count;
305};
306
307
308#endif /* EESCHEMA_SCH_RTREE_H_ */
coord_type GetY() const
Definition: box2.h:181
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetBottom() const
Definition: box2.h:190
virtual const BOX2I GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:74
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
Implements an R-tree for fast spatial and type indexing of schematic items.
Definition: sch_rtree.h:40
typename ee_rtree::Iterator iterator
Definition: sch_rtree.h:181
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:42
bool empty() const
Definition: sch_rtree.h:176
EE_TYPE Overlapping(KICAD_T aType, const BOX2I &aRect) const
Definition: sch_rtree.h:262
size_t size() const
Return the number of items in the tree.
Definition: sch_rtree.h:171
EE_TYPE Overlapping(const BOX2I &aRect) const
Definition: sch_rtree.h:243
bool remove(SCH_ITEM *aItem)
Remove an item from the tree.
Definition: sch_rtree.h:78
void insert(SCH_ITEM *aItem)
Insert an item into the tree.
Definition: sch_rtree.h:59
const iterator end() const
Definition: sch_rtree.h:296
bool contains(const SCH_ITEM *aItem, bool aRobust=false) const
Determine if a given item exists in the tree.
Definition: sch_rtree.h:125
iterator end()
Returns a read/write iterator that points to one past the last element in the EE_RTREE.
Definition: sch_rtree.h:285
EE_TYPE Overlapping(const VECTOR2I &aPoint, int aAccuracy=0) const
Definition: sch_rtree.h:248
size_t m_count
Definition: sch_rtree.h:304
EE_RTREE()
Definition: sch_rtree.h:45
iterator begin()
Returns a read/write iterator that points to the first element in the EE_RTREE N.B.
Definition: sch_rtree.h:276
EE_TYPE Overlapping(KICAD_T aType, const VECTOR2I &aPoint, int aAccuracy=0) const
Definition: sch_rtree.h:255
const iterator begin() const
Definition: sch_rtree.h:291
EE_TYPE OfType(KICAD_T aType) const
Definition: sch_rtree.h:238
ee_rtree * m_tree
Definition: sch_rtree.h:303
void clear()
Remove all items from the RTree.
Definition: sch_rtree.h:111
~EE_RTREE()
Definition: sch_rtree.h:51
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:147
virtual int GetPenWidth() const
Definition: sch_item.h:263
The EE_TYPE struct provides a type-specific auto-range iterator to the RTree.
Definition: sch_rtree.h:192
EE_TYPE(ee_rtree *aTree, KICAD_T aType)
Definition: sch_rtree.h:193
iterator begin()
Definition: sch_rtree.h:222
ee_rtree::Rect m_rect
Definition: sch_rtree.h:219
EE_TYPE(ee_rtree *aTree, KICAD_T aType, const BOX2I &aRect)
Definition: sch_rtree.h:203
ee_rtree * type_tree
Definition: sch_rtree.h:220
iterator end()
Definition: sch_rtree.h:227
constexpr KICAD_T BaseType(const KICAD_T aType)
Return the underlying type of the given type.
Definition: typeinfo.h:253
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:78
@ SCH_LOCATE_ANY_T
Definition: typeinfo.h:183
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618