KiCad PCB EDA Suite
Loading...
Searching...
No Matches
connectivity_items.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) 2013-2017 CERN
5 * Copyright (C) 2018-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Maciej Suminski <[email protected]>
8 * @author Tomasz Wlostowski <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28
29#ifndef PCBNEW_CONNECTIVITY_ITEMS_H
30#define PCBNEW_CONNECTIVITY_ITEMS_H
31
32#include <board.h>
33#include <pad.h>
34#include <footprint.h>
35#include <pcb_track.h>
36#include <pcb_shape.h>
37#include <zone.h>
38
40
41#include <memory>
42#include <algorithm>
43#include <functional>
44#include <vector>
45#include <deque>
46
49
50class CN_ITEM;
51class CN_CLUSTER;
52
53
59{
60public:
61 CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem ) :
62 m_pos( aPos ),
63 m_item( aItem ),
64 m_tag( -1 ),
65 m_noline( false )
66 { }
67
68 bool Valid() const;
69
70 bool Dirty() const;
71
72 CN_ITEM* Item() const { return m_item; }
73 void SetItem( CN_ITEM* aItem ) { m_item = aItem; }
74
76
77 const VECTOR2I& Pos() const { return m_pos; }
78
79 void Move( const VECTOR2I& aPos )
80 {
81 m_pos += aPos;
82 }
83
84 unsigned int Dist( const CN_ANCHOR& aSecond )
85 {
86 return ( m_pos - aSecond.Pos() ).EuclideanNorm();
87 }
88
90 int GetTag() const { return m_tag; }
91 void SetTag( int aTag ) { m_tag = aTag; }
92
94 const bool& GetNoLine() const { return m_noline; }
95 void SetNoLine( bool aEnable ) { m_noline = aEnable; }
96
97 const std::shared_ptr<CN_CLUSTER>& GetCluster() const { return m_cluster; }
98 void SetCluster( std::shared_ptr<CN_CLUSTER>& aCluster ) { m_cluster = aCluster; }
99
107 bool IsDangling() const;
108
112 int ConnectedItemsCount() const;
113
114 // Tag used for unconnected items.
115 static const int TAG_UNCONNECTED = -1;
116
117private:
120 int m_tag;
121 bool m_noline;
122
123 std::shared_ptr<CN_CLUSTER> m_cluster;
124};
125
126
127
133{
134public:
135 void Dump();
136
137 CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
138 {
139 m_parent = aParent;
140 m_canChangeNet = aCanChangeNet;
141 m_visited = false;
142 m_valid = true;
143 m_dirty = true;
144 m_anchors.reserve( std::max( 6, aAnchorCount ) );
145 m_start_layer = 0;
146 m_end_layer = std::numeric_limits<int>::max();
147 m_connected.reserve( 8 );
148 }
149
150 virtual ~CN_ITEM()
151 {
152 for( const std::shared_ptr<CN_ANCHOR>& anchor : m_anchors )
153 anchor->SetItem( nullptr );
154 };
155
156 std::shared_ptr<CN_ANCHOR> AddAnchor( const VECTOR2I& aPos )
157 {
158 m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
159 return m_anchors.at( m_anchors.size() - 1 );
160 }
161
162 std::vector<std::shared_ptr<CN_ANCHOR>>& Anchors() { return m_anchors; }
163
164 void SetValid( bool aValid ) { m_valid = aValid; }
165 bool Valid() const { return m_valid; }
166
167 void SetDirty( bool aDirty ) { m_dirty = aDirty; }
168 bool Dirty() const { return m_dirty; }
169
173 void SetLayers( int aStartLayer, int aEndLayer )
174 {
175 // B_Cu is nominally layer 2 but we reset it to INT_MAX to ensure that it is
176 // always greater than any other layer in the RTree
177 if( aStartLayer == B_Cu )
178 aStartLayer = std::numeric_limits<int>::max();
179
180 if( aEndLayer == B_Cu )
181 aEndLayer = std::numeric_limits<int>::max();
182
183 m_start_layer = aStartLayer;
184 m_end_layer = aEndLayer;
185 }
186
190 void SetLayer( int aLayer ) { SetLayers( aLayer, aLayer ); }
191
195 int StartLayer() const { return m_start_layer; }
196 int EndLayer() const { return m_end_layer; }
197
203 virtual int Layer() const
204 {
205 return StartLayer();
206 }
207
213 {
214 int layer = Layer();
215
216 if( layer == std::numeric_limits<int>::max() )
217 layer = B_Cu;
218
219 return ToLAYER_ID( layer );
220 }
221
222 const BOX2I& BBox()
223 {
224 if( m_dirty && m_valid )
226
227 return m_bbox;
228 }
229
231
232 const std::vector<CN_ITEM*>& ConnectedItems() const { return m_connected; }
233 void ClearConnections() { m_connected.clear(); }
234
235 void SetVisited( bool aVisited ) { m_visited = aVisited; }
236 bool Visited() const { return m_visited; }
237
238 bool CanChangeNet() const { return m_canChangeNet; }
239
240 void Connect( CN_ITEM* b )
241 {
242 std::lock_guard<std::mutex> lock( m_listLock );
243
244 auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
245
246 if( i != m_connected.end() && *i == b )
247 return;
248
249 m_connected.insert( i, b );
250 }
251
252 void RemoveInvalidRefs();
253
254 virtual int AnchorCount() const;
255 virtual const VECTOR2I GetAnchor( int n ) const;
256
257 int Net() const
258 {
259 return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
260 }
261
262protected:
263 bool m_dirty;
268
269private:
271
272 std::vector<CN_ITEM*> m_connected;
273 std::vector<std::shared_ptr<CN_ANCHOR>> m_anchors;
274
276
278 bool m_valid;
279
280 std::mutex m_listLock;
281};
282
283
284/*
285 * Represents a single outline of a zone fill on a particular layer. \a aSubpolyIndex indicates
286 * which outline in the fill's SHAPE_POLY_SET.
287 */
288class CN_ZONE_LAYER : public CN_ITEM
289{
290public:
291 CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex ) :
292 CN_ITEM( aParent, false ),
293 m_zone( aParent ),
294 m_subpolyIndex( aSubpolyIndex ),
295 m_layer( aLayer )
296 {
297 m_fillPoly = aParent->GetFilledPolysList( aLayer );
298 SetLayers( aLayer, aLayer );
299 }
300
302 {
303 if( m_zone->IsTeardropArea() )
304 return;
305
306 for( unsigned int ii = 0; ii < m_fillPoly->TriangulatedPolyCount(); ++ii )
307 {
308 const auto* triangleSet = m_fillPoly->TriangulatedPolygon( ii );
309
310 if( triangleSet->GetSourceOutlineIndex() != m_subpolyIndex )
311 continue;
312
313 for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : triangleSet->Triangles() )
314 {
315 BOX2I bbox = tri.BBox();
316 const int mmin[2] = { bbox.GetX(), bbox.GetY() };
317 const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
318
319 m_rTree.Insert( mmin, mmax, &tri );
320 }
321 }
322 }
323
324 int SubpolyIndex() const { return m_subpolyIndex; }
325
326 PCB_LAYER_ID GetLayer() const { return m_layer; }
327
328 bool ContainsPoint( const VECTOR2I& p ) const
329 {
330 if( m_zone->IsTeardropArea() )
331 return m_fillPoly->Outline( m_subpolyIndex ).Collide( p ) ;
332
333 int min[2] = { p.x, p.y };
334 int max[2] = { p.x, p.y };
335 bool collision = false;
336
337 auto visitor =
338 [&]( const SHAPE* aShape ) -> bool
339 {
340 if( aShape->Collide( p ) )
341 {
342 collision = true;
343 return false;
344 }
345
346 return true;
347 };
348
349 m_rTree.Search( min, max, visitor );
350
351 return collision;
352 }
353
355
356 virtual int AnchorCount() const override;
357 virtual const VECTOR2I GetAnchor( int n ) const override;
358
360 {
361 return m_fillPoly->Outline( m_subpolyIndex );
362 }
363
364 bool Collide( SHAPE* aRefShape ) const
365 {
366 if( m_zone->IsTeardropArea() )
367 return m_fillPoly->Collide( aRefShape );
368
369 BOX2I bbox = aRefShape->BBox();
370 int min[2] = { bbox.GetX(), bbox.GetY() };
371 int max[2] = { bbox.GetRight(), bbox.GetBottom() };
372 bool collision = false;
373
374 auto visitor =
375 [&]( const SHAPE* aShape ) -> bool
376 {
377 if( aRefShape->Collide( aShape ) )
378 {
379 collision = true;
380 return false;
381 }
382
383 return true;
384 };
385
386 m_rTree.Search( min, max, visitor );
387
388 return collision;
389 }
390
391 bool HasSingleConnection();
392
393private:
397 std::shared_ptr<SHAPE_POLY_SET> m_fillPoly;
398 RTree<const SHAPE*, int, 2, double> m_rTree;
399};
400
401
402
403
405{
406public:
408 {
409 m_dirty = false;
410 m_hasInvalid = false;
411 }
412
413 void Clear()
414 {
415 for( CN_ITEM* item : m_items )
416 delete item;
417
418 m_items.clear();
420 }
421
422 std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
423 std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
424
425 std::vector<CN_ITEM*>::const_iterator begin() const { return m_items.begin(); }
426 std::vector<CN_ITEM*>::const_iterator end() const { return m_items.end(); }
427
428 CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
429
430 template <class T>
431 void FindNearby( CN_ITEM* aItem, T aFunc )
432 {
433 m_index.Query( aItem->BBox(), aItem->StartLayer(), aItem->EndLayer(), aFunc );
434 }
435
436 void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
437
438 void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
439 bool IsDirty() const { return m_dirty; }
440
441 void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
442
444 {
445 for( CN_ITEM* item : m_items )
446 item->SetDirty( false );
447
448 SetDirty( false );
449 }
450
451 int Size() const { return m_items.size(); }
452
453 CN_ITEM* Add( PAD* pad );
454 CN_ITEM* Add( PCB_TRACK* track );
455 CN_ITEM* Add( PCB_ARC* track );
456 CN_ITEM* Add( PCB_VIA* via );
457 CN_ITEM* Add( CN_ZONE_LAYER* zitem );
458 CN_ITEM* Add( PCB_SHAPE* shape );
459
460 const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
461
462protected:
463 void addItemtoTree( CN_ITEM* item )
464 {
465 m_index.Insert( item );
466 }
467
468protected:
469 std::vector<CN_ITEM*> m_items;
470
471private:
475};
476
477
479{
480public:
481 CN_CLUSTER();
482 ~CN_CLUSTER();
483
484 bool HasValidNet() const { return m_originNet > 0; }
485 int OriginNet() const { return m_originNet; }
486
487 wxString OriginNetName() const;
488
489 bool Contains( const CN_ITEM* aItem );
490 bool Contains( const BOARD_CONNECTED_ITEM* aItem );
491 void Dump();
492
493 int Size() const { return m_items.size(); }
494
495 bool IsOrphaned() const
496 {
497 return m_originPad == nullptr;
498 }
499
500 bool IsConflicting() const { return m_conflicting; }
501
502 void Add( CN_ITEM* item );
503
504 std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
505 std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
506
507private:
511 std::vector<CN_ITEM*> m_items;
512 std::unordered_map<int, int> m_netRanks;
513};
514
515
516
517#endif /* PCBNEW_CONNECTIVITY_ITEMS_H */
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
constexpr coord_type GetY() const
Definition: box2.h:208
constexpr coord_type GetX() const
Definition: box2.h:207
constexpr coord_type GetRight() const
Definition: box2.h:217
constexpr coord_type GetBottom() const
Definition: box2.h:222
CN_ANCHOR represents a physical location that can be connected: a pad or a track/arc/via endpoint.
void SetTag(int aTag)
CN_ITEM * m_item
Pad or track/arc/via owning the anchor.
static const int TAG_UNCONNECTED
VECTOR2I m_pos
Position of the anchor.
void Move(const VECTOR2I &aPos)
bool Valid() const
void SetNoLine(bool aEnable)
int ConnectedItemsCount() const
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
const bool & GetNoLine() const
int GetTag() const
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
unsigned int Dist(const CN_ANCHOR &aSecond)
void SetCluster(std::shared_ptr< CN_CLUSTER > &aCluster)
const VECTOR2I & Pos() const
bool Dirty() const
CN_ITEM * Item() const
int m_tag
Tag for quick connection resolution.
bool m_noline
Whether it the node can be a target for ratsnest lines.
BOARD_CONNECTED_ITEM * Parent() const
bool IsDangling() const
The anchor point is dangling if the parent is a track and this anchor point is not connected to anoth...
void SetItem(CN_ITEM *aItem)
int Size() const
std::vector< CN_ITEM * >::iterator end()
std::vector< CN_ITEM * > m_items
bool IsConflicting() const
bool IsOrphaned() const
bool Contains(const CN_ITEM *aItem)
void Add(CN_ITEM *item)
CN_ITEM * m_originPad
std::vector< CN_ITEM * >::iterator begin()
wxString OriginNetName() const
std::unordered_map< int, int > m_netRanks
bool HasValidNet() const
int OriginNet() const
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
virtual int Layer() const
Return the item's layer, for single-layered items only.
void Connect(CN_ITEM *b)
virtual ~CN_ITEM()
const BOX2I & BBox()
virtual int AnchorCount() const
void RemoveInvalidRefs()
bool m_visited
visited flag for the BFS scan
std::vector< CN_ITEM * > m_connected
list of physically touching items
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
int m_start_layer
start layer of the item N.B. B_Cu is set to INT_MAX
void SetValid(bool aValid)
BOARD_CONNECTED_ITEM * m_parent
int m_end_layer
end layer of the item N.B. B_Cu is set to INT_MAX
bool Valid() const
int StartLayer() const
Return the contiguous set of layers spanned by the item.
std::shared_ptr< CN_ANCHOR > AddAnchor(const VECTOR2I &aPos)
void SetLayers(int aStartLayer, int aEndLayer)
Set the layers spanned by the item to aStartLayer and aEndLayer.
void ClearConnections()
BOX2I m_bbox
bounding box for the item
virtual const VECTOR2I GetAnchor(int n) const
PCB_LAYER_ID GetBoardLayer() const
When using CN_ITEM layers to compare against board items, use this function which correctly remaps th...
bool m_canChangeNet
can the net propagator modify the netcode?
void SetDirty(bool aDirty)
bool CanChangeNet() const
bool m_dirty
used to identify recently added item not yet scanned into the connectivity search
CN_ITEM(BOARD_CONNECTED_ITEM *aParent, bool aCanChangeNet, int aAnchorCount=2)
int EndLayer() const
void SetLayer(int aLayer)
Set the layers spanned by the item to a single layer aLayer.
void SetVisited(bool aVisited)
std::vector< std::shared_ptr< CN_ANCHOR > > m_anchors
bool m_valid
used to identify garbage items (we use lazy removal)
bool Dirty() const
std::vector< std::shared_ptr< CN_ANCHOR > > & Anchors()
BOARD_CONNECTED_ITEM * Parent() const
bool Visited() const
std::mutex m_listLock
mutex protecting this item's connected_items set to
CN_RTREE< CN_ITEM * > m_index
CN_ITEM * operator[](int aIndex)
CN_ITEM * Add(PAD *pad)
std::vector< CN_ITEM * >::iterator begin()
std::vector< CN_ITEM * >::const_iterator begin() const
void SetDirty(bool aDirty=true)
int Size() const
std::vector< CN_ITEM * >::const_iterator end() const
bool IsDirty() const
std::vector< CN_ITEM * >::iterator end()
std::vector< CN_ITEM * > m_items
void FindNearby(CN_ITEM *aItem, T aFunc)
void ClearDirtyFlags()
void addItemtoTree(CN_ITEM *item)
void SetHasInvalid(bool aInvalid=true)
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
void Query(const BOX2I &aBounds, int aStartLayer, int aEndLayer, Visitor &aVisitor) const
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
virtual int AnchorCount() const override
const SHAPE_LINE_CHAIN & GetOutline() const
CN_ZONE_LAYER(ZONE *aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex)
virtual const VECTOR2I GetAnchor(int n) const override
PCB_LAYER_ID GetLayer() const
RTree< const SHAPE *, int, 2, double > m_rTree
bool Collide(SHAPE *aRefShape) const
int SubpolyIndex() const
PCB_LAYER_ID m_layer
PCB_LAYER_ID GetLayer()
std::shared_ptr< SHAPE_POLY_SET > m_fillPoly
bool ContainsPoint(const VECTOR2I &p) const
virtual const BOX2I GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:77
Definition: pad.h:54
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
An abstract shape on 2D plane.
Definition: shape.h:126
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:181
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
Handle a list of polygons defining a copper zone.
Definition: zone.h:73
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:617
bool IsTeardropArea() const
Definition: zone.h:696
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
@ B_Cu
Definition: layer_ids.h:65
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:810