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-2021 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 
40 
41 #include <memory>
42 #include <algorithm>
43 #include <functional>
44 #include <vector>
45 #include <deque>
46 #include <intrusive_list.h>
47 
50 
51 class CN_ITEM;
52 class CN_CLUSTER;
53 
54 
59 class CN_ANCHOR
60 {
61 public:
63  {
64  m_item = nullptr;
65  }
66 
67  CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem )
68  {
69  m_pos = aPos;
70  m_item = aItem;
71  assert( m_item );
72  }
73 
74  bool Valid() const;
75 
76  CN_ITEM* Item() const
77  {
78  return m_item;
79  }
80 
82 
83  const VECTOR2I& Pos() const
84  {
85  return m_pos;
86  }
87 
88  void Move( const VECTOR2I& aPos )
89  {
90  m_pos += aPos;
91  }
92 
93  const unsigned int Dist( const CN_ANCHOR& aSecond )
94  {
95  return ( m_pos - aSecond.Pos() ).EuclideanNorm();
96  }
97 
99  inline int GetTag() const
100  {
101  return m_tag;
102  }
103 
105  inline void SetTag( int aTag )
106  {
107  m_tag = aTag;
108  }
109 
111  inline void SetNoLine( bool aEnable )
112  {
113  m_noline = aEnable;
114  }
115 
117  inline const bool& GetNoLine() const
118  {
119  return m_noline;
120  }
121 
122  inline void SetCluster( std::shared_ptr<CN_CLUSTER>& aCluster )
123  {
124  m_cluster = aCluster;
125  }
126 
127  inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
128  {
129  return m_cluster;
130  }
131 
139  bool IsDangling() const;
140 
144  int ConnectedItemsCount() const;
145 
146  // Tag used for unconnected items.
147  static const int TAG_UNCONNECTED = -1;
148 
149 private:
151  CN_ITEM* m_item = nullptr;
152  int m_tag = -1;
153  bool m_noline = false;
154 
155  std::shared_ptr<CN_CLUSTER> m_cluster;
156 };
157 
158 
159 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
160 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
161 
162 
167 class CN_ITEM
168 {
169 public:
170  using CONNECTED_ITEMS = std::vector<CN_ITEM*>;
171 
172  void Dump();
173 
174  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
175  {
176  m_parent = aParent;
177  m_canChangeNet = aCanChangeNet;
178  m_visited = false;
179  m_valid = true;
180  m_dirty = true;
181  m_anchors.reserve( std::max( 6, aAnchorCount ) );
183  m_connected.reserve( 8 );
184  }
185 
186  virtual ~CN_ITEM() {};
187 
188  void AddAnchor( const VECTOR2I& aPos )
189  {
190  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
191  }
192 
193  CN_ANCHORS& Anchors() { return m_anchors; }
194 
195  void SetValid( bool aValid ) { m_valid = aValid; }
196  bool Valid() const { return m_valid; }
197 
198  void SetDirty( bool aDirty ) { m_dirty = aDirty; }
199  bool Dirty() const { return m_dirty; }
200 
204  void SetLayers( const LAYER_RANGE& aLayers ) { m_layers = aLayers; }
205 
209  void SetLayer( int aLayer ) { m_layers = LAYER_RANGE( aLayer, aLayer ); }
210 
214  const LAYER_RANGE& Layers() const { return m_layers; }
215 
219  virtual int Layer() const
220  {
221  return Layers().Start();
222  }
223 
224  const BOX2I& BBox()
225  {
226  if( m_dirty && m_valid )
227  {
229  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
230  }
231 
232  return m_bbox;
233  }
234 
235  BOARD_CONNECTED_ITEM* Parent() const { return m_parent; }
236 
237  const CONNECTED_ITEMS& ConnectedItems() const { return m_connected; }
238  void ClearConnections() { m_connected.clear(); }
239 
240  void SetVisited( bool aVisited ) { m_visited = aVisited; }
241  bool Visited() const { return m_visited; }
242 
243  bool CanChangeNet() const { return m_canChangeNet; }
244 
245  void Connect( CN_ITEM* b )
246  {
247  std::lock_guard<std::mutex> lock( m_listLock );
248 
249  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
250 
251  if( i != m_connected.end() && *i == b )
252  return;
253 
254  m_connected.insert( i, b );
255  }
256 
257  void RemoveInvalidRefs();
258 
259  virtual int AnchorCount() const;
260  virtual const VECTOR2I GetAnchor( int n ) const;
261 
262  int Net() const
263  {
264  return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
265  }
267 protected:
268  bool m_dirty;
272 
273 private:
275 
278 
280 
281  bool m_visited;
282  bool m_valid;
283 
284  std::mutex m_listLock;
285 };
286 
287 
288 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
289 
290 
291 class CN_ZONE_LAYER : public CN_ITEM
292 {
293 public:
294  CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex ) :
295  CN_ITEM( aParent, aCanChangeNet ),
296  m_subpolyIndex( aSubpolyIndex ),
297  m_layer( aLayer )
298  {
299  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList( aLayer ).COutline( aSubpolyIndex );
300 
301  outline.SetClosed( true );
302  outline.Simplify();
303 
304  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
305  }
306 
307  int SubpolyIndex() const { return m_subpolyIndex; }
308 
309  PCB_LAYER_ID GetLayer() const { return m_layer; }
310 
311  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
312  {
313  return ContainsPoint( anchor->Pos(), 0 );
314  }
315 
316  bool ContainsPoint( const VECTOR2I& p, int aAccuracy = 0 ) const
317  {
318  ZONE* zone = static_cast<ZONE*>( Parent() );
319  int clearance = aAccuracy;
320 
321  if( zone->GetFilledPolysUseThickness() )
322  clearance += ( zone->GetMinThickness() + 1 ) / 2;
323 
324  return m_cachedPoly->ContainsPoint( p, clearance );
325  }
326 
327  const BOX2I& BBox()
328  {
329  if( m_dirty )
330  m_bbox = m_cachedPoly->BBox();
331 
332  return m_bbox;
333  }
334 
335  virtual int AnchorCount() const override;
336  virtual const VECTOR2I GetAnchor( int n ) const override;
337 
338 private:
339  std::vector<VECTOR2I> m_testOutlinePoints;
340  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
343 };
344 
345 
346 class CN_LIST
347 {
348 protected:
349  std::vector<CN_ITEM*> m_items;
350 
351  void addItemtoTree( CN_ITEM* item )
352  {
353  m_index.Insert( item );
354  }
355 
356 public:
358  {
359  m_dirty = false;
360  m_hasInvalid = false;
361  }
362 
363  void Clear()
364  {
365  for( CN_ITEM* item : m_items )
366  delete item;
367 
368  m_items.clear();
369  m_index.RemoveAll();
370  }
371 
372  using ITER = decltype( m_items )::iterator;
373  using CONST_ITER = decltype( m_items )::const_iterator;
374 
375  ITER begin() { return m_items.begin(); };
376  ITER end() { return m_items.end(); };
377 
379  {
380  return m_items.begin();
381  }
382 
383  CONST_ITER end() const
384  {
385  return m_items.end();
386  }
387 
388  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
389 
390  template <class T>
391  void FindNearby( CN_ITEM* aItem, T aFunc )
392  {
393  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
394  }
395 
396  void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
397 
398  void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
399  bool IsDirty() const { return m_dirty; }
400 
401  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
402 
404  {
405  for( auto item : m_items )
406  item->SetDirty( false );
407 
408  SetDirty( false );
409  }
410 
412  {
413  for( auto item : m_items )
414  item->SetDirty( true );
415 
416  SetDirty( true );
417  }
418 
419  int Size() const
420  {
421  return m_items.size();
422  }
423 
424  CN_ITEM* Add( PAD* pad );
425 
426  CN_ITEM* Add( PCB_TRACK* track );
427 
428  CN_ITEM* Add( PCB_ARC* track );
429 
430  CN_ITEM* Add( PCB_VIA* via );
431 
432  const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
433 
434 private:
435  bool m_dirty;
437 
439 };
440 
441 
443 {
444 private:
448  std::vector<CN_ITEM*> m_items;
449  std::unordered_map<int, int> m_netRanks;
450 
451 public:
452  CN_CLUSTER();
453  ~CN_CLUSTER();
454 
455  bool HasValidNet() const { return m_originNet > 0; }
456  int OriginNet() const { return m_originNet; }
457 
458  wxString OriginNetName() const;
459 
460  bool Contains( const CN_ITEM* aItem );
461  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
462  void Dump();
463 
464  int Size() const { return m_items.size(); }
465 
466  bool IsOrphaned() const { return m_originPad == nullptr; }
467 
468  bool IsConflicting() const { return m_conflicting; }
469 
470  void Add( CN_ITEM* item );
471 
472  using ITER = decltype(m_items)::iterator;
473 
474  ITER begin() { return m_items.begin(); };
475  ITER end() { return m_items.end(); };
476 };
477 
478 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
479 
480 
481 #endif /* PCBNEW_CONNECTIVITY_ITEMS_H */
std::vector< CN_ITEM * > CONNECTED_ITEMS
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
const CONNECTED_ITEMS & ConnectedItems() const
bool Contains(const CN_ITEM *aItem)
int GetTag() const
Set tag, common identifier for connected nodes.
std::vector< CN_ITEM * > m_items
std::vector< VECTOR2I > m_testOutlinePoints
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
decltype(m_items)::iterator ITER
BOARD_CONNECTED_ITEM * m_parent
int Size() const
void SetHasInvalid(bool aInvalid=true)
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
CN_ITEM * Add(PAD *pad)
void addItemtoTree(CN_ITEM *item)
bool m_valid
used to identify garbage items (we use lazy removal)
const BOX2I & BBox()
void ClearDirtyFlags()
const bool & GetNoLine() const
void ClearConnections()
void SetCluster(std::shared_ptr< CN_CLUSTER > &aCluster)
CN_ITEM * operator[](int aIndex)
LAYER_RANGE m_layers
layer range over which the item exists
bool ContainsPoint(const VECTOR2I &p, int aAccuracy=0) const
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void SetVisited(bool aVisited)
bool IsDirty() const
const unsigned int Dist(const CN_ANCHOR &aSecond)
Return tag, common identifier for connected nodes.
const SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:637
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
static const int TAG_UNCONNECTED
CN_ITEM * Item() const
bool IsDangling() const
The anchor point is dangling if the parent is a track and this anchor point is not connected to anoth...
CN_ANCHORS & Anchors()
CN_ANCHOR represents a physical location that can be connected: a pad or a track/arc/via endpoint.
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
decltype(m_items)::const_iterator CONST_ITER
void SetDirty(bool aDirty=true)
void RemoveAll()
Function RemoveAll() Removes all items from the RTree.
int ConnectedItemsCount() const
int Net() const
allow parallel connection threads
bool Visited() const
void MarkAllAsDirty()
VECTOR2I m_pos
Position of the anchor.
virtual int AnchorCount() const
CONST_ITER begin() const
int Start() const
Definition: pns_layerset.h:82
void SetValid(bool aValid)
std::unordered_map< int, int > m_netRanks
std::vector< CN_ITEM * > m_items
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
bool m_visited
visited flag for the BFS scan
std::vector< CN_ANCHOR_PTR > CN_ANCHORS
int GetMinThickness() const
Definition: zone.h:244
int OriginNet() const
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
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...
virtual int AnchorCount() const override
const wxPoint GetPosition() const
Definition: eda_rect.h:111
int Size() const
bool m_dirty
used to identify recently added item not yet scanned into the connectivity search
void SetLayers(const LAYER_RANGE &aLayers)
Set the layers spanned by the item to aLayers.
std::mutex m_listLock
mutex protecting this item's connected_items set to
Handle a list of polygons defining a copper zone.
Definition: zone.h:56
virtual ~CN_ITEM()
BOX2I m_bbox
bounding box for the item
int SubpolyIndex() const
void SetTag(int aTag)
Decide whether this node can be a ratsnest line target.
void Add(CN_ITEM *item)
bool m_canChangeNet
can the net propagator modify the netcode?
PCB_LAYER_ID m_layer
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
bool Valid() const
CN_ZONE_LAYER(ZONE *aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex)
bool IsConflicting() const
virtual const VECTOR2I GetAnchor(int n) const
void SetDirty(bool aDirty)
int m_tag
Tag for quick connection resolution.
bool CanChangeNet() const
wxString OriginNetName() const
bool HasValidNet() const
void AddAnchor(const VECTOR2I &aPos)
void FindNearby(CN_ITEM *aItem, T aFunc)
CN_ITEM * m_item
Pad or track/arc/via owning the anchor.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
void SetLayer(int aLayer)
Set the layers spanned by the item to a single layer aLayer.
CN_ITEM * m_originPad
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
const LAYER_RANGE & Layers() const
Return the contiguous set of layers spanned by the item.
Handle the component boundary box.
Definition: eda_rect.h:42
BOARD_CONNECTED_ITEM * Parent() const
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
virtual const VECTOR2I GetAnchor(int n) const override
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
CN_ITEM(BOARD_CONNECTED_ITEM *aParent, bool aCanChangeNet, int aAnchorCount=2)
std::unique_ptr< POLY_GRID_PARTITION > m_cachedPoly
virtual int Layer() const
Return the item's layer, for single-layered items only.
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
void SetNoLine(bool aEnable)
Return true if this node can be a target for ratsnest lines.
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
void Connect(CN_ITEM *b)
void Move(const VECTOR2I &aPos)
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:75
Definition: pad.h:57
decltype(m_items)::iterator ITER
bool IsOrphaned() const
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31
const BOX2I & BBox()
void RemoveInvalidRefs()
bool m_noline
Whether it the node can be a target for ratsnest lines.
const wxSize GetSize() const
Definition: eda_rect.h:100
bool Valid() const
CONST_ITER end() const
CN_RTREE< CN_ITEM * > m_index
CN_ANCHORS m_anchors
bool GetFilledPolysUseThickness() const
Definition: zone.h:691
PCB_LAYER_ID GetLayer() const