KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 The 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 <pcb_shape.h>
37#include <zone.h>
38
40
41#include <memory>
42#include <algorithm>
43#include <functional>
44#include <vector>
45#include <deque>
46
49
50class CN_ITEM;
51class CN_CLUSTER;
52
53
59{
60public:
61 CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem ) :
62 m_pos( aPos ),
63 m_item( aItem ),
64 m_tag( -1 ),
65 m_noline( false )
66 { }
67
68 bool Valid() const;
69
70 bool Dirty() const;
71
72 CN_ITEM* Item() const { return m_item; }
73 void SetItem( CN_ITEM* aItem ) { m_item = aItem; }
74
76
77 const VECTOR2I& Pos() const { return m_pos; }
78
79 void Move( const VECTOR2I& aPos )
80 {
81 m_pos += aPos;
82 }
83
84 unsigned int Dist( const CN_ANCHOR& aSecond )
85 {
86 return ( m_pos - aSecond.Pos() ).EuclideanNorm();
87 }
88
90 int GetTag() const { return m_tag; }
91 void SetTag( int aTag ) { m_tag = aTag; }
92
94 const bool& GetNoLine() const { return m_noline; }
95 void SetNoLine( bool aEnable ) { m_noline = aEnable; }
96
97 const std::shared_ptr<CN_CLUSTER>& GetCluster() const { return m_cluster; }
98 void SetCluster( std::shared_ptr<CN_CLUSTER>& aCluster ) { m_cluster = aCluster; }
99
107 bool IsDangling() const;
108
112 int ConnectedItemsCount() const;
113
114 // Tag used for unconnected items.
115 static const int TAG_UNCONNECTED = -1;
116
117private:
120 int m_tag;
121 bool m_noline;
122
123 std::shared_ptr<CN_CLUSTER> m_cluster;
124};
125
126
127
133{
134public:
135 void Dump();
136
137 CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
138 {
139 m_parent = aParent;
140 m_canChangeNet = aCanChangeNet;
141 m_valid = true;
142 m_dirty = true;
143 m_anchors.reserve( std::max( 6, aAnchorCount ) );
144 m_start_layer = 0;
145 m_end_layer = std::numeric_limits<int>::max();
146 m_connected.reserve( 8 );
147 }
148
149 virtual ~CN_ITEM()
150 {
151 for( const std::shared_ptr<CN_ANCHOR>& anchor : m_anchors )
152 anchor->SetItem( nullptr );
153 };
154
155 std::shared_ptr<CN_ANCHOR> AddAnchor( const VECTOR2I& aPos )
156 {
157 m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
158 return m_anchors.at( m_anchors.size() - 1 );
159 }
160
161 std::vector<std::shared_ptr<CN_ANCHOR>>& Anchors() { return m_anchors; }
162
163 void SetValid( bool aValid ) { m_valid = aValid; }
164 bool Valid() const { return m_valid; }
165
166 void SetDirty( bool aDirty ) { m_dirty = aDirty; }
167 bool Dirty() const { return m_dirty; }
168
172 void SetLayers( int aStartLayer, int aEndLayer )
173 {
174 // B_Cu is nominally layer 2 but we reset it to INT_MAX to ensure that it is
175 // always greater than any other layer in the RTree
176 if( aStartLayer == B_Cu )
177 aStartLayer = std::numeric_limits<int>::max();
178
179 if( aEndLayer == B_Cu )
180 aEndLayer = std::numeric_limits<int>::max();
181
182 m_start_layer = aStartLayer;
183 m_end_layer = aEndLayer;
184 }
185
189 void SetLayer( int aLayer ) { SetLayers( aLayer, aLayer ); }
190
194 int StartLayer() const { return m_start_layer; }
195 int EndLayer() const { return m_end_layer; }
196
202 virtual int Layer() const
203 {
204 return StartLayer();
205 }
206
212 {
213 int layer = Layer();
214
215 if( layer == std::numeric_limits<int>::max() )
216 layer = B_Cu;
217
218 return ToLAYER_ID( layer );
219 }
220
221 const BOX2I& BBox()
222 {
223 if( m_dirty && m_valid )
224 m_bbox = m_parent->GetBoundingBox();
225
226 return m_bbox;
227 }
228
230
231 const std::vector<CN_ITEM*>& ConnectedItems() const { return m_connected; }
232 void ClearConnections() { m_connected.clear(); }
233
234 bool CanChangeNet() const { return m_canChangeNet; }
235
236 void Connect( CN_ITEM* b )
237 {
238 std::lock_guard<std::mutex> lock( m_listLock );
239
240 auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
241
242 if( i != m_connected.end() && *i == b )
243 return;
244
245 m_connected.insert( i, b );
246 }
247
248 void RemoveInvalidRefs();
249
250 virtual int AnchorCount() const;
251 virtual const VECTOR2I GetAnchor( int n ) const;
252
253 int Net() const
254 {
255 return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
256 }
257
258protected:
259 bool m_dirty;
264
265private:
267
268 std::vector<CN_ITEM*> m_connected;
269 std::vector<std::shared_ptr<CN_ANCHOR>> m_anchors;
270
272
273 bool m_valid;
274
275 std::mutex m_listLock;
276};
277
278
279/*
280 * Represents a single outline of a zone fill on a particular layer. \a aSubpolyIndex indicates
281 * which outline in the fill's SHAPE_POLY_SET.
282 */
283class CN_ZONE_LAYER : public CN_ITEM
284{
285public:
286 CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex ) :
287 CN_ITEM( aParent, false ),
288 m_zone( aParent ),
289 m_subpolyIndex( aSubpolyIndex ),
290 m_layer( aLayer )
291 {
292 m_fillPoly = aParent->GetFilledPolysList( aLayer );
293 SetLayers( aLayer, aLayer );
294 }
295
297 {
298 if( m_zone->IsTeardropArea() )
299 return;
300
301 for( unsigned int ii = 0; ii < m_fillPoly->TriangulatedPolyCount(); ++ii )
302 {
303 const auto* triangleSet = m_fillPoly->TriangulatedPolygon( ii );
304
305 if( triangleSet->GetSourceOutlineIndex() != m_subpolyIndex )
306 continue;
307
308 for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : triangleSet->Triangles() )
309 {
310 BOX2I bbox = tri.BBox();
311 const int mmin[2] = { bbox.GetX(), bbox.GetY() };
312 const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
313
314 m_rTree.Insert( mmin, mmax, &tri );
315 }
316 }
317 }
318
319 int SubpolyIndex() const { return m_subpolyIndex; }
320
321 PCB_LAYER_ID GetLayer() const { return m_layer; }
322
323 bool ContainsPoint( const VECTOR2I& p ) const
324 {
325 if( m_zone->IsTeardropArea() )
326 return m_fillPoly->Outline( m_subpolyIndex ).Collide( p ) ;
327
328 int min[2] = { p.x, p.y };
329 int max[2] = { p.x, p.y };
330 bool collision = false;
331
332 auto visitor =
333 [&]( const SHAPE* aShape ) -> bool
334 {
335 if( aShape->Collide( p ) )
336 {
337 collision = true;
338 return false;
339 }
340
341 return true;
342 };
343
344 m_rTree.Search( min, max, visitor );
345
346 return collision;
347 }
348
350
351 virtual int AnchorCount() const override;
352 virtual const VECTOR2I GetAnchor( int n ) const override;
353
355 {
356 return m_fillPoly->Outline( m_subpolyIndex );
357 }
358
359 bool Collide( SHAPE* aRefShape ) const
360 {
361 if( m_zone->IsTeardropArea() )
362 return m_fillPoly->Collide( aRefShape );
363
364 BOX2I bbox = aRefShape->BBox();
365 int min[2] = { bbox.GetX(), bbox.GetY() };
366 int max[2] = { bbox.GetRight(), bbox.GetBottom() };
367 bool collision = false;
368
369 auto visitor =
370 [&]( const SHAPE* aShape ) -> bool
371 {
372 if( aRefShape->Collide( aShape ) )
373 {
374 collision = true;
375 return false;
376 }
377
378 return true;
379 };
380
381 m_rTree.Search( min, max, visitor );
382
383 return collision;
384 }
385
386 bool HasSingleConnection();
387
388private:
392 std::shared_ptr<SHAPE_POLY_SET> m_fillPoly;
393 RTree<const SHAPE*, int, 2, double> m_rTree;
394};
395
396
397
398
400{
401public:
403 {
404 m_dirty = false;
405 m_hasInvalid = false;
406 }
407
408 void Clear()
409 {
410 for( CN_ITEM* item : m_items )
411 delete item;
412
413 m_items.clear();
414 m_index.RemoveAll();
415 }
416
417 std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
418 std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
419
420 std::vector<CN_ITEM*>::const_iterator begin() const { return m_items.begin(); }
421 std::vector<CN_ITEM*>::const_iterator end() const { return m_items.end(); }
422
423 CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
424
425 template <class T>
426 void FindNearby( CN_ITEM* aItem, T aFunc )
427 {
428 m_index.Query( aItem->BBox(), aItem->StartLayer(), aItem->EndLayer(), aFunc );
429 }
430
431 void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
432
433 void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
434 bool IsDirty() const { return m_dirty; }
435
436 void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
437
439 {
440 for( CN_ITEM* item : m_items )
441 item->SetDirty( false );
442
443 SetDirty( false );
444 }
445
446 int Size() const { return m_items.size(); }
447
448 CN_ITEM* Add( PAD* pad );
449 CN_ITEM* Add( PCB_TRACK* track );
450 CN_ITEM* Add( PCB_ARC* track );
451 CN_ITEM* Add( PCB_VIA* via );
452 CN_ITEM* Add( CN_ZONE_LAYER* zitem );
453 CN_ITEM* Add( PCB_SHAPE* shape );
454
455 const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
456
457protected:
458 void addItemtoTree( CN_ITEM* item )
459 {
460 m_index.Insert( item );
461 }
462
463protected:
464 std::vector<CN_ITEM*> m_items;
465
466private:
470};
471
472
474{
475public:
476 CN_CLUSTER();
477 ~CN_CLUSTER();
478
479 bool HasValidNet() const { return m_originNet > 0; }
480 int OriginNet() const { return m_originNet; }
481
482 wxString OriginNetName() const;
483
484 bool Contains( const CN_ITEM* aItem );
485 bool Contains( const BOARD_CONNECTED_ITEM* aItem );
486 void Dump();
487
488 int Size() const { return m_items.size(); }
489
490 bool IsOrphaned() const
491 {
492 return m_originPad == nullptr;
493 }
494
495 bool IsConflicting() const { return m_conflicting; }
496
497 void Add( CN_ITEM* item );
498
499 std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
500 std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
501
502private:
506 std::vector<CN_ITEM*> m_items;
507 std::unordered_map<int, int> m_netRanks;
508};
509
510
511
512#endif /* PCBNEW_CONNECTIVITY_ITEMS_H */
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
constexpr coord_type GetY() const
Definition box2.h:208
constexpr coord_type GetX() const
Definition box2.h:207
constexpr coord_type GetRight() const
Definition box2.h:217
constexpr coord_type GetBottom() const
Definition box2.h:222
void SetTag(int aTag)
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)
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
const std::shared_ptr< CN_CLUSTER > & GetCluster() const
unsigned int Dist(const CN_ANCHOR &aSecond)
void SetCluster(std::shared_ptr< CN_CLUSTER > &aCluster)
const VECTOR2I & Pos() const
bool Dirty() const
CN_ITEM * Item() const
int m_tag
Tag for quick connection resolution.
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...
void SetItem(CN_ITEM *aItem)
int Size() const
std::vector< CN_ITEM * >::iterator end()
std::vector< CN_ITEM * > m_items
bool IsConflicting() const
bool IsOrphaned() const
bool Contains(const CN_ITEM *aItem)
void Add(CN_ITEM *item)
CN_ITEM * m_originPad
std::vector< CN_ITEM * >::iterator begin()
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 Connect(CN_ITEM *b)
virtual ~CN_ITEM()
const BOX2I & BBox()
virtual int AnchorCount() const
void RemoveInvalidRefs()
std::vector< CN_ITEM * > m_connected
list of physically touching items
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
int m_start_layer
start layer of the item N.B. B_Cu is set to INT_MAX
void SetValid(bool aValid)
BOARD_CONNECTED_ITEM * m_parent
int m_end_layer
end layer of the item N.B. B_Cu is set to INT_MAX
bool Valid() const
int StartLayer() const
Return the contiguous set of layers spanned by the item.
std::shared_ptr< CN_ANCHOR > AddAnchor(const VECTOR2I &aPos)
void SetLayers(int aStartLayer, int aEndLayer)
Set the layers spanned by the item to aStartLayer and aEndLayer.
void ClearConnections()
BOX2I m_bbox
bounding box for the item
virtual const VECTOR2I GetAnchor(int n) const
PCB_LAYER_ID GetBoardLayer() const
When using CN_ITEM layers to compare against board items, use this function which correctly remaps th...
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)
int EndLayer() const
void SetLayer(int aLayer)
Set the layers spanned by the item to a single layer aLayer.
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
std::mutex m_listLock
mutex protecting this item's connected_items set to
CN_RTREE< CN_ITEM * > m_index
CN_ITEM * operator[](int aIndex)
CN_ITEM * Add(PAD *pad)
std::vector< CN_ITEM * >::iterator begin()
std::vector< CN_ITEM * >::const_iterator begin() const
void SetDirty(bool aDirty=true)
int Size() const
std::vector< CN_ITEM * >::const_iterator end() const
bool IsDirty() const
std::vector< CN_ITEM * >::iterator end()
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)
CN_RTREE - Implements an R-tree for fast spatial indexing of connectivity items.
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
PCB_LAYER_ID m_layer
PCB_LAYER_ID GetLayer()
std::shared_ptr< SHAPE_POLY_SET > m_fillPoly
bool ContainsPoint(const VECTOR2I &p) const
Definition pad.h:54
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:126
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:181
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:74
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition zone.h:600
PCB_LAYER_ID
A quick note on layer IDs:
Definition layer_ids.h:60
@ B_Cu
Definition layer_ids.h:65
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition lset.cpp:737
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695