DRC_RTREE - Implements 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_ID >	LAYER_PAIR

using	iterator = typename drc_rtree::Iterator

Public Member Functions
	DRC_RTREE ()

	~DRC_RTREE ()

void	Insert (BOARD_ITEM *aItem, int aWorstClearance=0, int aLayer=UNDEFINED_LAYER)
	Function Insert() Inserts an item into the tree. More...

void	clear ()
	Function RemoveAll() Removes 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=nullptr, VECTOR2I *aPos=nullptr) const
	This one is for tessellated items. 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
	Returns 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_rtree *	m_tree [PCB_LAYER_ID_COUNT]

size_t	m_count

Detailed Description

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

Non-owning.

Definition at line 43 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 64 of file drc_rtree.h.

◆ iterator

using DRC_RTREE::iterator = typename drc_rtree::Iterator

Definition at line 414 of file drc_rtree.h.

◆ LAYER_PAIR

typedef std::pair<PCB_LAYER_ID, PCB_LAYER_ID> DRC_RTREE::LAYER_PAIR

Definition at line 311 of file drc_rtree.h.

Constructor & Destructor Documentation

◆ DRC_RTREE()

DRC_RTREE::DRC_RTREE ( )

inline

Definition at line 68 of file drc_rtree.h.

     {
         for( int layer : LSET::AllLayersMask().Seq() )
             m_tree[layer] = new drc_rtree();
 
         m_count = 0;
     }

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

◆ ~DRC_RTREE()

DRC_RTREE::~DRC_RTREE ( )

inline

Definition at line 76 of file drc_rtree.h.

     {
         for( auto tree : m_tree )
             delete tree;
     }

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 153 of file drc_rtree.h.

     {
         BOX2I box = aRefShape->BBox();
         box.Inflate( aClearance );
 
         int min[2] = { box.GetX(),         box.GetY() };
         int max[2] = { box.GetRight(),     box.GetBottom() };
 
         int count = 0;
 
         auto visit =
                 [&] ( ITEM_WITH_SHAPE* aItem ) -> bool
                 {
                     if( !aFilter || aFilter( aItem->parent ) )
                     {
                         int actual;
 
                         if( aRefShape->Collide( aItem->shape, aClearance, &actual ) )
                         {
                             count++;
                             return false;
                         }
                     }
 
                     return true;
                 };
 
         this->m_tree[aTargetLayer]->Search( min, max, visit );
         return count > 0;
     }

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

Function RemoveAll() Removes all items from the RTree.

Definition at line 145 of file drc_rtree.h.

     {
         for( auto tree : m_tree )
             tree->RemoveAll();
 
         m_count = 0;
     }

References m_count, and m_tree.

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

◆ empty()

bool DRC_RTREE::empty ( ) const

inline

Definition at line 409 of file drc_rtree.h.

     {
         return m_count == 0;
     }

References m_count.

◆ Insert()

void DRC_RTREE::Insert	(	BOARD_ITEM *	aItem,
		int	aWorstClearance = `0`,
		int	aLayer = `UNDEFINED_LAYER`
	)

inline

Function Insert() Inserts an item into the tree.

Definition at line 86 of file drc_rtree.h.

     {
         std::vector<SHAPE*> subshapes;
 
         auto addLayer =
                 [&]( PCB_LAYER_ID layer )
                 {
                     std::shared_ptr<SHAPE> shape = aItem->GetEffectiveShape( layer );
                     subshapes.clear();
 
                     if( shape->HasIndexableSubshapes() )
                         shape->GetIndexableSubshapes( subshapes );
                     else
                         subshapes.push_back( shape.get() );
 
                     for( SHAPE* subshape : subshapes )
                     {
                         BOX2I bbox = subshape->BBox();
 
                         bbox.Inflate( aWorstClearance );
 
                         const int mmin[2] = { bbox.GetX(), bbox.GetY() };
                         const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
 
                         m_tree[layer]->Insert( mmin, mmax, new ITEM_WITH_SHAPE( aItem, subshape,
                                                                                 shape ) );
                         m_count++;
                     }
                 };
 
         if( aItem->Type() == PCB_FP_TEXT_T && !static_cast<FP_TEXT*>( aItem )->IsVisible() )
             return;
 
         if( aLayer != UNDEFINED_LAYER )
         {
             addLayer( (PCB_LAYER_ID) aLayer );
         }
         else
         {
             LSET layers = aItem->GetLayerSet();
 
             // Special-case pad holes which pierce all the copper layers
             if( aItem->Type() == PCB_PAD_T )
             {
                 PAD* pad = static_cast<PAD*>( aItem );
 
                 if( pad->GetDrillSizeX() > 0 && pad->GetDrillSizeY() > 0 )
                     layers |= LSET::AllCuMask();
             }
 
             for( int layer : layers.Seq() )
                 addLayer( (PCB_LAYER_ID) layer );
         }
     }

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

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

◆ OnLayer()

DRC_LAYER DRC_RTREE::OnLayer ( PCB_LAYER_ID aLayer ) const

inline

Definition at line 451 of file drc_rtree.h.

     {
         return DRC_LAYER( m_tree[int( aLayer )] );
     }

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 456 of file drc_rtree.h.

     {
         EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
         rect.Inflate( aAccuracy );
         return DRC_LAYER( m_tree[int( aLayer )], rect );
     }

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 463 of file drc_rtree.h.

     {
         return DRC_LAYER( m_tree[int( aLayer )], aRect );
     }

References m_tree.

◆ QueryColliding() [1/2]

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 190 of file drc_rtree.h.

     {
         // keep track of BOARD_ITEMs that have been already found to collide (some items
         // might be build of COMPOUND/triangulated shapes and a single subshape collision
         // means we have a hit)
         std::unordered_set<BOARD_ITEM*> collidingCompounds;
 
         // keep track of results of client filter so we don't ask more than once for compound
         // shapes
         std::map<BOARD_ITEM*, bool> filterResults;
 
         EDA_RECT box = aRefItem->GetBoundingBox();
         box.Inflate( aClearance );
 
         int min[2] = { box.GetX(),         box.GetY() };
         int max[2] = { box.GetRight(),     box.GetBottom() };
 
         std::shared_ptr<SHAPE> refShape = aRefItem->GetEffectiveShape( aRefLayer );
 
         int count = 0;
 
         auto visit =
                 [&]( ITEM_WITH_SHAPE* aItem ) -> bool
                 {
                     if( aItem->parent == aRefItem )
                         return true;
 
                     if( collidingCompounds.find( aItem->parent ) != collidingCompounds.end() )
                         return true;
 
                     bool filtered;
                     auto it = filterResults.find( aItem->parent );
 
                     if( it == filterResults.end() )
                     {
                         filtered = aFilter && !aFilter( aItem->parent );
                         filterResults[ aItem->parent ] = filtered;
                     }
                     else
                     {
                         filtered = it->second;
                     }
 
                     if( filtered )
                         return true;
 
                     if( refShape->Collide( aItem->shape, aClearance ) )
                     {
                         collidingCompounds.insert( aItem->parent );
                         count++;
 
                         if( aVisitor )
                             return aVisitor( aItem->parent );
                     }
 
                     return true;
                 };
 
         this->m_tree[aTargetLayer]->Search( min, max, visit );
         return count;
     }

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 TRACKS_CLEANER::cleanup(), insideArea(), DRC_TEST_PROVIDER_HOLE_CLEARANCE::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/2]

bool DRC_RTREE::QueryColliding	(	EDA_RECT	aBox,
		SHAPE *	aRefShape,
		PCB_LAYER_ID	aLayer,
		int	aClearance,
		int *	aActual = `nullptr`,
		VECTOR2I *	aPos = `nullptr`
	)		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 263 of file drc_rtree.h.

     {
         aBox.Inflate( aClearance );
 
         int min[2] = { aBox.GetX(), aBox.GetY() };
         int max[2] = { aBox.GetRight(), aBox.GetBottom() };
 
         bool     collision = false;
         int      actual = INT_MAX;
         VECTOR2I pos;
 
         auto visit =
                 [&]( ITEM_WITH_SHAPE* aItem ) -> bool
                 {
                     int      curActual;
                     VECTOR2I curPos;
 
                     if( aRefShape->Collide( aItem->shape, aClearance, &curActual, &curPos ) )
                     {
                         collision = true;
 
                         if( curActual < actual )
                         {
                             actual = curActual;
                             pos = curPos;
                         }
                     }
 
                     return true;
                 };
 
         this->m_tree[aLayer]->Search( min, max, visit );
 
         if( collision )
         {
             if( aActual )
                 *aActual = std::max( 0, actual );
 
             if( aPos )
                 *aPos = pos;
 
             return true;
         }
 
         return false;
     }

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

◆ 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 326 of file drc_rtree.h.

     {
         std::vector<PAIR_INFO> pairsToVisit;
 
         for( LAYER_PAIR& layerPair : aLayerPairs )
         {
             const PCB_LAYER_ID refLayer = layerPair.first;
             const PCB_LAYER_ID targetLayer = layerPair.second;
 
             for( ITEM_WITH_SHAPE* refItem : aRefTree->OnLayer( refLayer ) )
             {
                 BOX2I box = refItem->shape->BBox();
                 box.Inflate( aMaxClearance );
 
                 int min[2] = { box.GetX(),     box.GetY() };
                 int max[2] = { box.GetRight(), box.GetBottom() };
 
                 auto visit =
                         [&]( ITEM_WITH_SHAPE* aItemToTest ) -> bool
                         {
                             // don't collide items against themselves
                             if( aItemToTest->parent == refItem->parent )
                                 return true;
 
                             pairsToVisit.emplace_back( layerPair, refItem, aItemToTest );
                             return true;
                         };
 
                 this->m_tree[targetLayer]->Search( min, max, visit );
             };
         }
 
         // keep track of BOARD_ITEMs pairs that have been already found to collide (some items
         // might be build of COMPOUND/triangulated shapes and a single subshape collision
         // means we have a hit)
         std::map< std::pair<BOARD_ITEM*, BOARD_ITEM*>, int> collidingCompounds;
 
         int progress = 0;
         int count = pairsToVisit.size();
 
         for( const PAIR_INFO& pair : pairsToVisit )
         {
             if( !aProgressReporter( progress++, count ) )
                 break;
 
             BOARD_ITEM* a = pair.refItem->parent;
             BOARD_ITEM* b = pair.testItem->parent;
 
             // store canonical order so we don't collide in both directions (a:b and b:a)
             if( static_cast<void*>( a ) > static_cast<void*>( b ) )
                 std::swap( a, b );
 
             // don't report multiple collisions for compound or triangulated shapes
             if( collidingCompounds.count( { a, b } ) )
                 continue;
 
             bool collisionDetected = false;
 
             if( !aVisitor( pair.layerPair, pair.refItem, pair.testItem, &collisionDetected ) )
                 break;
 
             if( collisionDetected )
                 collidingCompounds[ { a, b } ] = 1;
         }
 
         return 0;
     }

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

Returns the number of items in the tree.

Returns: number of elements in the tree;

Definition at line 404 of file drc_rtree.h.

     {
         return m_count;
     }

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 471 of file drc_rtree.h.

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

◆ m_tree

drc_rtree* DRC_RTREE::m_tree[PCB_LAYER_ID_COUNT]

private

Definition at line 470 of file drc_rtree.h.

Referenced by CheckColliding(), clear(), DRC_RTREE(), Insert(), OnLayer(), Overlapping(), QueryColliding(), QueryCollidingPairs(), and ~DRC_RTREE().

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

drc_rtree.h

Classes

Public Types

Public Member Functions

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

◆ drc_rtree

◆ iterator

◆ LAYER_PAIR

Constructor & Destructor Documentation

◆ DRC_RTREE()

◆ ~DRC_RTREE()

Member Function Documentation

◆ CheckColliding()

◆ clear()

◆ empty()

◆ Insert()

◆ OnLayer()

◆ Overlapping() [1/2]

◆ Overlapping() [2/2]

◆ QueryColliding() [1/2]

◆ QueryColliding() [2/2]

◆ QueryCollidingPairs()

◆ size()

Member Data Documentation

◆ m_count

◆ m_tree