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  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 
184  bool m_visited;
185 
188 
190  bool m_valid;
191 
193  std::mutex m_listLock;
194 
195 protected:
197  bool m_dirty;
198 
201 
204 
205 public:
206  void Dump();
207 
208  CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
209  {
210  m_parent = aParent;
211  m_canChangeNet = aCanChangeNet;
212  m_visited = false;
213  m_valid = true;
214  m_dirty = true;
215  m_anchors.reserve( std::max( 6, aAnchorCount ) );
217  m_connected.reserve( 8 );
218  }
219 
220  virtual ~CN_ITEM() {};
221 
222  void AddAnchor( const VECTOR2I& aPos )
223  {
224  m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
225  }
226 
228  {
229  return m_anchors;
230  }
231 
232  void SetValid( bool aValid )
233  {
234  m_valid = aValid;
235  }
236 
237  bool Valid() const
238  {
239  return m_valid;
240  }
241 
242  void SetDirty( bool aDirty )
243  {
244  m_dirty = aDirty;
245  }
246 
247  bool Dirty() const
248  {
249  return m_dirty;
250  }
251 
257  void SetLayers( const LAYER_RANGE& aLayers )
258  {
259  m_layers = aLayers;
260  }
261 
267  void SetLayer( int aLayer )
268  {
269  m_layers = LAYER_RANGE( aLayer, aLayer );
270  }
271 
277  const LAYER_RANGE& Layers() const
278  {
279  return m_layers;
280  }
281 
287  virtual int Layer() const
288  {
289  return Layers().Start();
290  }
291 
292  const BOX2I& BBox()
293  {
294  if( m_dirty && m_valid )
295  {
297  m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
298  }
299  return m_bbox;
300  }
301 
303  {
304  return m_parent;
305  }
306 
308  {
309  return m_connected;
310  }
311 
313  {
314  m_connected.clear();
315  }
316 
317  void SetVisited( bool aVisited )
318  {
319  m_visited = aVisited;
320  }
321 
322  bool Visited() const
323  {
324  return m_visited;
325  }
326 
327  bool CanChangeNet() const
328  {
329  return m_canChangeNet;
330  }
331 
332  void Connect( CN_ITEM* b )
333  {
334  std::lock_guard<std::mutex> lock( m_listLock );
335 
336  auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
337 
338  if( i != m_connected.end() && *i == b )
339  return;
340 
341  m_connected.insert( i, b );
342  }
343 
344  void RemoveInvalidRefs();
345 
346  virtual int AnchorCount() const;
347  virtual const VECTOR2I GetAnchor( int n ) const;
348 
349  int Net() const
350  {
351  return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
352  }
353 };
354 
355 typedef std::shared_ptr<CN_ITEM> CN_ITEM_PTR;
356 
357 class CN_ZONE_LAYER : public CN_ITEM
358 {
359 public:
360  CN_ZONE_LAYER( ZONE_CONTAINER* aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet,
361  int aSubpolyIndex ) :
362  CN_ITEM( aParent, aCanChangeNet ),
363  m_subpolyIndex( aSubpolyIndex ),
364  m_layer( aLayer )
365  {
366  SHAPE_LINE_CHAIN outline = aParent->GetFilledPolysList( aLayer ).COutline( aSubpolyIndex );
367 
368  outline.SetClosed( true );
369  outline.Simplify();
370 
371  m_cachedPoly = std::make_unique<POLY_GRID_PARTITION>( outline, 16 );
372  }
373 
374  int SubpolyIndex() const
375  {
376  return m_subpolyIndex;
377  }
378 
379  bool ContainsAnchor( const CN_ANCHOR_PTR anchor ) const
380  {
381  return ContainsPoint( anchor->Pos(), 0 );
382  }
383 
384  bool ContainsPoint( const VECTOR2I p, int aAccuracy = 0 ) const
385  {
386  auto zone = static_cast<ZONE_CONTAINER*> ( Parent() );
387  int clearance = aAccuracy;
388 
389  if( zone->GetFilledPolysUseThickness() )
390  clearance += ( zone->GetMinThickness() + 1 ) / 2;
391 
392  return m_cachedPoly->ContainsPoint( p, clearance );
393  }
394 
395  const BOX2I& BBox()
396  {
397  if( m_dirty )
398  m_bbox = m_cachedPoly->BBox();
399 
400  return m_bbox;
401  }
402 
403  virtual int AnchorCount() const override;
404  virtual const VECTOR2I GetAnchor( int n ) const override;
405 
406 private:
407  std::vector<VECTOR2I> m_testOutlinePoints;
408  std::unique_ptr<POLY_GRID_PARTITION> m_cachedPoly;
411 };
412 
413 class CN_LIST
414 {
415 private:
416  bool m_dirty;
418 
420 
421 protected:
422  std::vector<CN_ITEM*> m_items;
423 
424  void addItemtoTree( CN_ITEM* item )
425  {
426  m_index.Insert( item );
427  }
428 
429 public:
431  {
432  m_dirty = false;
433  m_hasInvalid = false;
434  }
435 
436  void Clear()
437  {
438  for( auto item : m_items )
439  delete item;
440 
441  m_items.clear();
442  m_index.RemoveAll();
443  }
444 
445  using ITER = decltype( m_items )::iterator;
446  using CONST_ITER = decltype( m_items )::const_iterator;
447 
448  ITER begin() { return m_items.begin(); };
449  ITER end() { return m_items.end(); };
450 
452  {
453  return m_items.begin();
454  }
455 
456  CONST_ITER end() const
457  {
458  return m_items.end();
459  }
460 
461  CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
462 
463  template <class T>
464  void FindNearby( CN_ITEM *aItem, T aFunc )
465  {
466  m_index.Query( aItem->BBox(), aItem->Layers(), aFunc );
467  }
468 
469  void SetHasInvalid( bool aInvalid = true )
470  {
471  m_hasInvalid = aInvalid;
472  }
473 
474  void SetDirty( bool aDirty = true )
475  {
476  m_dirty = aDirty;
477  }
478 
479  bool IsDirty() const
480  {
481  return m_dirty;
482  }
483 
484  void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
485 
487  {
488  for( auto item : m_items )
489  item->SetDirty( false );
490 
491  SetDirty( false );
492  }
493 
495  {
496  for( auto item : m_items )
497  item->SetDirty( true );
498 
499  SetDirty( true );
500  }
501 
502  int Size() const
503  {
504  return m_items.size();
505  }
506 
507  CN_ITEM* Add( D_PAD* pad );
508 
509  CN_ITEM* Add( TRACK* track );
510 
511  CN_ITEM* Add( ARC* track );
512 
513  CN_ITEM* Add( VIA* via );
514 
515  const std::vector<CN_ITEM*> Add( ZONE_CONTAINER* zone, PCB_LAYER_ID aLayer );
516 };
517 
519 {
520 private:
521 
522  bool m_conflicting = false;
523  int m_originNet = 0;
524  CN_ITEM* m_originPad = nullptr;
525  std::vector<CN_ITEM*> m_items;
526 
527 public:
528  CN_CLUSTER();
529  ~CN_CLUSTER();
530 
531  bool HasValidNet() const
532  {
533  return m_originNet > 0;
534  }
535 
536  int OriginNet() const
537  {
538  return m_originNet;
539  }
540 
541  wxString OriginNetName() const;
542 
543  bool Contains( const CN_ITEM* aItem );
544  bool Contains( const BOARD_CONNECTED_ITEM* aItem );
545  void Dump();
546 
547  int Size() const
548  {
549  return m_items.size();
550  }
551 
552  bool HasNet() const
553  {
554  return m_originNet > 0;
555  }
556 
557  bool IsOrphaned() const
558  {
559  return m_originPad == nullptr;
560  }
561 
562  bool IsConflicting() const
563  {
564  return m_conflicting;
565  }
566 
567  void Add( CN_ITEM* item );
568 
569  using ITER = decltype(m_items)::iterator;
570 
571  ITER begin() { return m_items.begin(); };
572  ITER end() { return m_items.end(); };
573 };
574 
575 typedef std::shared_ptr<CN_CLUSTER> CN_CLUSTER_PTR;
576 
577 
578 #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:133
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
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:61
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)
CN_ZONE_LAYER(ZONE_CONTAINER *aParent, PCB_LAYER_ID aLayer, bool aCanChangeNet, int aSubpolyIndex)
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
const BOX2I & BBox()
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 SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:627
bool ContainsAnchor(const CN_ANCHOR_PTR anchor) const
void SetVisited(bool aVisited)
bool IsDirty() const
const unsigned int Dist(const CN_ANCHOR &aSecond)
bool Dirty() const
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()
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)
virtual int AnchorCount() const override
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
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
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...
PCB_LAYER_ID m_layer
const std::shared_ptr< CN_CLUSTER > & GetCluster() 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.
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
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.
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
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