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_CONNECTIVITY_ITEMS_H_
30 #define PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_
31 
32 #include <class_board.h>
33 #include <class_pad.h>
34 #include <class_module.h>
35 #include <class_track.h>
36 #include <class_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  const unsigned int Dist( const CN_ANCHOR& aSecond )
85  {
86  return ( m_pos - aSecond.Pos() ).EuclideanNorm();
87  }
88 
90  inline int GetTag() const
91  {
92  return m_tag;
93  }
94 
96  inline void SetTag( int aTag )
97  {
98  m_tag = aTag;
99  }
100 
102  inline void SetNoLine( bool aEnable )
103  {
104  m_noline = aEnable;
105  }
106 
108  inline const bool& GetNoLine() const
109  {
110  return m_noline;
111  }
112 
113  inline void SetCluster( std::shared_ptr<CN_CLUSTER> aCluster )
114  {
115  m_cluster = aCluster;
116  }
117 
118  inline const std::shared_ptr<CN_CLUSTER>& GetCluster() const
119  {
120  return m_cluster;
121  }
122 
131  bool IsDangling() const;
132 
137  int ConnectedItemsCount() const;
138 
139  // Tag used for unconnected items.
140  static const int TAG_UNCONNECTED = -1;
141 
142 private:
145 
147  CN_ITEM* m_item = nullptr;
148 
150  int m_tag = -1;
151 
153  bool m_noline = false;
154 
156  std::shared_ptr<CN_CLUSTER> m_cluster;
157 };
158 
159 
160 typedef std::shared_ptr<CN_ANCHOR> CN_ANCHOR_PTR;
161 typedef std::vector<CN_ANCHOR_PTR> CN_ANCHORS;
162 
163 
164 // basic connectivity item
165 class CN_ITEM : public INTRUSIVE_LIST<CN_ITEM>
166 {
167 public:
168  using CONNECTED_ITEMS = std::vector<CN_ITEM*>;
169 
170 private:
172 
175 
177 
179  bool m_visited;
180 
183 
185  bool m_valid;
186 
188  std::mutex m_listLock;
189 
190 protected:
192  bool m_dirty;
193 
196 
199 
200 public:
201  void Dump();
202 
203  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
204  {
205  m_parent = aParent;
206  m_canChangeNet = aCanChangeNet;
207  m_visited = false;
208  m_valid = true;
209  m_dirty = true;
210  m_anchors.reserve( std::max( 6, aAnchorCount ) );
212  m_connected.reserve( 8 );
213  }
214 
215  virtual ~CN_ITEM() {};
216 
217  void AddAnchor( const VECTOR2I& aPos )
218  {
219  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
220  }
221 
223  {
224  return m_anchors;
225  }
226 
227  void SetValid( bool aValid )
228  {
229  m_valid = aValid;
230  }
231 
232  bool Valid() const
233  {
234  return m_valid;
235  }
236 
237  void SetDirty( bool aDirty )
238  {
239  m_dirty = aDirty;
240  }
241 
242  bool Dirty() const
243  {
244  return m_dirty;
245  }
246 
252  void SetLayers( const LAYER_RANGE& aLayers )
253  {
254  m_layers = aLayers;
255  }
256 
262  void SetLayer( int aLayer )
263  {
264  m_layers = LAYER_RANGE( aLayer, aLayer );
265  }
266 
272  const LAYER_RANGE& Layers() const
273  {
274  return m_layers;
275  }
276 
282  virtual int Layer() const
283  {
284  return Layers().Start();
285  }
286 
287  const BOX2I& BBox()
288  {
289  if( m_dirty && m_valid )
290  {
292  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
293  }
294  return m_bbox;
295  }
296 
298  {
299  return m_parent;
300  }
301 
303  {
304  return m_connected;
305  }
306 
308  {
309  m_connected.clear();
310  }
311 
312  void SetVisited( bool aVisited )
313  {
314  m_visited = aVisited;
315  }
316 
317  bool Visited() const
318  {
319  return m_visited;
320  }
321 
322  bool CanChangeNet() const
323  {
324  return m_canChangeNet;
325  }
326 
327  void Connect( CN_ITEM* b )
328  {
329  std::lock_guard<std::mutex> lock( m_listLock );
330 
331  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
332 
333  if( i != m_connected.end() && *i == b )
334  return;
335 
336  m_connected.insert( i, b );
337  }
338 
339  void RemoveInvalidRefs();
340 
341  virtual int AnchorCount() const;
342  virtual const VECTOR2I GetAnchor( int n ) const;
343 
344  int Net() const
345  {
346  return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
347  }
348 };
349 
350 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
351 
352 class CN_ZONE : public CN_ITEM
353 {
354 public:
355  CN_ZONE( ZONE_CONTAINER* aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex ) :
356  CN_ITEM( aParent, aCanChangeNet ),
357  m_subpolyIndex( aSubpolyIndex ),
358  m_layer( aLayer )
359  {
360  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList( aLayer ).COutline( aSubpolyIndex );
361 
362  outline.SetClosed( true );
363  outline.Simplify();
364 
365  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
366  }
367 
368  int SubpolyIndex() const
369  {
370  return m_subpolyIndex;
371  }
372 
373  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
374  {
375  return ContainsPoint( anchor->Pos() );
376  }
377 
378  bool ContainsPoint( const VECTOR2I p ) const
379  {
380  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
381  int clearance = zone->GetFilledPolysUseThickness() ? zone->GetMinThickness() / 2 : 0;
382  return m_cachedPoly->ContainsPoint( p, clearance );
383  }
384 
385  const BOX2I& BBox()
386  {
387  if( m_dirty )
388  m_bbox = m_cachedPoly->BBox();
389 
390  return m_bbox;
391  }
392 
393  virtual int AnchorCount() const override;
394  virtual const VECTOR2I GetAnchor( int n ) const override;
395 
396 private:
397  std::vector<VECTOR2I> m_testOutlinePoints;
398  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
401 };
402 
403 class CN_LIST
404 {
405 private:
406  bool m_dirty;
408 
410 
411 protected:
412  std::vector<CN_ITEM*> m_items;
413 
414  void addItemtoTree( CN_ITEM* item )
415  {
416  m_index.Insert( item );
417  }
418 
419 public:
421  {
422  m_dirty = false;
423  m_hasInvalid = false;
424  }
425 
426  void Clear()
427  {
428  for( auto item : m_items )
429  delete item;
430 
431  m_items.clear();
432  m_index.RemoveAll();
433  }
434 
435  using ITER = decltype( m_items )::iterator;
436  using CONST_ITER = decltype( m_items )::const_iterator;
437 
438  ITER begin() { return m_items.begin(); };
439  ITER end() { return m_items.end(); };
440 
442  {
443  return m_items.begin();
444  }
445 
446  CONST_ITER end() const
447  {
448  return m_items.end();
449  }
450 
451  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
452 
453  template <class T>
454  void FindNearby( CN_ITEM *aItem, T aFunc )
455  {
456  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
457  }
458 
459  void SetHasInvalid( bool aInvalid = true )
460  {
461  m_hasInvalid = aInvalid;
462  }
463 
464  void SetDirty( bool aDirty = true )
465  {
466  m_dirty = aDirty;
467  }
468 
469  bool IsDirty() const
470  {
471  return m_dirty;
472  }
473 
474  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
475 
477  {
478  for( auto item : m_items )
479  item->SetDirty( false );
480 
481  SetDirty( false );
482  }
483 
485  {
486  for( auto item : m_items )
487  item->SetDirty( true );
488 
489  SetDirty( true );
490  }
491 
492  int Size() const
493  {
494  return m_items.size();
495  }
496 
497  CN_ITEM* Add( D_PAD* pad );
498 
499  CN_ITEM* Add( TRACK* track );
500 
501  CN_ITEM* Add( ARC* track );
502 
503  CN_ITEM* Add( VIA* via );
504 
505  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone, PCB_LAYER_ID aLayer );
506 };
507 
509 {
510 private:
511 
512  bool m_conflicting = false;
513  int m_originNet = 0;
514  CN_ITEM* m_originPad = nullptr;
515  std::vector<CN_ITEM*> m_items;
516 
517 public:
518  CN_CLUSTER();
519  ~CN_CLUSTER();
520 
521  bool HasValidNet() const
522  {
523  return m_originNet > 0;
524  }
525 
526  int OriginNet() const
527  {
528  return m_originNet;
529  }
530 
531  wxString OriginNetName() const;
532 
533  bool Contains( const CN_ITEM* aItem );
534  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
535  void Dump();
536 
537  int Size() const
538  {
539  return m_items.size();
540  }
541 
542  bool HasNet() const
543  {
544  return m_originNet > 0;
545  }
546 
547  bool IsOrphaned() const
548  {
549  return m_originPad == nullptr;
550  }
551 
552  bool IsConflicting() const
553  {
554  return m_conflicting;
555  }
556 
557  void Add( CN_ITEM* item );
558 
559  using ITER = decltype(m_items)::iterator;
560 
561  ITER begin() { return m_items.begin(); };
562  ITER end() { return m_items.end(); };
563 };
564 
565 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
566 
567 
568 #endif /* PCBNEW_CONNECTIVITY_CONNECTIVITY_ITEMS_H_ */
std::vector< CN_ITEM * > CONNECTED_ITEMS
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
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.
virtual int AnchorCount() const override
std::vector< CN_ITEM * > m_items
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:61
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
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.
int SubpolyIndex() const
std::vector< VECTOR2I > m_testOutlinePoints
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
A lightweight intrusive list container
CN_ITEM * Add(D_PAD *pad)
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
layer range over which the item exists
const BOX2I & BBox()
const SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:602
void SetVisited(bool aVisited)
bool IsDirty() const
const unsigned int Dist(const CN_ANCHOR &aSecond)
bool Dirty() const
T
enum T contains all this lexer's tokens.
BOARD_CONNECTED_ITEM * Parent() const
static const int TAG_UNCONNECTED
CN_ITEM * Item() const
bool HasNet() 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
A single base class (TRACK) represents both tracks and vias, with subclasses for curved tracks (ARC) ...
void MarkAllAsDirty()
PCB_LAYER_ID m_layer
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
visited flag for the BFS scan
PCB_LAYER_ID
A quick note on layer IDs:
std::vector< CN_ANCHOR_PTR > CN_ANCHORS
int OriginNet() const
CN_ANCHOR(const VECTOR2I &aPos, CN_ITEM *aItem)
const wxPoint GetPosition() const
Definition: eda_rect.h:115
int Size() const
bool m_dirty
dirty flag, used to identify recently added item not yet scanned into the connectivity search
void SetLayers(const LAYER_RANGE &aLayers)
Function SetLayers()
std::mutex m_listLock
mutex protecting this item's connected_items set to allow parallel connection threads
virtual ~CN_ITEM()
BOX2I m_bbox
bounding box for the item
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
void Add(CN_ITEM *item)
bool m_canChangeNet
can the net propagator modify the netcode?
void Query(const BOX2I &aBounds, const LAYER_RANGE &aRange, Visitor &aVisitor)
Function Query() Executes a function object aVisitor for each item whose bounding box intersects with...
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
bool ContainsPoint(const VECTOR2I p) const
bool Valid() const
Pad object description.
bool IsConflicting() const
virtual const VECTOR2I GetAnchor(int n) const
void SetDirty(bool aDirty)
int m_tag
Tag for quick connection resolution.
std::unique_ptr< POLY_GRID_PARTITION > m_cachedPoly
bool CanChangeNet() const
wxString OriginNetName() const
bool HasValidNet() const
void AddAnchor(const VECTOR2I &aPos)
void FindNearby(CN_ITEM *aItem, T aFunc)
virtual const VECTOR2I GetAnchor(int n) const override
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
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
CN_ITEM(BOARD_CONNECTED_ITEM *aParent, bool aCanChangeNet, int aAnchorCount=2)
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.
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void Connect(CN_ITEM *b)
CN_ZONE(ZONE_CONTAINER *aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex)
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: base_struct.cpp:97
decltype(m_items)::iterator ITER
bool IsOrphaned() const
LAYER_RANGE.
Definition: pns_layerset.h:32
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