KiCad PCB EDA Suite
Loading...
Searching...
No Matches
connectivity_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) 2018 KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24#ifndef PCBNEW_CONNECTIVITY_RTREE_H_
25#define PCBNEW_CONNECTIVITY_RTREE_H_
26
27#include <math/box2.h>
28#include <router/pns_layerset.h>
29
30#include <geometry/rtree.h>
31
32
38template< class T >
40{
41public:
42
44 {
45 this->m_tree = new RTree<T, int, 3, double>();
46 }
47
49 {
50 delete this->m_tree;
51 }
52
57 void Insert( T aItem )
58 {
59 const BOX2I& bbox = aItem->BBox();
60 const LAYER_RANGE layers = aItem->Layers();
61
62 const int mmin[3] = { layers.Start(), bbox.GetX(), bbox.GetY() };
63 const int mmax[3] = { layers.End(), bbox.GetRight(), bbox.GetBottom() };
64
65 m_tree->Insert( mmin, mmax, aItem );
66 }
67
73 void Remove( T aItem )
74 {
75
76 // First, attempt to remove the item using its given BBox
77 const BOX2I& bbox = aItem->BBox();
78 const LAYER_RANGE layers = aItem->Layers();
79 const int mmin[3] = { layers.Start(), bbox.GetX(), bbox.GetY() };
80 const int mmax[3] = { layers.End(), bbox.GetRight(), bbox.GetBottom() };
81
82 // If we are not successful ( 1 == not found ), then we expand
83 // the search to the full tree
84 if( m_tree->Remove( mmin, mmax, aItem ) )
85 {
86 // N.B. We must search the whole tree for the pointer to remove
87 // because the item may have been moved before we have the chance to
88 // delete it from the tree
89 const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
90 const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
91 m_tree->Remove( mmin2, mmax2, aItem );
92 }
93 }
94
99 void RemoveAll( )
100 {
101 m_tree->RemoveAll();
102 }
103
109 template <class Visitor>
110 void Query( const BOX2I& aBounds, const LAYER_RANGE& aRange, Visitor& aVisitor ) const
111 {
112 const int mmin[3] = { aRange.Start(), aBounds.GetX(), aBounds.GetY() };
113 const int mmax[3] = { aRange.End(), aBounds.GetRight(), aBounds.GetBottom() };
114
115 m_tree->Search( mmin, mmax, aVisitor );
116 }
117
118private:
119
120 RTree<T, int, 3, double>* m_tree;
121};
122
123
124#endif /* PCBNEW_CONNECTIVITY_RTREE_H_ */
coord_type GetY() const
Definition: box2.h:182
coord_type GetX() const
Definition: box2.h:181
coord_type GetRight() const
Definition: box2.h:190
coord_type GetBottom() const
Definition: box2.h:191
CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
void Query(const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor) const
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
void Remove(T aItem)
Function Remove() Removes an item from the tree.
RTree< T, int, 3, double > * m_tree
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
int Start() const
Definition: pns_layerset.h:82
int End() const
Definition: pns_layerset.h:87