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 std::shared_ptr<CN_ANCHOR> AddAnchor( const VECTOR2I& aPos )
183 {
184 m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
185 return m_anchors.at( m_anchors.size() - 1 );
186 }
187
188 std::vector<std::shared_ptr<CN_ANCHOR>>& Anchors() { return m_anchors; }
189
190 void SetValid( bool aValid ) { m_valid = aValid; }
191 bool Valid() const { return m_valid; }
192
193 void SetDirty( bool aDirty ) { m_dirty = aDirty; }
194 bool Dirty() const { return m_dirty; }
195
199 void SetLayers( const LAYER_RANGE& aLayers ) { m_layers = aLayers; }
200
204 void SetLayer( int aLayer ) { m_layers = LAYER_RANGE( aLayer, aLayer ); }
205
209 const LAYER_RANGE& Layers() const { return m_layers; }
210
214 virtual int Layer() const
215 {
216 return Layers().Start();
217 }
218
219 const BOX2I& BBox()
220 {
221 if( m_dirty && m_valid )
223
224 return m_bbox;
225 }
226
228
229 const std::vector<CN_ITEM*>& ConnectedItems() const { return m_connected; }
230 void ClearConnections() { m_connected.clear(); }
231
232 void SetVisited( bool aVisited ) { m_visited = aVisited; }
233 bool Visited() const { return m_visited; }
234
235 bool CanChangeNet() const { return m_canChangeNet; }
236
237 void Connect( CN_ITEM* b )
238 {
239 std::lock_guard<std::mutex> lock( m_listLock );
240
241 auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
242
243 if( i != m_connected.end() && *i == b )
244 return;
245
246 m_connected.insert( i, b );
247 }
248
249 void RemoveInvalidRefs();
250
251 virtual int AnchorCount() const;
252 virtual const VECTOR2I GetAnchor( int n ) const;
253
254 int GetAnchorItemCount() const { return m_anchors.size(); }
255 std::shared_ptr<CN_ANCHOR> GetAnchorItem( int n ) const { return m_anchors[n]; }
256
257 int Net() const
258 {
259 return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
260 }
262protected:
263 bool m_dirty;
267
268private:
270
271 std::vector<CN_ITEM*> m_connected;
272 std::vector<std::shared_ptr<CN_ANCHOR>> m_anchors;
273
275
277 bool m_valid;
278
279 std::mutex m_listLock;
280};
281
282
283typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
284
285
286class CN_ZONE_LAYER : public CN_ITEM
287{
288public:
289 CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex ) :
290 CN_ITEM( aParent, false ),
291 m_subpolyIndex( aSubpolyIndex ),
292 m_layer( aLayer )
293 {
294 m_triangulatedPoly = aParent->GetFilledPolysList( aLayer );
295 SetLayers( aLayer );
296 }
297
299 {
300 for( unsigned int ii = 0; ii < m_triangulatedPoly->TriangulatedPolyCount(); ++ii )
301 {
302 const auto* triangleSet = m_triangulatedPoly->TriangulatedPolygon( ii );
303
304 if( triangleSet->GetSourceOutlineIndex() != m_subpolyIndex )
305 continue;
306
307 for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : triangleSet->Triangles() )
308 {
309 BOX2I bbox = tri.BBox();
310 const int mmin[2] = { bbox.GetX(), bbox.GetY() };
311 const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
312
313 m_rTree.Insert( mmin, mmax, &tri );
314 }
315 }
316 }
317
318 int SubpolyIndex() const { return m_subpolyIndex; }
319
320 PCB_LAYER_ID GetLayer() const { return m_layer; }
321
322 bool ContainsPoint( const VECTOR2I& p ) const
323 {
324 int min[2] = { p.x, p.y };
325 int max[2] = { p.x, p.y };
326 bool collision = false;
327
328 auto visitor =
329 [&]( const SHAPE* aShape ) -> bool
330 {
331 if( aShape->Collide( p ) )
332 {
333 collision = true;
334 return false;
335 }
336
337 return true;
338 };
339
340 m_rTree.Search( min, max, visitor );
341
342 return collision;
343 }
344
346
347 virtual int AnchorCount() const override;
348 virtual const VECTOR2I GetAnchor( int n ) const override;
349
351 {
352 return m_triangulatedPoly->Outline( m_subpolyIndex );
353 }
354
356 {
357 VECTOR2I closest;
358
359 m_triangulatedPoly->SquaredDistanceToPolygon( aPt, m_subpolyIndex, &closest );
360
361 return closest;
362 }
363
364 bool Collide( SHAPE* aRefShape ) const
365 {
366 BOX2I bbox = aRefShape->BBox();
367 int min[2] = { bbox.GetX(), bbox.GetY() };
368 int max[2] = { bbox.GetRight(), bbox.GetBottom() };
369 bool collision = false;
370
371 auto visitor =
372 [&]( const SHAPE* aShape ) -> bool
373 {
374 if( aRefShape->Collide( aShape ) )
375 {
376 collision = true;
377 return false;
378 }
379
380 return true;
381 };
382
383 m_rTree.Search( min, max, visitor );
384
385 return collision;
386 }
387
388private:
391 std::shared_ptr<SHAPE_POLY_SET> m_triangulatedPoly;
392 RTree<const SHAPE*, int, 2, double> m_rTree;
393};
394
395
396
397
399{
400protected:
401 std::vector<CN_ITEM*> m_items;
402
403 void addItemtoTree( CN_ITEM* item )
404 {
405 m_index.Insert( item );
406 }
407
408public:
410 {
411 m_dirty = false;
412 m_hasInvalid = false;
413 }
414
415 void Clear()
416 {
417 for( CN_ITEM* item : m_items )
418 delete item;
419
420 m_items.clear();
422 }
423
424 using ITER = decltype( m_items )::iterator;
425 using CONST_ITER = decltype( m_items )::const_iterator;
426
427 ITER begin() { return m_items.begin(); };
428 ITER end() { return m_items.end(); };
429
430 CONST_ITER begin() const { return m_items.begin(); }
431 CONST_ITER end() const { return m_items.end(); }
432
433 CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
434
435 template <class T>
436 void FindNearby( CN_ITEM* aItem, T aFunc )
437 {
438 m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
439 }
440
441 void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
442
443 void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
444 bool IsDirty() const { return m_dirty; }
445
446 void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
447
449 {
450 for( CN_ITEM* item : m_items )
451 item->SetDirty( false );
452
453 SetDirty( false );
454 }
455
456 int Size() const
457 {
458 return m_items.size();
459 }
460
461 CN_ITEM* Add( PAD* pad );
462
463 CN_ITEM* Add( PCB_TRACK* track );
464
465 CN_ITEM* Add( PCB_ARC* track );
466
467 CN_ITEM* Add( PCB_VIA* via );
468
469 CN_ITEM* Add( CN_ZONE_LAYER* zitem );
470
471 const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
472
473private:
477};
478
479
481{
482private:
486 std::vector<CN_ITEM*> m_items;
487 std::unordered_map<int, int> m_netRanks;
488
489public:
490 CN_CLUSTER();
491 ~CN_CLUSTER();
492
493 bool HasValidNet() const { return m_originNet > 0; }
494 int OriginNet() const { return m_originNet; }
495
496 wxString OriginNetName() const;
497
498 bool Contains( const CN_ITEM* aItem );
499 bool Contains( const BOARD_CONNECTED_ITEM* aItem );
500 void Dump();
501
502 int Size() const { return m_items.size(); }
503
504 bool IsOrphaned() const { return m_originPad == nullptr; }
505
506 bool IsConflicting() const { return m_conflicting; }
507
508 void Add( CN_ITEM* item );
509
510 using ITER = decltype(m_items)::iterator;
511
512 ITER begin() { return m_items.begin(); };
513 ITER end() { return m_items.end(); };
514};
515
516
517
518#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
std::shared_ptr< CN_ANCHOR > AddAnchor(const VECTOR2I &aPos)
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)
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:59
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:602
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