KiCad PCB EDA Suite
connectivity_algo.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) 2019-2022 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// #define CONNECTIVITY_DEBUG
29
30#ifndef __CONNECTIVITY_ALGO_H
31#define __CONNECTIVITY_ALGO_H
32
33#include <board.h>
34#include <pad.h>
35#include <footprint.h>
36#include <zone.h>
37
39
40#include <memory>
41#include <algorithm>
42#include <functional>
43#include <vector>
44#include <deque>
45#include <intrusive_list.h>
46
50
51class CN_RATSNEST_NODES;
52class BOARD;
54class BOARD_ITEM;
55class ZONE;
57
58
64{
65public:
67 m_weight( 0 ),
68 m_visible( true )
69 {}
70
71 CN_EDGE( const std::shared_ptr<CN_ANCHOR>& aSource, const std::shared_ptr<CN_ANCHOR>& aTarget,
72 unsigned aWeight = 0 ) :
73 m_source( aSource ),
74 m_target( aTarget ),
75 m_weight( aWeight ),
76 m_visible( true )
77 {}
78
85 bool operator<( CN_EDGE aOther ) const
86 {
87 return m_weight < aOther.m_weight;
88 }
89
90 std::shared_ptr<CN_ANCHOR> GetSourceNode() const { return m_source; }
91 std::shared_ptr<CN_ANCHOR> GetTargetNode() const { return m_target; }
92
93 void SetSourceNode( const std::shared_ptr<CN_ANCHOR>& aNode ) { m_source = aNode; }
94 void SetTargetNode( const std::shared_ptr<CN_ANCHOR>& aNode ) { m_target = aNode; }
95
96 void SetWeight( unsigned weight ) { m_weight = weight; }
97 unsigned GetWeight() const { return m_weight; }
98
99 void SetVisible( bool aVisible ) { m_visible = aVisible; }
100 bool IsVisible() const { return m_visible; }
101
102 const VECTOR2I GetSourcePos() const { return m_source->Pos(); }
103 const VECTOR2I GetTargetPos() const { return m_target->Pos(); }
104 const unsigned GetLength() const
105 {
106 return ( m_target->Pos() - m_source->Pos() ).EuclideanNorm();
107 }
108
109private:
110 std::shared_ptr<CN_ANCHOR> m_source;
111 std::shared_ptr<CN_ANCHOR> m_target;
112 unsigned m_weight;
114};
115
116
118{
119public:
121 {
125 };
126
127 using CLUSTERS = std::vector<std::shared_ptr<CN_CLUSTER>>;
128
130 {
131 public:
132 ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
133 {
134 if( aItem )
135 m_items.push_back( aItem );
136 }
137
139 {
140 for( CN_ITEM* item : m_items )
141 item->SetValid( false );
142 }
143
144 void Link( CN_ITEM* aItem )
145 {
146 m_items.push_back( aItem );
147 }
148
149 const std::list<CN_ITEM*> GetItems() const
150 {
151 return m_items;
152 }
153
154 std::list<CN_ITEM*> m_items;
155 };
156
159
160 bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
161 {
162 return m_itemMap.find( aItem ) != m_itemMap.end();
163 }
164
166 {
167 return m_itemMap[ aItem ];
168 }
169
170 bool IsNetDirty( int aNet ) const
171 {
172 if( aNet < 0 )
173 return false;
174
175 return m_dirtyNets[ aNet ];
176 }
177
179 {
180 for( size_t ii = 0; ii < m_dirtyNets.size(); ii++ )
181 m_dirtyNets[ii] = false;
182 }
183
184 void GetDirtyClusters( CLUSTERS& aClusters ) const
185 {
186 for( const std::shared_ptr<CN_CLUSTER>& cl : m_ratsnestClusters )
187 {
188 int net = cl->OriginNet();
189
190 if( net >= 0 && m_dirtyNets[net] )
191 aClusters.push_back( cl );
192 }
193 }
194
195 int NetCount() const
196 {
197 return m_dirtyNets.size();
198 }
199
200 void Build( BOARD* aZoneLayer, PROGRESS_REPORTER* aReporter = nullptr );
201 void LocalBuild( const std::vector<BOARD_ITEM*>& aItems );
202
203 void Clear();
204
205 bool Remove( BOARD_ITEM* aItem );
206 bool Add( BOARD_ITEM* aItem );
207
209 const std::initializer_list<KICAD_T>& aTypes,
210 int aSingleNet, CN_ITEM* rootItem = nullptr );
212
218 void PropagateNets( BOARD_COMMIT* aCommit = nullptr,
220
221 void FindIsolatedCopperIslands( ZONE* aZone, PCB_LAYER_ID aLayer, std::vector<int>& aIslands );
222
231 void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones,
232 bool aConnectivityAlreadyRebuilt );
233
234 const CLUSTERS& GetClusters();
235
236 const CN_LIST& ItemList() const
237 {
238 return m_itemList;
239 }
240
241 template <typename Func>
242 void ForEachAnchor( Func&& aFunc ) const
243 {
244 for( CN_ITEM* item : m_itemList )
245 {
246 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
247 aFunc( *anchor );
248 }
249 }
250
251 template <typename Func>
252 void ForEachItem( Func&& aFunc ) const
253 {
254 for( CN_ITEM* item : m_itemList )
255 aFunc( *item );
256 }
257
258 void MarkNetAsDirty( int aNet );
259 void SetProgressReporter( PROGRESS_REPORTER* aReporter );
260
261private:
262 void searchConnections();
263
264 void propagateConnections( BOARD_COMMIT* aCommit = nullptr,
266
267 template <class Container, class BItem>
268 void add( Container& c, BItem brditem )
269 {
270 CN_ITEM* item = c.Add( brditem );
271
272 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
273 }
274
275 void markItemNetAsDirty( const BOARD_ITEM* aItem );
276
277private:
279 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
280
281 std::vector<std::shared_ptr<CN_CLUSTER>> m_connClusters;
282 std::vector<std::shared_ptr<CN_CLUSTER>> m_ratsnestClusters;
283 std::vector<bool> m_dirtyNets;
284
286};
287
288
290{
291public:
292 CN_VISITOR( CN_ITEM* aItem ) :
293 m_item( aItem )
294 {}
295
296 bool operator()( CN_ITEM* aCandidate );
297
298protected:
299 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
300
301 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
302
303protected:
305};
306
307#endif
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:50
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:265
ITEM_MAP_ENTRY(CN_ITEM *aItem=nullptr)
const std::list< CN_ITEM * > GetItems() const
void MarkItemsAsInvalid()
std::list< CN_ITEM * > m_items
void Link(CN_ITEM *aItem)
bool Remove(BOARD_ITEM *aItem)
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem) const
void ForEachItem(Func &&aFunc) const
void add(Container &c, BItem brditem)
PROGRESS_REPORTER * m_progressReporter
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
void PropagateNets(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
Propagate nets from pads to other items in clusters.
void propagateConnections(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void GetDirtyClusters(CLUSTERS &aClusters) const
const CLUSTERS & GetClusters()
void FindIsolatedCopperIslands(ZONE *aZone, PCB_LAYER_ID aLayer, std::vector< int > &aIslands)
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const std::initializer_list< KICAD_T > &aTypes, int aSingleNet, CN_ITEM *rootItem=nullptr)
void Build(BOARD *aZoneLayer, PROGRESS_REPORTER *aReporter=nullptr)
void MarkNetAsDirty(int aNet)
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters
void ForEachAnchor(Func &&aFunc) const
const CN_LIST & ItemList() const
bool IsNetDirty(int aNet) const
std::vector< bool > m_dirtyNets
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
void LocalBuild(const std::vector< BOARD_ITEM * > &aItems)
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
bool Add(BOARD_ITEM *aItem)
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
void SetWeight(unsigned weight)
void SetVisible(bool aVisible)
const unsigned GetLength() const
unsigned GetWeight() const
std::shared_ptr< CN_ANCHOR > m_target
unsigned m_weight
const VECTOR2I GetTargetPos() const
std::shared_ptr< CN_ANCHOR > GetTargetNode() const
std::shared_ptr< CN_ANCHOR > m_source
CN_EDGE(const std::shared_ptr< CN_ANCHOR > &aSource, const std::shared_ptr< CN_ANCHOR > &aTarget, unsigned aWeight=0)
void SetTargetNode(const std::shared_ptr< CN_ANCHOR > &aNode)
std::shared_ptr< CN_ANCHOR > GetSourceNode() const
void SetSourceNode(const std::shared_ptr< CN_ANCHOR > &aNode)
const VECTOR2I GetSourcePos() const
bool IsVisible() const
bool operator<(CN_EDGE aOther) const
This sort operator provides a sort-by-weight for the ratsnest operation.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
CN_VISITOR(CN_ITEM *aItem)
void checkZoneItemConnection(CN_ZONE_LAYER *aZoneLayer, CN_ITEM *aItem)
CN_ITEM * m_item
The item we are looking for connections to.
void checkZoneZoneConnection(CN_ZONE_LAYER *aZoneLayerA, CN_ZONE_LAYER *aZoneLayerB)
bool operator()(CN_ITEM *aCandidate)
A progress reporter interface for use in multi-threaded environments.
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
PROPAGATE_MODE
Controls how nets are propagated through clusters.
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59