KiCad PCB EDA Suite
DRC_RTREE Class Reference

Implement an R-tree for fast spatial and layer indexing of connectable items. More...

#include <drc_rtree.h>

Classes

struct  DRC_LAYER
 The DRC_LAYER struct provides a layer-specific auto-range iterator to the RTree. More...
 
struct  ITEM_WITH_SHAPE
 
struct  PAIR_INFO
 

Public Types

typedef std::pair< PCB_LAYER_ID, PCB_LAYER_IDLAYER_PAIR
 
using iterator = typename drc_rtree::Iterator
 

Public Member Functions

 DRC_RTREE ()
 
 ~DRC_RTREE ()
 
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. More...
 
void clear ()
 Remove all items from the RTree. More...
 
bool CheckColliding (SHAPE *aRefShape, PCB_LAYER_ID aTargetLayer, int aClearance=0, std::function< bool(BOARD_ITEM *)> aFilter=nullptr) const
 
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. More...
 
bool QueryColliding (EDA_RECT aBox, SHAPE *aRefShape, PCB_LAYER_ID aLayer, int aClearance, int *aActual, VECTOR2I *aPos) const
 This one is for tessellated items. More...
 
bool QueryColliding (EDA_RECT aBox, SHAPE *aRefShape, PCB_LAYER_ID aLayer) const
 Quicker version of above that just reports a raw yes/no. More...
 
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
 
size_t size () const
 Return the number of items in the tree. More...
 
bool empty () const
 
DRC_LAYER OnLayer (PCB_LAYER_ID aLayer) const
 
DRC_LAYER Overlapping (PCB_LAYER_ID aLayer, const wxPoint &aPoint, int aAccuracy=0) const
 
DRC_LAYER Overlapping (PCB_LAYER_ID aLayer, const EDA_RECT &aRect) const
 

Private Types

using drc_rtree = RTree< ITEM_WITH_SHAPE *, int, 2, double >
 

Private Attributes

drc_rtreem_tree [PCB_LAYER_ID_COUNT]
 
size_t m_count
 

Detailed Description

Implement an R-tree for fast spatial and layer indexing of connectable items.

Non-owning.

Definition at line 46 of file drc_rtree.h.

Member Typedef Documentation

◆ drc_rtree

using DRC_RTREE::drc_rtree = RTree<ITEM_WITH_SHAPE*, int, 2, double>
private

Definition at line 67 of file drc_rtree.h.

◆ iterator

using DRC_RTREE::iterator = typename drc_rtree::Iterator

Definition at line 467 of file drc_rtree.h.

◆ LAYER_PAIR

Definition at line 363 of file drc_rtree.h.

Constructor & Destructor Documentation

◆ DRC_RTREE()

DRC_RTREE::DRC_RTREE ( )
inline

Definition at line 71 of file drc_rtree.h.

72  {
73  for( int layer : LSET::AllLayersMask().Seq() )
74  m_tree[layer] = new drc_rtree();
75 
76  m_count = 0;
77  }
RTree< ITEM_WITH_SHAPE *, int, 2, double > drc_rtree
Definition: drc_rtree.h:67
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
size_t m_count
Definition: drc_rtree.h:524
static LSET AllLayersMask()
Definition: lset.cpp:796

References LSET::AllLayersMask(), m_count, and m_tree.

◆ ~DRC_RTREE()

DRC_RTREE::~DRC_RTREE ( )
inline

Definition at line 79 of file drc_rtree.h.

80  {
81  for( auto tree : m_tree )
82  {
83  for( auto el : *tree )
84  delete el;
85 
86  delete tree;
87  }
88  }
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523

References m_tree.

Member Function Documentation

◆ CheckColliding()

bool DRC_RTREE::CheckColliding ( SHAPE aRefShape,
PCB_LAYER_ID  aTargetLayer,
int  aClearance = 0,
std::function< bool(BOARD_ITEM *)>  aFilter = nullptr 
) const
inline

Definition at line 146 of file drc_rtree.h.

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  }
coord_type GetX() const
Definition: box2.h:173
coord_type GetRight() const
Definition: box2.h:182
coord_type GetBottom() const
Definition: box2.h:183
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_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
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

References SHAPE::BBox(), SHAPE::Collide(), BOX2< Vec >::GetBottom(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), and m_tree.

Referenced by extractDiffPairCoupledItems().

◆ clear()

void DRC_RTREE::clear ( )
inline

Remove all items from the RTree.

Definition at line 138 of file drc_rtree.h.

139  {
140  for( auto tree : m_tree )
141  tree->RemoveAll();
142 
143  m_count = 0;
144  }
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
size_t m_count
Definition: drc_rtree.h:524

References m_count, and m_tree.

Referenced by DRC_TEST_PROVIDER_HOLE_TO_HOLE::Run(), and DRC_TEST_PROVIDER_COPPER_CLEARANCE::Run().

◆ empty()

bool DRC_RTREE::empty ( ) const
inline

Definition at line 462 of file drc_rtree.h.

463  {
464  return m_count == 0;
465  }
size_t m_count
Definition: drc_rtree.h:524

References m_count.

◆ Insert()

void DRC_RTREE::Insert ( BOARD_ITEM aItem,
PCB_LAYER_ID  aLayer,
int  aWorstClearance = 0 
)
inline

Insert an item into the tree on a particular layer with an optional worst clearance.

Definition at line 93 of file drc_rtree.h.

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  }
class FP_TEXT, text in a footprint
Definition: typeinfo.h:92
coord_type GetX() const
Definition: box2.h:173
coord_type GetRight() const
Definition: box2.h:182
class PAD, a pad in a footprint
Definition: typeinfo.h:89
coord_type GetBottom() const
Definition: box2.h:183
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
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
size_t m_count
Definition: drc_rtree.h:524
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
Definition: pad.h:57
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:914
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:112

References BOX2< Vec >::GetBottom(), BOARD_ITEM::GetEffectiveShape(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), m_count, m_tree, pad, PCB_FP_TEXT_T, PCB_PAD_T, ToLAYER_ID(), EDA_ITEM::Type(), and UNDEFINED_LAYER.

Referenced by TRACKS_CLEANER::cleanup(), DRC_TEST_PROVIDER_SILK_TO_MASK::Run(), DRC_TEST_PROVIDER_HOLE_TO_HOLE::Run(), DRC_TEST_PROVIDER_SILK_CLEARANCE::Run(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), test::DRC_TEST_PROVIDER_DIFF_PAIR_COUPLING::Run(), and DRC_TEST_PROVIDER_COPPER_CLEARANCE::Run().

◆ OnLayer()

DRC_LAYER DRC_RTREE::OnLayer ( PCB_LAYER_ID  aLayer) const
inline

Definition at line 504 of file drc_rtree.h.

505  {
506  return DRC_LAYER( m_tree[int( aLayer )] );
507  }
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523

References m_tree.

Referenced by QueryCollidingPairs().

◆ Overlapping() [1/2]

DRC_LAYER DRC_RTREE::Overlapping ( PCB_LAYER_ID  aLayer,
const wxPoint &  aPoint,
int  aAccuracy = 0 
) const
inline

Definition at line 509 of file drc_rtree.h.

510  {
511  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
512  rect.Inflate( aAccuracy );
513  return DRC_LAYER( m_tree[int( aLayer )], rect );
514  }
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
Handle the component boundary box.
Definition: eda_rect.h:42

References EDA_RECT::Inflate(), and m_tree.

◆ Overlapping() [2/2]

DRC_LAYER DRC_RTREE::Overlapping ( PCB_LAYER_ID  aLayer,
const EDA_RECT aRect 
) const
inline

Definition at line 516 of file drc_rtree.h.

517  {
518  return DRC_LAYER( m_tree[int( aLayer )], aRect );
519  }
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523

References m_tree.

◆ QueryColliding() [1/3]

int DRC_RTREE::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
inline

This is a fast test which essentially does bounding-box overlap given a worst-case clearance.

It's used when looking up the specific item-to-item clearance might be expensive and should be deferred till we know we have a possible hit.

Definition at line 183 of file drc_rtree.h.

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  }
int GetX() const
Definition: eda_rect.h:107
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
int GetBottom() const
Definition: eda_rect.h:123
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
int GetRight() const
Definition: eda_rect.h:120
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:108
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:75
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

References EDA_RECT::GetBottom(), EDA_ITEM::GetBoundingBox(), BOARD_ITEM::GetEffectiveShape(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), EDA_RECT::Inflate(), and m_tree.

Referenced by calcIsInsideArea(), TRACKS_CLEANER::cleanup(), DRC_TEST_PROVIDER_HOLE_TO_HOLE::Run(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), DRC_TEST_PROVIDER_COPPER_CLEARANCE::testItemAgainstZones(), DRC_TEST_PROVIDER_COPPER_CLEARANCE::testPadClearances(), and DRC_TEST_PROVIDER_COPPER_CLEARANCE::testTrackClearances().

◆ QueryColliding() [2/3]

bool DRC_RTREE::QueryColliding ( EDA_RECT  aBox,
SHAPE aRefShape,
PCB_LAYER_ID  aLayer,
int  aClearance,
int *  aActual,
VECTOR2I aPos 
) const
inline

This one is for tessellated items.

(All shapes in the tree will be from a single BOARD_ITEM.) It checks all items in the bbox overlap to find the minimal actual distance and position.

Definition at line 256 of file drc_rtree.h.

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  }
int GetX() const
Definition: eda_rect.h:107
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
int GetBottom() const
Definition: eda_rect.h:123
drc_rtree * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
int GetRight() const
Definition: eda_rect.h:120
int GetY() const
Definition: eda_rect.h:108
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

References SHAPE::Collide(), EDA_RECT::GetBottom(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), EDA_RECT::Inflate(), and m_tree.

◆ QueryColliding() [3/3]

bool DRC_RTREE::QueryColliding ( EDA_RECT  aBox,
SHAPE aRefShape,
PCB_LAYER_ID  aLayer 
) const
inline

Quicker version of above that just reports a raw yes/no.

Definition at line 311 of file drc_rtree.h.

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  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
int GetX() const
Definition: eda_rect.h:107
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
int GetBottom() const
Definition: eda_rect.h:123
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
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
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.
An abstract shape on 2D plane.
Definition: shape.h:116
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int GetY() const
Definition: eda_rect.h:108

References SHAPE::Collide(), SHAPE_LINE_CHAIN::CPoint(), EDA_RECT::GetBottom(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), m_tree, SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), and SHAPE_LINE_CHAIN_BASE::PointInside().

◆ QueryCollidingPairs()

int DRC_RTREE::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
inline

Definition at line 378 of file drc_rtree.h.

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  }
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
coord_type GetRight() const
Definition: box2.h:182
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 * m_tree[PCB_LAYER_ID_COUNT]
Definition: drc_rtree.h:523
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
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
DRC_LAYER OnLayer(PCB_LAYER_ID aLayer) const
Definition: drc_rtree.h:504

References BOX2< Vec >::GetBottom(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), BOX2< Vec >::Inflate(), m_tree, and OnLayer().

Referenced by DRC_TEST_PROVIDER_SILK_TO_MASK::Run(), and DRC_TEST_PROVIDER_SILK_CLEARANCE::Run().

◆ size()

size_t DRC_RTREE::size ( ) const
inline

Return the number of items in the tree.

Returns
number of elements in the tree.

Definition at line 457 of file drc_rtree.h.

458  {
459  return m_count;
460  }
size_t m_count
Definition: drc_rtree.h:524

References m_count.

Referenced by DRC_TEST_PROVIDER_SILK_CLEARANCE::Run().

Member Data Documentation

◆ m_count

size_t DRC_RTREE::m_count
private

Definition at line 524 of file drc_rtree.h.

Referenced by clear(), DRC_RTREE(), empty(), Insert(), and size().

◆ m_tree


The documentation for this class was generated from the following file: