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-2020 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <maciej.suminski@cern.ch>
8  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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 <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 class CN_ANCHOR
55 {
56 public:
58  {
59  m_item = nullptr;
60  }
61 
62  CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem )
63  {
64  m_pos = aPos;
65  m_item = aItem;
66  assert( m_item );
67  }
68 
69  bool Valid() const;
70 
71 
72  CN_ITEM* Item() const
73  {
74  return m_item;
75  }
76 
78 
79  const VECTOR2I& Pos() const
80  {
81  return m_pos;
82  }
83 
84  void Move( const VECTOR2I& aPos )
85  {
86  m_pos += aPos;
87  }
88 
89  const unsigned int Dist( const CN_ANCHOR& aSecond )
90  {
91  return ( m_pos - aSecond.Pos() ).EuclideanNorm();
92  }
93 
95  inline int GetTag() const
96  {
97  return m_tag;
98  }
99 
101  inline void SetTag( int aTag )
102  {
103  m_tag = aTag;
104  }
105 
107  inline void SetNoLine( bool aEnable )
108  {
109  m_noline = aEnable;
110  }
111 
113  inline const bool& GetNoLine() const
114  {
115  return m_noline;
116  }
117 
118  inline void SetCluster( std::shared_ptr<CN_CLUSTER> aCluster )
119  {
120  m_cluster = aCluster;
121  }
122 
123  inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
124  {
125  return m_cluster;
126  }
127 
136  bool IsDangling() const;
137 
142  int ConnectedItemsCount() const;
143 
144  // Tag used for unconnected items.
145  static const int TAG_UNCONNECTED = -1;
146 
147 private:
150 
152  CN_ITEM* m_item = nullptr;
153 
155  int m_tag = -1;
156 
158  bool m_noline = false;
159 
161  std::shared_ptr<CN_CLUSTER> m_cluster;
162 };
163 
164 
165 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
166 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
167 
168 
169 // basic connectivity item
170 class CN_ITEM
171 {
172 public:
173  using CONNECTED_ITEMS = std::vector<CN_ITEM*>;
174 
175 private:
177 
180 
182 
183  bool m_visited;
184  bool m_valid;
185 
186  std::mutex m_listLock;
187 protected:
189  bool m_dirty;
193 
194 public:
195  void Dump();
196 
197  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
198  {
199  m_parent = aParent;
200  m_canChangeNet = aCanChangeNet;
201  m_visited = false;
202  m_valid = true;
203  m_dirty = true;
204  m_anchors.reserve( std::max( 6, aAnchorCount ) );
206  m_connected.reserve( 8 );
207  }
208 
209  virtual ~CN_ITEM() {};
210 
211  void AddAnchor( const VECTOR2I& aPos )
212  {
213  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
214  }
215 
216  CN_ANCHORS& Anchors() { return m_anchors; }
217 
218  void SetValid( bool aValid ) { m_valid = aValid; }
219  bool Valid() const { return m_valid; }
220 
221  void SetDirty( bool aDirty ) { m_dirty = aDirty; }
222  bool Dirty() const { return m_dirty; }
223 
229  void SetLayers( const LAYER_RANGE& aLayers )
230  {
231  m_layers = aLayers;
232  }
233 
239  void SetLayer( int aLayer )
240  {
241  m_layers = LAYER_RANGE( aLayer, aLayer );
242  }
243 
249  const LAYER_RANGE& Layers() const
250  {
251  return m_layers;
252  }
253 
259  virtual int Layer() const
260  {
261  return Layers().Start();
262  }
263 
264  const BOX2I& BBox()
265  {
266  if( m_dirty && m_valid )
267  {
269  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
270  }
271  return m_bbox;
272  }
273 
275  {
276  return m_parent;
277  }
278 
279  const CONNECTED_ITEMS& ConnectedItems() const { return m_connected; }
280  void ClearConnections() { m_connected.clear(); }
281 
282  void SetVisited( bool aVisited ) { m_visited = aVisited; }
283  bool Visited() const { return m_visited; }
284 
285  bool CanChangeNet() const { return m_canChangeNet; }
286 
287  void Connect( CN_ITEM* b )
288  {
289  std::lock_guard<std::mutex> lock( m_listLock );
290 
291  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
292 
293  if( i != m_connected.end() && *i == b )
294  return;
295 
296  m_connected.insert( i, b );
297  }
298 
299  void RemoveInvalidRefs();
300 
301  virtual int AnchorCount() const;
302  virtual const VECTOR2I GetAnchor( int n ) const;
303 
304  int Net() const
305  {
306  return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
307  }
308 };
309 
310 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
311 
312 class CN_ZONE_LAYER : public CN_ITEM
313 {
314 public:
315  CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex ) :
316  CN_ITEM( aParent, aCanChangeNet ),
317  m_subpolyIndex( aSubpolyIndex ),
318  m_layer( aLayer )
319  {
320  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList( aLayer ).COutline( aSubpolyIndex );
321 
322  outline.SetClosed( true );
323  outline.Simplify();
324 
325  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
326  }
327 
328  int SubpolyIndex() const
329  {
330  return m_subpolyIndex;
331  }
332 
333  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
334  {
335  return ContainsPoint( anchor->Pos(), 0 );
336  }
337 
338  bool ContainsPoint( const VECTOR2I p, int aAccuracy = 0 ) const
339  {
340  ZONE* zone = static_cast<ZONE*>( Parent() );
341  int clearance = aAccuracy;
342 
343  if( zone->GetFilledPolysUseThickness() )
344  clearance += ( zone->GetMinThickness() + 1 ) / 2;
345 
346  return m_cachedPoly->ContainsPoint( p, clearance );
347  }
348 
349  const BOX2I& BBox()
350  {
351  if( m_dirty )
352  m_bbox = m_cachedPoly->BBox();
353 
354  return m_bbox;
355  }
356 
357  virtual int AnchorCount() const override;
358  virtual const VECTOR2I GetAnchor( int n ) const override;
359 
360 private:
361  std::vector<VECTOR2I> m_testOutlinePoints;
362  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
365 };
366 
367 class CN_LIST
368 {
369 private:
370  bool m_dirty;
372 
374 
375 protected:
376  std::vector<CN_ITEM*> m_items;
377 
378  void addItemtoTree( CN_ITEM* item )
379  {
380  m_index.Insert( item );
381  }
382 
383 public:
385  {
386  m_dirty = false;
387  m_hasInvalid = false;
388  }
389 
390  void Clear()
391  {
392  for( auto item : m_items )
393  delete item;
394 
395  m_items.clear();
396  m_index.RemoveAll();
397  }
398 
399  using ITER = decltype( m_items )::iterator;
400  using CONST_ITER = decltype( m_items )::const_iterator;
401 
402  ITER begin() { return m_items.begin(); };
403  ITER end() { return m_items.end(); };
404 
406  {
407  return m_items.begin();
408  }
409 
410  CONST_ITER end() const
411  {
412  return m_items.end();
413  }
414 
415  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
416 
417  template <class T>
418  void FindNearby( CN_ITEM *aItem, T aFunc )
419  {
420  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
421  }
422 
423  void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
424 
425  void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
426  bool IsDirty() const { return m_dirty; }
427 
428  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
429 
431  {
432  for( auto item : m_items )
433  item->SetDirty( false );
434 
435  SetDirty( false );
436  }
437 
439  {
440  for( auto item : m_items )
441  item->SetDirty( true );
442 
443  SetDirty( true );
444  }
445 
446  int Size() const
447  {
448  return m_items.size();
449  }
450 
451  CN_ITEM* Add( PAD* pad );
452 
453  CN_ITEM* Add( TRACK* track );
454 
455  CN_ITEM* Add( ARC* track );
456 
457  CN_ITEM* Add( VIA* via );
458 
459  const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
460 };
461 
463 {
464 private:
465  bool m_conflicting = false;
466  int m_originNet = 0;
467  CN_ITEM* m_originPad = nullptr;
468  std::vector<CN_ITEM*> m_items;
469 
470 public:
471  CN_CLUSTER();
472  ~CN_CLUSTER();
473 
474  bool HasValidNet() const { return m_originNet > 0; }
475  int OriginNet() const { return m_originNet; }
476 
477  wxString OriginNetName() const;
478 
479  bool Contains( const CN_ITEM* aItem );
480  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
481  void Dump();
482 
483  int Size() const { return m_items.size(); }
484 
485  bool IsOrphaned() const { return m_originPad == nullptr; }
486 
487  bool IsConflicting() const { return m_conflicting; }
488 
489  void Add( CN_ITEM* item );
490 
491  using ITER = decltype(m_items)::iterator;
492 
493  ITER begin() { return m_items.begin(); };
494  ITER end() { return m_items.end(); };
495 };
496 
497 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
498 
499 
500 #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:134
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
const CONNECTED_ITEMS & ConnectedItems() const
bool Contains(const CN_ITEM *aItem)
int GetTag() const
Returns tag, common identifier for connected nodes.
std::vector< CN_ITEM * > m_items
std::vector< VECTOR2I > m_testOutlinePoints
Definition: track.h:354
BOX2< VECTOR2I > BOX2I
Definition: box2.h:522
int GetNetCode() const
Function GetNetCode.
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.
CN_ITEM * Add(PAD *pad)
void addItemtoTree(CN_ITEM *item)
bool m_valid
visited flag for the BFS scan
const BOX2I & BBox()
void ClearDirtyFlags()
const bool & GetNoLine() const
Returns true if this node can be a target for ratsnest lines.
void ClearConnections()
CN_ITEM * operator[](int aIndex)
LAYER_RANGE m_layers
used to identify recently added item not yet scanned into the connectivity search
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void SetVisited(bool aVisited)
bool IsDirty() const
const unsigned int Dist(const CN_ANCHOR &aSecond)
const SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: zone.h:647
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
static const int TAG_UNCONNECTED
CN_ITEM * Item() const
void SetCluster(std::shared_ptr< CN_CLUSTER > aCluster)
bool IsDangling() const
has meaning only for tracks and vias.
CN_ANCHORS & Anchors()
void Insert(T aItem)
Function Insert() Inserts an item into the tree.
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
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
has meaning only for tracks and vias.
int Net() const
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:83
void SetValid(bool aValid)
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
std::vector< CN_ITEM * > m_items
void SetClosed(bool aClosed)
Function SetClosed()
bool m_visited
can the net propagator modify the netcode?
PCB_LAYER_ID
A quick note on layer IDs:
std::vector< CN_ANCHOR_PTR > CN_ANCHORS
int GetMinThickness() const
Definition: zone.h:242
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:115
int Size() const
bool m_dirty
mutex protecting this item's connected_items set to allow parallel connection threads
void SetLayers(const LAYER_RANGE &aLayers)
Function SetLayers()
std::mutex m_listLock
used to identify garbage items (we use lazy removal)
ZONE handles a list of polygons defining a copper zone.
Definition: zone.h:57
virtual ~CN_ITEM()
BOX2I m_bbox
layer range over which the item exists
int SubpolyIndex() const
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
void Add(CN_ITEM *item)
bool ContainsPoint(const VECTOR2I p, int aAccuracy=0) const
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)
Definition: track.h:272
CN_ITEM * m_item
Item owning the anchor.
SHAPE_LINE_CHAIN.
void SetLayer(int aLayer)
Function SetLayer()
CN_ITEM * m_originPad
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
const LAYER_RANGE & Layers() const
Function Layers()
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
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
Function Layer()
std::shared_ptr< CN_ITEM > CN_ITEM_PTR
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
void Dump()
bounding box for the item
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
void Connect(CN_ITEM *b)
void Move(const VECTOR2I &aPos)
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: eda_item.cpp:89
Definition: pad.h:59
decltype(m_items)::iterator ITER
bool IsOrphaned() const
LAYER_RANGE.
Definition: pns_layerset.h:32
Definition: track.h:83
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:103
bool Valid() const
CONST_ITER end() const
CN_RTREE< CN_ITEM * > m_index
CN_ANCHORS m_anchors
list of items physically connected (touching)
bool GetFilledPolysUseThickness() const
Definition: zone.h:704