KiCad PCB EDA Suite
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-2022 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 <zone.h>
37
39
40#include <memory>
41#include <algorithm>
42#include <functional>
43#include <vector>
44#include <deque>
45#include <intrusive_list.h>
46
49
50class CN_ITEM;
51class CN_CLUSTER;
52
53
59{
60public:
62 {
63 m_item = nullptr;
64 }
65
66 CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem )
67 {
68 m_pos = aPos;
69 m_item = aItem;
70 assert( m_item );
71 }
72
73 bool Valid() const;
74
75 CN_ITEM* Item() const
76 {
77 return m_item;
78 }
79
81
82 const VECTOR2I& Pos() const
83 {
84 return m_pos;
85 }
86
87 void Move( const VECTOR2I& aPos )
88 {
89 m_pos += aPos;
90 }
91
92 const unsigned int Dist( const CN_ANCHOR& aSecond )
93 {
94 return ( m_pos - aSecond.Pos() ).EuclideanNorm();
95 }
96
98 inline int GetTag() const
99 {
100 return m_tag;
101 }
102
104 inline void SetTag( int aTag )
105 {
106 m_tag = aTag;
107 }
108
110 inline void SetNoLine( bool aEnable )
111 {
112 m_noline = aEnable;
113 }
114
116 inline const bool& GetNoLine() const
117 {
118 return m_noline;
119 }
120
121 inline void SetCluster( std::shared_ptr<CN_CLUSTER>& aCluster )
122 {
123 m_cluster = aCluster;
124 }
125
126 inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
127 {
128 return m_cluster;
129 }
130
138 bool IsDangling() const;
139
143 int ConnectedItemsCount() const;
144
145 // Tag used for unconnected items.
146 static const int TAG_UNCONNECTED = -1;
147
148private:
150 CN_ITEM* m_item = nullptr;
151 int m_tag = -1;
152 bool m_noline = false;
153
154 std::shared_ptr<CN_CLUSTER> m_cluster;
155};
156
157
158
164{
165public:
166 void Dump();
167
168 CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
169 {
170 m_parent = aParent;
171 m_canChangeNet = aCanChangeNet;
172 m_visited = false;
173 m_valid = true;
174 m_dirty = true;
175 m_anchors.reserve( std::max( 6, aAnchorCount ) );
177 m_connected.reserve( 8 );
178 }
179
180 virtual ~CN_ITEM() {};
181
182 void AddAnchor( const VECTOR2I& aPos )
183 {
184 m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
185 }
186
187 std::vector<std::shared_ptr<CN_ANCHOR>>& Anchors() { return m_anchors; }
188
189 void SetValid( bool aValid ) { m_valid = aValid; }
190 bool Valid() const { return m_valid; }
191
192 void SetDirty( bool aDirty ) { m_dirty = aDirty; }
193 bool Dirty() const { return m_dirty; }
194
198 void SetLayers( const LAYER_RANGE& aLayers ) { m_layers = aLayers; }
199
203 void SetLayer( int aLayer ) { m_layers = LAYER_RANGE( aLayer, aLayer ); }
204
208 const LAYER_RANGE& Layers() const { return m_layers; }
209
213 virtual int Layer() const
214 {
215 return Layers().Start();
216 }
217
218 const BOX2I& BBox()
219 {
220 if( m_dirty && m_valid )
222
223 return m_bbox;
224 }
225
227
228 const std::vector<CN_ITEM*>& ConnectedItems() const { return m_connected; }
229 void ClearConnections() { m_connected.clear(); }
230
231 void SetVisited( bool aVisited ) { m_visited = aVisited; }
232 bool Visited() const { return m_visited; }
233
234 bool CanChangeNet() const { return m_canChangeNet; }
235
236 void Connect( CN_ITEM* b )
237 {
238 std::lock_guard<std::mutex> lock( m_listLock );
239
240 auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
241
242 if( i != m_connected.end() && *i == b )
243 return;
244
245 m_connected.insert( i, b );
246 }
247
248 void RemoveInvalidRefs();
249
250 virtual int AnchorCount() const;
251 virtual const VECTOR2I GetAnchor( int n ) const;
252
253 int GetAnchorItemCount() const { return m_anchors.size(); }
254 std::shared_ptr<CN_ANCHOR> GetAnchorItem( int n ) const { return m_anchors[n]; }
255
256 int Net() const
257 {
258 return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
259 }
261protected:
262 bool m_dirty;
266
267private:
269
270 std::vector<CN_ITEM*> m_connected;
271 std::vector<std::shared_ptr<CN_ANCHOR>> m_anchors;
272
274
276 bool m_valid;
277
278 std::mutex m_listLock;
279};
280
281
282typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
283
284
285class CN_ZONE_LAYER : public CN_ITEM
286{
287public:
288 CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex ) :
289 CN_ITEM( aParent, false ),
290 m_subpolyIndex( aSubpolyIndex ),
291 m_layer( aLayer )
292 {
293 m_triangulatedPoly = aParent->GetFilledPolysList( aLayer );
294 SetLayers( aLayer );
295 }
296
298 {
299 for( unsigned int ii = 0; ii < m_triangulatedPoly->TriangulatedPolyCount(); ++ii )
300 {
301 const auto* triangleSet = m_triangulatedPoly->TriangulatedPolygon( ii );
302
303 if( triangleSet->GetSourceOutlineIndex() != m_subpolyIndex )
304 continue;
305
306 for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : triangleSet->Triangles() )
307 {
308 BOX2I bbox = tri.BBox();
309 const int mmin[2] = { bbox.GetX(), bbox.GetY() };
310 const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
311
312 m_rTree.Insert( mmin, mmax, &tri );
313 }
314 }
315 }
316
317 int SubpolyIndex() const { return m_subpolyIndex; }
318
319 PCB_LAYER_ID GetLayer() const { return m_layer; }
320
321 bool ContainsPoint( const VECTOR2I& p ) const
322 {
323 int min[2] = { p.x, p.y };
324 int max[2] = { p.x, p.y };
325 bool collision = false;
326
327 auto visitor =
328 [&]( const SHAPE* aShape ) -> bool
329 {
330 if( aShape->Collide( p ) )
331 {
332 collision = true;
333 return false;
334 }
335
336 return true;
337 };
338
339 m_rTree.Search( min, max, visitor );
340
341 return collision;
342 }
343
345
346 virtual int AnchorCount() const override;
347 virtual const VECTOR2I GetAnchor( int n ) const override;
348
350 {
351 return m_triangulatedPoly->Outline( m_subpolyIndex );
352 }
353
355 {
356 VECTOR2I closest;
357
358 m_triangulatedPoly->SquaredDistanceToPolygon( aPt, m_subpolyIndex, &closest );
359
360 return closest;
361 }
362
363 bool Collide( SHAPE* aRefShape ) const
364 {
365 BOX2I bbox = aRefShape->BBox();
366 int min[2] = { bbox.GetX(), bbox.GetY() };
367 int max[2] = { bbox.GetRight(), bbox.GetBottom() };
368 bool collision = false;
369
370 auto visitor =
371 [&]( const SHAPE* aShape ) -> bool
372 {
373 if( aRefShape->Collide( aShape ) )
374 {
375 collision = true;
376 return false;
377 }
378
379 return true;
380 };
381
382 m_rTree.Search( min, max, visitor );
383
384 return collision;
385 }
386
387private:
390 std::shared_ptr<SHAPE_POLY_SET> m_triangulatedPoly;
391 RTree<const SHAPE*, int, 2, double> m_rTree;
392};
393
394
395
396
398{
399protected:
400 std::vector<CN_ITEM*> m_items;
401
402 void addItemtoTree( CN_ITEM* item )
403 {
404 m_index.Insert( item );
405 }
406
407public:
409 {
410 m_dirty = false;
411 m_hasInvalid = false;
412 }
413
414 void Clear()
415 {
416 for( CN_ITEM* item : m_items )
417 delete item;
418
419 m_items.clear();
421 }
422
423 using ITER = decltype( m_items )::iterator;
424 using CONST_ITER = decltype( m_items )::const_iterator;
425
426 ITER begin() { return m_items.begin(); };
427 ITER end() { return m_items.end(); };
428
429 CONST_ITER begin() const { return m_items.begin(); }
430 CONST_ITER end() const { return m_items.end(); }
431
432 CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
433
434 template <class T>
435 void FindNearby( CN_ITEM* aItem, T aFunc )
436 {
437 m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
438 }
439
440 void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
441
442 void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
443 bool IsDirty() const { return m_dirty; }
444
445 void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
446
448 {
449 for( CN_ITEM* item : m_items )
450 item->SetDirty( false );
451
452 SetDirty( false );
453 }
454
455 int Size() const
456 {
457 return m_items.size();
458 }
459
460 CN_ITEM* Add( PAD* pad );
461
462 CN_ITEM* Add( PCB_TRACK* track );
463
464 CN_ITEM* Add( PCB_ARC* track );
465
466 CN_ITEM* Add( PCB_VIA* via );
467
468 CN_ITEM* Add( CN_ZONE_LAYER* zitem );
469
470 const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
471
472private:
476};
477
478
480{
481private:
485 std::vector<CN_ITEM*> m_items;
486 std::unordered_map<int, int> m_netRanks;
487
488public:
489 CN_CLUSTER();
490 ~CN_CLUSTER();
491
492 bool HasValidNet() const { return m_originNet > 0; }
493 int OriginNet() const { return m_originNet; }
494
495 wxString OriginNetName() const;
496
497 bool Contains( const CN_ITEM* aItem );
498 bool Contains( const BOARD_CONNECTED_ITEM* aItem );
499 void Dump();
500
501 int Size() const { return m_items.size(); }
502
503 bool IsOrphaned() const { return m_originPad == nullptr; }
504
505 bool IsConflicting() const { return m_conflicting; }
506
507 void Add( CN_ITEM* item );
508
509 using ITER = decltype(m_items)::iterator;
510
511 ITER begin() { return m_items.begin(); };
512 ITER end() { return m_items.end(); };
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,...
coord_type GetY() const
Definition: box2.h:181
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetBottom() const
Definition: box2.h:190
CN_ANCHOR represents a physical location that can be connected: a pad or a track/arc/via endpoint.
void SetTag(int aTag)
Decide whether this node can be a ratsnest line target.
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)
Return true if this node can be a target for ratsnest lines.
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
Set tag, common identifier for connected nodes.
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
void SetCluster(std::shared_ptr< CN_CLUSTER > &aCluster)
const VECTOR2I & Pos() const
CN_ITEM * Item() const
int m_tag
Tag for quick connection resolution.
const unsigned int Dist(const CN_ANCHOR &aSecond)
Return tag, common identifier for connected nodes.
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...
int Size() const
std::vector< CN_ITEM * > m_items
decltype(m_items)::iterator ITER
bool IsConflicting() const
bool IsOrphaned() const
bool Contains(const CN_ITEM *aItem)
void Add(CN_ITEM *item)
CN_ITEM * m_originPad
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 SetLayers(const LAYER_RANGE &aLayers)
Set the layers spanned by the item to aLayers.
void Connect(CN_ITEM *b)
virtual ~CN_ITEM()
const BOX2I & BBox()
virtual int AnchorCount() const
void RemoveInvalidRefs()
std::shared_ptr< CN_ANCHOR > GetAnchorItem(int n) const
bool m_visited
visited flag for the BFS scan
std::vector< CN_ITEM * > m_connected
list of physically touching items
int GetAnchorItemCount() const
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
allow parallel connection threads
void SetValid(bool aValid)
BOARD_CONNECTED_ITEM * m_parent
bool Valid() const
void ClearConnections()
BOX2I m_bbox
bounding box for the item
virtual const VECTOR2I GetAnchor(int n) const
LAYER_RANGE m_layers
layer range over which the item exists
bool m_canChangeNet
can the net propagator modify the netcode?
void SetDirty(bool aDirty)
void AddAnchor(const VECTOR2I &aPos)
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)
void SetLayer(int aLayer)
Set the layers spanned by the item to a single layer aLayer.
void SetVisited(bool aVisited)
const LAYER_RANGE & Layers() const
Return the contiguous set of layers spanned by the item.
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
CONST_ITER end() const
CN_ITEM * operator[](int aIndex)
decltype(m_items)::const_iterator CONST_ITER
decltype(m_items)::iterator ITER
CN_ITEM * Add(PAD *pad)
void SetDirty(bool aDirty=true)
int Size() const
bool IsDirty() const
CONST_ITER begin() const
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)
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
void Query(const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor) const
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
VECTOR2I ClosestPoint(const VECTOR2I aPt)
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
std::shared_ptr< SHAPE_POLY_SET > m_triangulatedPoly
PCB_LAYER_ID m_layer
PCB_LAYER_ID GetLayer()
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:74
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
int Start() const
Definition: pns_layerset.h:82
Definition: pad.h:58
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:123
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:178
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:57
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:596
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
@ PCB_LAYER_ID_COUNT
Definition: layer_ids.h:137