![]() |
KiCad PCB EDA Suite
|
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_ID > | LAYER_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_rtree * | m_tree [PCB_LAYER_ID_COUNT] |
size_t | m_count |
Implement an R-tree for fast spatial and layer indexing of connectable items.
Non-owning.
Definition at line 46 of file drc_rtree.h.
|
private |
Definition at line 67 of file drc_rtree.h.
using DRC_RTREE::iterator = typename drc_rtree::Iterator |
Definition at line 467 of file drc_rtree.h.
typedef std::pair<PCB_LAYER_ID, PCB_LAYER_ID> DRC_RTREE::LAYER_PAIR |
Definition at line 363 of file drc_rtree.h.
|
inline |
|
inline |
|
inline |
Definition at line 146 of file drc_rtree.h.
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().
|
inline |
Remove all items from the RTree.
Definition at line 138 of file drc_rtree.h.
References m_count, and m_tree.
Referenced by DRC_TEST_PROVIDER_HOLE_TO_HOLE::Run(), and DRC_TEST_PROVIDER_COPPER_CLEARANCE::Run().
|
inline |
Definition at line 462 of file drc_rtree.h.
References m_count.
|
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.
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().
|
inline |
|
inline |
|
inline |
|
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.
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().
|
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.
References SHAPE::Collide(), EDA_RECT::GetBottom(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), EDA_RECT::Inflate(), and m_tree.
|
inline |
Quicker version of above that just reports a raw yes/no.
Definition at line 311 of file drc_rtree.h.
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().
|
inline |
Definition at line 378 of file drc_rtree.h.
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().
|
inline |
Return the number of items in the tree.
Definition at line 457 of file drc_rtree.h.
References m_count.
Referenced by DRC_TEST_PROVIDER_SILK_CLEARANCE::Run().
|
private |
Definition at line 524 of file drc_rtree.h.
Referenced by clear(), DRC_RTREE(), empty(), Insert(), and size().
|
private |
Definition at line 523 of file drc_rtree.h.
Referenced by CheckColliding(), clear(), DRC_RTREE(), Insert(), OnLayer(), Overlapping(), QueryColliding(), QueryCollidingPairs(), and ~DRC_RTREE().