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 <pad.h>
31 #include <fp_text.h>
32 #include <memory>
33 #include <unordered_set>
34 #include <set>
35 #include <vector>
36 
37 #include <geometry/rtree.h>
38 #include <geometry/shape.h>
39 #include <geometry/shape_segment.h>
40 #include <math/vector2d.h>
41 
46 class DRC_RTREE
47 {
48 
49 public:
50 
52  {
53  ITEM_WITH_SHAPE( BOARD_ITEM *aParent, SHAPE* aShape,
54  std::shared_ptr<SHAPE> aParentShape = nullptr ) :
55  parent ( aParent ),
56  shape ( aShape ),
57  parentShape( aParentShape )
58  {};
59 
62  std::shared_ptr<SHAPE> parentShape;
63  };
64 
65 private:
66 
67  using drc_rtree = RTree<ITEM_WITH_SHAPE*, int, 2, double>;
68 
69 public:
70 
72  {
73  for( int layer : LSET::AllLayersMask().Seq() )
74  m_tree[layer] = new drc_rtree();
75 
76  m_count = 0;
77  }
78 
80  {
81  for( auto tree : m_tree )
82  {
83  for( auto el : *tree )
84  delete el;
85 
86  delete tree;
87  }
88  }
89 
93  void Insert( BOARD_ITEM* aItem, PCB_LAYER_ID aLayer, int aWorstClearance = 0 )
94  {
95  wxCHECK( aLayer != UNDEFINED_LAYER, /* void */ );
96 
97  if( aItem->Type() == PCB_FP_TEXT_T && !static_cast<FP_TEXT*>( aItem )->IsVisible() )
98  return;
99 
100  std::vector<SHAPE*> subshapes;
101  std::shared_ptr<SHAPE> shape = aItem->GetEffectiveShape( ToLAYER_ID( aLayer ) );
102  subshapes.clear();
103 
104  if( shape->HasIndexableSubshapes() )
105  shape->GetIndexableSubshapes( subshapes );
106  else
107  subshapes.push_back( shape.get() );
108 
109  if( aItem->Type() == PCB_PAD_T )
110  {
111  PAD* pad = static_cast<PAD*>( aItem );
112 
113  if( pad->GetDrillSizeX() )
114  {
115  const SHAPE* hole = pad->GetEffectiveHoleShape();
116  subshapes.push_back( const_cast<SHAPE*>( hole ) );
117  }
118  }
119 
120  for( SHAPE* subshape : subshapes )
121  {
122  BOX2I bbox = subshape->BBox();
123 
124  bbox.Inflate( aWorstClearance );
125 
126  const int mmin[2] = { bbox.GetX(), bbox.GetY() };
127  const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
128  ITEM_WITH_SHAPE* itemShape = new ITEM_WITH_SHAPE( aItem, subshape, shape );
129 
130  m_tree[aLayer]->Insert( mmin, mmax, itemShape );
131  m_count++;
132  }
133  }
134 
138  void clear()
139  {
140  for( auto tree : m_tree )
141  tree->RemoveAll();
142 
143  m_count = 0;
144  }
145 
146  bool CheckColliding( SHAPE* aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance = 0,
147  std::function<bool( BOARD_ITEM*)> aFilter = nullptr ) const
148  {
149  BOX2I box = aRefShape->BBox();
150  box.Inflate( aClearance );
151 
152  int min[2] = { box.GetX(), box.GetY() };
153  int max[2] = { box.GetRight(), box.GetBottom() };
154 
155  int count = 0;
156 
157  auto visit =
158  [&] ( ITEM_WITH_SHAPE* aItem ) -> bool
159  {
160  if( !aFilter || aFilter( aItem->parent ) )
161  {
162  int actual;
163 
164  if( aRefShape->Collide( aItem->shape, aClearance, &actual ) )
165  {
166  count++;
167  return false;
168  }
169  }
170 
171  return true;
172  };
173 
174  this->m_tree[aTargetLayer]->Search( min, max, visit );
175  return count > 0;
176  }
177 
183  int QueryColliding( BOARD_ITEM* aRefItem,
184  PCB_LAYER_ID aRefLayer,
185  PCB_LAYER_ID aTargetLayer,
186  std::function<bool( BOARD_ITEM* )> aFilter = nullptr,
187  std::function<bool( BOARD_ITEM* )> aVisitor = nullptr,
188  int aClearance = 0 ) const
189  {
190  // keep track of BOARD_ITEMs that have been already found to collide (some items
191  // might be build of COMPOUND/triangulated shapes and a single subshape collision
192  // means we have a hit)
193  std::unordered_set<BOARD_ITEM*> collidingCompounds;
194 
195  // keep track of results of client filter so we don't ask more than once for compound
196  // shapes
197  std::map<BOARD_ITEM*, bool> filterResults;
198 
199  EDA_RECT box = aRefItem->GetBoundingBox();
200  box.Inflate( aClearance );
201 
202  int min[2] = { box.GetX(), box.GetY() };
203  int max[2] = { box.GetRight(), box.GetBottom() };
204 
205  std::shared_ptr<SHAPE> refShape = aRefItem->GetEffectiveShape( aRefLayer );
206 
207  int count = 0;
208 
209  auto visit =
210  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
211  {
212  if( aItem->parent == aRefItem )
213  return true;
214 
215  if( collidingCompounds.find( aItem->parent ) != collidingCompounds.end() )
216  return true;
217 
218  bool filtered;
219  auto it = filterResults.find( aItem->parent );
220 
221  if( it == filterResults.end() )
222  {
223  filtered = aFilter && !aFilter( aItem->parent );
224  filterResults[ aItem->parent ] = filtered;
225  }
226  else
227  {
228  filtered = it->second;
229  }
230 
231  if( filtered )
232  return true;
233 
234  if( refShape->Collide( aItem->shape, aClearance ) )
235  {
236  collidingCompounds.insert( aItem->parent );
237  count++;
238 
239  if( aVisitor )
240  return aVisitor( aItem->parent );
241  }
242 
243  return true;
244  };
245 
246  this->m_tree[aTargetLayer]->Search( min, max, visit );
247  return count;
248  }
249 
256  bool QueryColliding( EDA_RECT aBox, SHAPE* aRefShape, PCB_LAYER_ID aLayer, int aClearance,
257  int* aActual, VECTOR2I* aPos ) const
258  {
259  aBox.Inflate( aClearance );
260 
261  int min[2] = { aBox.GetX(), aBox.GetY() };
262  int max[2] = { aBox.GetRight(), aBox.GetBottom() };
263 
264  bool collision = false;
265  int actual = INT_MAX;
266  VECTOR2I pos;
267 
268  auto visit =
269  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
270  {
271  int curActual;
272  VECTOR2I curPos;
273 
274  if( aRefShape->Collide( aItem->shape, aClearance, &curActual, &curPos ) )
275  {
276  collision = true;
277 
278  if( curActual < actual )
279  {
280  actual = curActual;
281  pos = curPos;
282  }
283 
284  // Stop looking after we have a true collision
285  if( actual <= 0 )
286  return false;
287  }
288 
289  return true;
290  };
291 
292  this->m_tree[aLayer]->Search( min, max, visit );
293 
294  if( collision )
295  {
296  if( aActual )
297  *aActual = std::max( 0, actual );
298 
299  if( aPos )
300  *aPos = pos;
301 
302  return true;
303  }
304 
305  return false;
306  }
307 
311  bool QueryColliding( EDA_RECT aBox, SHAPE* aRefShape, PCB_LAYER_ID aLayer ) const
312  {
313  SHAPE_POLY_SET* poly = dynamic_cast<SHAPE_POLY_SET*>( aRefShape );
314 
315  int min[2] = { aBox.GetX(), aBox.GetY() };
316  int max[2] = { aBox.GetRight(), aBox.GetBottom() };
317  bool collision = false;
318 
319  // Special case the polygon case. Otherwise we'll call its Collide() method which will
320  // triangulate it as well and then do triangle/triangle collisions. This ends up being
321  // slower than 4 calls to PointInside().
322  auto polyVisitor =
323  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
324  {
325  SHAPE* shape = aItem->shape;
326  wxASSERT( dynamic_cast<SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI*>( shape ) );
327  auto tri = static_cast<SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI*>( shape );
328 
329  const SHAPE_LINE_CHAIN& outline = poly->Outline( 0 );
330 
331  if( outline.PointInside( tri->GetPoint( 0 ) )
332  || outline.PointInside( tri->GetPoint( 1 ) )
333  || outline.PointInside( tri->GetPoint( 2 ) )
334  || tri->PointInside( outline.CPoint( 0 ) ) )
335  {
336  collision = true;
337  return false;
338  }
339 
340  return true;
341  };
342 
343  auto visitor =
344  [&]( ITEM_WITH_SHAPE* aItem ) -> bool
345  {
346  if( aRefShape->Collide( aItem->shape, 0 ) )
347  {
348  collision = true;
349  return false;
350  }
351 
352  return true;
353  };
354 
355  if( poly && poly->OutlineCount() == 1 )
356  this->m_tree[aLayer]->Search( min, max, polyVisitor );
357  else
358  this->m_tree[aLayer]->Search( min, max, visitor );
359 
360  return collision;
361  }
362 
363  typedef std::pair<PCB_LAYER_ID, PCB_LAYER_ID> LAYER_PAIR;
364 
365  struct PAIR_INFO
366  {
368  layerPair( aPair ),
369  refItem( aRef ),
370  testItem( aTest )
371  { };
372 
376  };
377 
379  std::vector<LAYER_PAIR> aLayerPairs,
380  std::function<bool( const LAYER_PAIR&,
382  bool* aCollision )> aVisitor,
383  int aMaxClearance,
384  std::function<bool(int, int )> aProgressReporter ) const
385  {
386  std::vector<PAIR_INFO> pairsToVisit;
387 
388  for( LAYER_PAIR& layerPair : aLayerPairs )
389  {
390  const PCB_LAYER_ID refLayer = layerPair.first;
391  const PCB_LAYER_ID targetLayer = layerPair.second;
392 
393  for( ITEM_WITH_SHAPE* refItem : aRefTree->OnLayer( refLayer ) )
394  {
395  BOX2I box = refItem->shape->BBox();
396  box.Inflate( aMaxClearance );
397 
398  int min[2] = { box.GetX(), box.GetY() };
399  int max[2] = { box.GetRight(), box.GetBottom() };
400 
401  auto visit =
402  [&]( ITEM_WITH_SHAPE* aItemToTest ) -> bool
403  {
404  // don't collide items against themselves
405  if( aItemToTest->parent == refItem->parent )
406  return true;
407 
408  pairsToVisit.emplace_back( layerPair, refItem, aItemToTest );
409  return true;
410  };
411 
412  this->m_tree[targetLayer]->Search( min, max, visit );
413  };
414  }
415 
416  // keep track of BOARD_ITEMs pairs that have been already found to collide (some items
417  // might be build of COMPOUND/triangulated shapes and a single subshape collision
418  // means we have a hit)
419  std::map< std::pair<BOARD_ITEM*, BOARD_ITEM*>, int> collidingCompounds;
420 
421  int progress = 0;
422  int count = pairsToVisit.size();
423 
424  for( const PAIR_INFO& pair : pairsToVisit )
425  {
426  if( !aProgressReporter( progress++, count ) )
427  break;
428 
429  BOARD_ITEM* a = pair.refItem->parent;
430  BOARD_ITEM* b = pair.testItem->parent;
431 
432  // store canonical order so we don't collide in both directions (a:b and b:a)
433  if( static_cast<void*>( a ) > static_cast<void*>( b ) )
434  std::swap( a, b );
435 
436  // don't report multiple collisions for compound or triangulated shapes
437  if( collidingCompounds.count( { a, b } ) )
438  continue;
439 
440  bool collisionDetected = false;
441 
442  if( !aVisitor( pair.layerPair, pair.refItem, pair.testItem, &collisionDetected ) )
443  break;
444 
445  if( collisionDetected )
446  collidingCompounds[ { a, b } ] = 1;
447  }
448 
449  return 0;
450  }
451 
457  size_t size() const
458  {
459  return m_count;
460  }
461 
462  bool empty() const
463  {
464  return m_count == 0;
465  }
466 
467  using iterator = typename drc_rtree::Iterator;
468 
477  struct DRC_LAYER
478  {
479  DRC_LAYER( drc_rtree* aTree ) : layer_tree( aTree )
480  {
481  m_rect = { { INT_MIN, INT_MIN }, { INT_MAX, INT_MAX } };
482  };
483 
484  DRC_LAYER( drc_rtree* aTree, const EDA_RECT aRect ) : layer_tree( aTree )
485  {
486  m_rect = { { aRect.GetX(), aRect.GetY() },
487  { aRect.GetRight(), aRect.GetBottom() } };
488  };
489 
490  drc_rtree::Rect m_rect;
492 
494  {
495  return layer_tree->begin( m_rect );
496  }
497 
499  {
500  return layer_tree->end( m_rect );
501  }
502  };
503 
505  {
506  return DRC_LAYER( m_tree[int( aLayer )] );
507  }
508 
509  DRC_LAYER Overlapping( PCB_LAYER_ID aLayer, const wxPoint& aPoint, int aAccuracy = 0 ) const
510  {
511  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
512  rect.Inflate( aAccuracy );
513  return DRC_LAYER( m_tree[int( aLayer )], rect );
514  }
515 
516  DRC_LAYER Overlapping( PCB_LAYER_ID aLayer, const EDA_RECT& aRect ) const
517  {
518  return DRC_LAYER( m_tree[int( aLayer )], aRect );
519  }
520 
521 
522 private:
524  size_t m_count;
525 };
526 
527 
528 #endif /* DRC_RTREE_H_ */
iterator begin()
Definition: drc_rtree.h:493
ITEM_WITH_SHAPE(BOARD_ITEM *aParent, SHAPE *aShape, std::shared_ptr< SHAPE > aParentShape=nullptr)
Definition: drc_rtree.h:53
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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:49
int GetX() const
Definition: eda_rect.h:107
bool empty() const
Definition: drc_rtree.h:462
drc_rtree * layer_tree
Definition: drc_rtree.h:491
coord_type GetRight() const
Definition: box2.h:182
LAYER_PAIR layerPair
Definition: drc_rtree.h:371
DRC_LAYER(drc_rtree *aTree)
Definition: drc_rtree.h:479
class PAD, a pad in a footprint
Definition: typeinfo.h:89
std::pair< PCB_LAYER_ID, PCB_LAYER_ID > LAYER_PAIR
Definition: drc_rtree.h:363
coord_type GetBottom() const
Definition: box2.h:183
drc_rtree::Rect m_rect
Definition: drc_rtree.h:488
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Definition: board_item.cpp:181
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:516
RTree< ITEM_WITH_SHAPE *, int, 2, double > drc_rtree
Definition: drc_rtree.h:67
int GetBottom() const
Definition: eda_rect.h:123
DRC_LAYER(drc_rtree *aTree, const EDA_RECT aRect)
Definition: drc_rtree.h:484
The DRC_LAYER struct provides a layer-specific auto-range iterator to the RTree.
Definition: drc_rtree.h:477
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
DRC_LAYER Overlapping(PCB_LAYER_ID aLayer, const wxPoint &aPoint, int aAccuracy=0) const
Definition: drc_rtree.h:509
bool CheckColliding(SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
Definition: drc_rtree.h:146
size_t size() const
Return the number of items in the tree.
Definition: drc_rtree.h:457
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
std::shared_ptr< SHAPE > parentShape
Definition: drc_rtree.h:62
ITEM_WITH_SHAPE * testItem
Definition: drc_rtree.h:375
ITEM_WITH_SHAPE * refItem
Definition: drc_rtree.h:374
int GetRight() const
Definition: eda_rect.h:120
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
size_t m_count
Definition: drc_rtree.h:524
void clear()
Remove all items from the RTree.
Definition: drc_rtree.h:138
static LSET AllLayersMask()
Definition: lset.cpp:796
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:378
DRC_RTREE()
Definition: drc_rtree.h:71
PAIR_INFO(LAYER_PAIR aPair, ITEM_WITH_SHAPE *aRef, ITEM_WITH_SHAPE *aTest)
Definition: drc_rtree.h:367
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:108
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:93
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:75
Definition: pad.h:57
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:46
typename drc_rtree::Iterator iterator
Definition: drc_rtree.h:467
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:256
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:311
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:914
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:112
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:183
DRC_LAYER OnLayer(PCB_LAYER_ID aLayer) const
Definition: drc_rtree.h:504
~DRC_RTREE()
Definition: drc_rtree.h:79