KiCad PCB EDA Suite
drc_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) 2020-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 DRC_RTREE_H_
26 #define DRC_RTREE_H_
27 
28 #include <eda_rect.h>
29 #include <board_item.h>
30 #include <fp_text.h>
31 #include <memory>
32 #include <unordered_set>
33 #include <set>
34 #include <vector>
35 
36 #include <geometry/rtree.h>
37 #include <geometry/shape.h>
38 #include <math/vector2d.h>
39 
44 class DRC_RTREE
45 {
46 
47 public:
48 
50  {
51  ITEM_WITH_SHAPE( BOARD_ITEM *aParent, SHAPE* aShape,
52  std::shared_ptr<SHAPE> aParentShape = nullptr ) :
53  parent ( aParent ),
54  shape ( aShape ),
55  parentShape( aParentShape )
56  {};
57 
60  std::shared_ptr<SHAPE> parentShape;
61  };
62 
63 private:
64 
65  using drc_rtree = RTree<ITEM_WITH_SHAPE*, int, 2, double>;
66 
67 public:
68 
70  {
71  for( int layer : LSET::AllLayersMask().Seq() )
72  m_tree[layer] = new drc_rtree();
73 
74  m_count = 0;
75  }
76 
78  {
79  for( auto tree : m_tree )
80  delete tree;
81  }
82 
86  void Insert( BOARD_ITEM* aItem, PCB_LAYER_ID aLayer, int aWorstClearance = 0 )
87  {
88  wxCHECK( aLayer != UNDEFINED_LAYER, /* void */ );
89 
90  if( aItem->Type() == PCB_FP_TEXT_T && !static_cast<FP_TEXT*>( aItem )->IsVisible() )
91  return;
92 
93  std::vector<SHAPE*> subshapes;
94  std::shared_ptr<SHAPE> shape = aItem->GetEffectiveShape( ToLAYER_ID( aLayer ) );
95  subshapes.clear();
96 
97  if( shape->HasIndexableSubshapes() )
98  shape->GetIndexableSubshapes( subshapes );
99  else
100  subshapes.push_back( shape.get() );
101 
102  for( SHAPE* subshape : subshapes )
103  {
104  BOX2I bbox = subshape->BBox();
105 
106  bbox.Inflate( aWorstClearance );
107 
108  const int mmin[2] = { bbox.GetX(), bbox.GetY() };
109  const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
110  ITEM_WITH_SHAPE* itemShape = new ITEM_WITH_SHAPE( aItem, subshape, shape );
111 
112  m_tree[aLayer]->Insert( mmin, mmax, itemShape );
113  m_count++;
114  }
115  }
116 
120  void clear()
121  {
122  for( auto tree : m_tree )
123  tree->RemoveAll();
124 
125  m_count = 0;
126  }
127 
128  bool CheckColliding( SHAPE* aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance = 0,
129  std::function<bool( BOARD_ITEM*)> aFilter = nullptr ) const
130  {
131  BOX2I box = aRefShape->BBox();
132  box.Inflate( aClearance );
133 
134  int min[2] = { box.GetX(), box.GetY() };
135  int max[2] = { box.GetRight(), box.GetBottom() };
136 
137  int count = 0;
138 
139  auto visit =
140  [&] ( ITEM_WITH_SHAPE* aItem ) -> bool
141  {
142  if( !aFilter || aFilter( aItem->parent ) )
143  {
144  int actual;
145 
146  if( aRefShape->Collide( aItem->shape, aClearance, &actual ) )
147  {
148  count++;
149  return false;
150  }
151  }
152 
153  return true;
154  };
155 
156  this->m_tree[aTargetLayer]->Search( min, max, visit );
157  return count > 0;
158  }
159 
165  int QueryColliding( BOARD_ITEM* aRefItem,
166  PCB_LAYER_ID aRefLayer,
167  PCB_LAYER_ID aTargetLayer,
168  std::function<bool( BOARD_ITEM* )> aFilter = nullptr,
169  std::function<bool( BOARD_ITEM* )> aVisitor = nullptr,
170  int aClearance = 0 ) const
171  {
172  // keep track of BOARD_ITEMs that have been already found to collide (some items
173  // might be build of COMPOUND/triangulated shapes and a single subshape collision
174  // means we have a hit)
175  std::unordered_set<BOARD_ITEM*> collidingCompounds;
176 
177  // keep track of results of client filter so we don't ask more than once for compound
178  // shapes
179  std::map<BOARD_ITEM*, bool> filterResults;
180 
181  EDA_RECT box = aRefItem->GetBoundingBox();
182  box.Inflate( aClearance );
183 
184  int min[2] = { box.GetX(), box.GetY() };
185  int max[2] = { box.GetRight(), box.GetBottom() };
186 
187  std::shared_ptr<SHAPE> refShape = aRefItem->GetEffectiveShape( aRefLayer );
188 
189  int count = 0;
190 
191  auto visit =
192  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
193  {
194  if( aItem->parent == aRefItem )
195  return true;
196 
197  if( collidingCompounds.find( aItem->parent ) != collidingCompounds.end() )
198  return true;
199 
200  bool filtered;
201  auto it = filterResults.find( aItem->parent );
202 
203  if( it == filterResults.end() )
204  {
205  filtered = aFilter && !aFilter( aItem->parent );
206  filterResults[ aItem->parent ] = filtered;
207  }
208  else
209  {
210  filtered = it->second;
211  }
212 
213  if( filtered )
214  return true;
215 
216  if( refShape->Collide( aItem->shape, aClearance ) )
217  {
218  collidingCompounds.insert( aItem->parent );
219  count++;
220 
221  if( aVisitor )
222  return aVisitor( aItem->parent );
223  }
224 
225  return true;
226  };
227 
228  this->m_tree[aTargetLayer]->Search( min, max, visit );
229  return count;
230  }
231 
238  bool QueryColliding( EDA_RECT aBox, SHAPE* aRefShape, PCB_LAYER_ID aLayer, int aClearance,
239  int* aActual, VECTOR2I* aPos ) const
240  {
241  aBox.Inflate( aClearance );
242 
243  int min[2] = { aBox.GetX(), aBox.GetY() };
244  int max[2] = { aBox.GetRight(), aBox.GetBottom() };
245 
246  bool collision = false;
247  int actual = INT_MAX;
248  VECTOR2I pos;
249 
250  auto visit =
251  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
252  {
253  int curActual;
254  VECTOR2I curPos;
255 
256  if( aRefShape->Collide( aItem->shape, aClearance, &curActual, &curPos ) )
257  {
258  collision = true;
259 
260  if( curActual < actual )
261  {
262  actual = curActual;
263  pos = curPos;
264  }
265 
266  // Stop looking after we have a true collision
267  if( actual <= 0 )
268  return false;
269  }
270 
271  return true;
272  };
273 
274  this->m_tree[aLayer]->Search( min, max, visit );
275 
276  if( collision )
277  {
278  if( aActual )
279  *aActual = std::max( 0, actual );
280 
281  if( aPos )
282  *aPos = pos;
283 
284  return true;
285  }
286 
287  return false;
288  }
289 
293  bool QueryColliding( EDA_RECT aBox, SHAPE* aRefShape, PCB_LAYER_ID aLayer ) const
294  {
295  int min[2] = { aBox.GetX(), aBox.GetY() };
296  int max[2] = { aBox.GetRight(), aBox.GetBottom() };
297  bool collision = false;
298 
299  auto visit =
300  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
301  {
302  if( aRefShape->Collide( aItem->shape, 0 ) )
303  {
304  collision = true;
305  return false;
306  }
307 
308  return true;
309  };
310 
311  this->m_tree[aLayer]->Search( min, max, visit );
312 
313  return collision;
314  }
315 
316  typedef std::pair<PCB_LAYER_ID, PCB_LAYER_ID> LAYER_PAIR;
317 
318  struct PAIR_INFO
319  {
321  layerPair( aPair ),
322  refItem( aRef ),
323  testItem( aTest )
324  { };
325 
329  };
330 
332  std::vector<LAYER_PAIR> aLayerPairs,
333  std::function<bool( const LAYER_PAIR&,
335  bool* aCollision )> aVisitor,
336  int aMaxClearance,
337  std::function<bool(int, int )> aProgressReporter ) const
338  {
339  std::vector<PAIR_INFO> pairsToVisit;
340 
341  for( LAYER_PAIR& layerPair : aLayerPairs )
342  {
343  const PCB_LAYER_ID refLayer = layerPair.first;
344  const PCB_LAYER_ID targetLayer = layerPair.second;
345 
346  for( ITEM_WITH_SHAPE* refItem : aRefTree->OnLayer( refLayer ) )
347  {
348  BOX2I box = refItem->shape->BBox();
349  box.Inflate( aMaxClearance );
350 
351  int min[2] = { box.GetX(), box.GetY() };
352  int max[2] = { box.GetRight(), box.GetBottom() };
353 
354  auto visit =
355  [&]( ITEM_WITH_SHAPE* aItemToTest ) -> bool
356  {
357  // don't collide items against themselves
358  if( aItemToTest->parent == refItem->parent )
359  return true;
360 
361  pairsToVisit.emplace_back( layerPair, refItem, aItemToTest );
362  return true;
363  };
364 
365  this->m_tree[targetLayer]->Search( min, max, visit );
366  };
367  }
368 
369  // keep track of BOARD_ITEMs pairs that have been already found to collide (some items
370  // might be build of COMPOUND/triangulated shapes and a single subshape collision
371  // means we have a hit)
372  std::map< std::pair<BOARD_ITEM*, BOARD_ITEM*>, int> collidingCompounds;
373 
374  int progress = 0;
375  int count = pairsToVisit.size();
376 
377  for( const PAIR_INFO& pair : pairsToVisit )
378  {
379  if( !aProgressReporter( progress++, count ) )
380  break;
381 
382  BOARD_ITEM* a = pair.refItem->parent;
383  BOARD_ITEM* b = pair.testItem->parent;
384 
385  // store canonical order so we don't collide in both directions (a:b and b:a)
386  if( static_cast<void*>( a ) > static_cast<void*>( b ) )
387  std::swap( a, b );
388 
389  // don't report multiple collisions for compound or triangulated shapes
390  if( collidingCompounds.count( { a, b } ) )
391  continue;
392 
393  bool collisionDetected = false;
394 
395  if( !aVisitor( pair.layerPair, pair.refItem, pair.testItem, &collisionDetected ) )
396  break;
397 
398  if( collisionDetected )
399  collidingCompounds[ { a, b } ] = 1;
400  }
401 
402  return 0;
403  }
404 
410  size_t size() const
411  {
412  return m_count;
413  }
414 
415  bool empty() const
416  {
417  return m_count == 0;
418  }
419 
420  using iterator = typename drc_rtree::Iterator;
421 
430  struct DRC_LAYER
431  {
432  DRC_LAYER( drc_rtree* aTree ) : layer_tree( aTree )
433  {
434  m_rect = { { INT_MIN, INT_MIN }, { INT_MAX, INT_MAX } };
435  };
436 
437  DRC_LAYER( drc_rtree* aTree, const EDA_RECT aRect ) : layer_tree( aTree )
438  {
439  m_rect = { { aRect.GetX(), aRect.GetY() },
440  { aRect.GetRight(), aRect.GetBottom() } };
441  };
442 
443  drc_rtree::Rect m_rect;
445 
447  {
448  return layer_tree->begin( m_rect );
449  }
450 
452  {
453  return layer_tree->end( m_rect );
454  }
455  };
456 
458  {
459  return DRC_LAYER( m_tree[int( aLayer )] );
460  }
461 
462  DRC_LAYER Overlapping( PCB_LAYER_ID aLayer, const wxPoint& aPoint, int aAccuracy = 0 ) const
463  {
464  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
465  rect.Inflate( aAccuracy );
466  return DRC_LAYER( m_tree[int( aLayer )], rect );
467  }
468 
469  DRC_LAYER Overlapping( PCB_LAYER_ID aLayer, const EDA_RECT& aRect ) const
470  {
471  return DRC_LAYER( m_tree[int( aLayer )], aRect );
472  }
473 
474 
475 private:
477  size_t m_count;
478 };
479 
480 
481 #endif /* DRC_RTREE_H_ */
iterator begin()
Definition: drc_rtree.h:446
ITEM_WITH_SHAPE(BOARD_ITEM *aParent, SHAPE *aShape, std::shared_ptr< SHAPE > aParentShape=nullptr)
Definition: drc_rtree.h:51
class FP_TEXT, text in a footprint
Definition: typeinfo.h:92
coord_type GetX() const
Definition: box2.h:173
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:80
int GetX() const
Definition: eda_rect.h:98
bool empty() const
Definition: drc_rtree.h:415
drc_rtree * layer_tree
Definition: drc_rtree.h:444
coord_type GetRight() const
Definition: box2.h:182
LAYER_PAIR layerPair
Definition: drc_rtree.h:324
DRC_LAYER(drc_rtree *aTree)
Definition: drc_rtree.h:432
std::pair< PCB_LAYER_ID, PCB_LAYER_ID > LAYER_PAIR
Definition: drc_rtree.h:316
coord_type GetBottom() const
Definition: box2.h:183
drc_rtree::Rect m_rect
Definition: drc_rtree.h:441
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
DRC_LAYER Overlapping(PCB_LAYER_ID aLayer, const EDA_RECT &aRect) const
Definition: drc_rtree.h:469
RTree< ITEM_WITH_SHAPE *, int, 2, double > drc_rtree
Definition: drc_rtree.h:65
int GetBottom() const
Definition: eda_rect.h:114
DRC_LAYER(drc_rtree *aTree, const EDA_RECT aRect)
Definition: drc_rtree.h:437
The DRC_LAYER struct provides a layer-specific auto-range iterator to the RTree.
Definition: drc_rtree.h:430
DRC_LAYER Overlapping(PCB_LAYER_ID aLayer, const wxPoint &aPoint, int aAccuracy=0) const
Definition: drc_rtree.h:462
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:128
size_t size() const
Return the number of items in the tree.
Definition: drc_rtree.h:410
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:476
std::shared_ptr< SHAPE > parentShape
Definition: drc_rtree.h:60
ITEM_WITH_SHAPE * testItem
Definition: drc_rtree.h:328
ITEM_WITH_SHAPE * refItem
Definition: drc_rtree.h:327
int GetRight() const
Definition: eda_rect.h:111
size_t m_count
Definition: drc_rtree.h:477
void clear()
Remove all items from the RTree.
Definition: drc_rtree.h:120
static LSET AllLayersMask()
Definition: lset.cpp:787
An abstract shape on 2D plane.
Definition: shape.h:116
coord_type GetY() const
Definition: box2.h:174
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
int QueryCollidingPairs(DRC_RTREE *aRefTree, std::vector< LAYER_PAIR > aLayerPairs, std::function< bool(const LAYER_PAIR &, ITEM_WITH_SHAPE *, ITEM_WITH_SHAPE *, bool *aCollision)> aVisitor, int aMaxClearance, std::function< bool(int, int)> aProgressReporter) const
Definition: drc_rtree.h:331
DRC_RTREE()
Definition: drc_rtree.h:69
PAIR_INFO(LAYER_PAIR aPair, ITEM_WITH_SHAPE *aRef, ITEM_WITH_SHAPE *aTest)
Definition: drc_rtree.h:320
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:64
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:99
void Insert(BOARD_ITEM *aItem, PCB_LAYER_ID aLayer, int aWorstClearance=0)
Insert an item into the tree on a particular layer with an optional worst clearance.
Definition: drc_rtree.h:86
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Definition: board_item.cpp:181
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:75
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:44
typename drc_rtree::Iterator iterator
Definition: drc_rtree.h:420
bool QueryColliding(EDA_RECT aBox, SHAPE *aRefShape, PCB_LAYER_ID aLayer, int aClearance, int *aActual, VECTOR2I *aPos) const
This one is for tessellated items.
Definition: drc_rtree.h:238
bool QueryColliding(EDA_RECT aBox, SHAPE *aRefShape, PCB_LAYER_ID aLayer) const
Quicker version of above that just reports a raw yes/no.
Definition: drc_rtree.h:293
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:905
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113
int QueryColliding(BOARD_ITEM *aRefItem, PCB_LAYER_ID aRefLayer, PCB_LAYER_ID aTargetLayer, std::function< bool(BOARD_ITEM *)> aFilter=nullptr, std::function< bool(BOARD_ITEM *)> aVisitor=nullptr, int aClearance=0) const
This is a fast test which essentially does bounding-box overlap given a worst-case clearance.
Definition: drc_rtree.h:165
DRC_LAYER OnLayer(PCB_LAYER_ID aLayer) const
Definition: drc_rtree.h:457
~DRC_RTREE()
Definition: drc_rtree.h:77