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-2023 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<const CN_ANCHOR> GetSourceNode() const { return m_source; }
91 std::shared_ptr<const CN_ANCHOR> GetTargetNode() const { return m_target; }
92
93 void SetSourceNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_source = aNode; }
94 void SetTargetNode( const std::shared_ptr<const 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<const CN_ANCHOR> m_source;
111 std::shared_ptr<const 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
217 void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
218
219 void FindIsolatedCopperIslands( ZONE* aZone, PCB_LAYER_ID aLayer, std::vector<int>& aIslands );
220
229 void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones,
230 bool aConnectivityAlreadyRebuilt );
231
232 const CLUSTERS& GetClusters();
233
234 const CN_LIST& ItemList() const
235 {
236 return m_itemList;
237 }
238
239 template <typename Func>
240 void ForEachAnchor( Func&& aFunc ) const
241 {
242 for( CN_ITEM* item : m_itemList )
243 {
244 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
245 aFunc( *anchor );
246 }
247 }
248
249 template <typename Func>
250 void ForEachItem( Func&& aFunc ) const
251 {
252 for( CN_ITEM* item : m_itemList )
253 aFunc( *item );
254 }
255
256 void MarkNetAsDirty( int aNet );
257 void SetProgressReporter( PROGRESS_REPORTER* aReporter );
258
259private:
260 void searchConnections();
261
262 void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
263
264 template <class Container, class BItem>
265 void add( Container& c, BItem brditem )
266 {
267 CN_ITEM* item = c.Add( brditem );
268
269 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
270 }
271
272 void markItemNetAsDirty( const BOARD_ITEM* aItem );
273
274private:
276 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
277
278 std::vector<std::shared_ptr<CN_CLUSTER>> m_connClusters;
279 std::vector<std::shared_ptr<CN_CLUSTER>> m_ratsnestClusters;
280 std::vector<bool> m_dirtyNets;
281
283};
284
285
287{
288public:
289 CN_VISITOR( CN_ITEM* aItem ) :
290 m_item( aItem )
291 {}
292
293 bool operator()( CN_ITEM* aCandidate );
294
295protected:
296 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
297
298 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
299
300protected:
302};
303
304#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:58
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
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void GetDirtyClusters(CLUSTERS &aClusters) const
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
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
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagate nets from pads to other items in clusters.
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.
std::shared_ptr< const CN_ANCHOR > GetSourceNode() const
std::shared_ptr< const CN_ANCHOR > m_target
void SetTargetNode(const std::shared_ptr< const CN_ANCHOR > &aNode)
void SetWeight(unsigned weight)
void SetSourceNode(const std::shared_ptr< const CN_ANCHOR > &aNode)
void SetVisible(bool aVisible)
const unsigned GetLength() const
unsigned GetWeight() const
std::shared_ptr< const CN_ANCHOR > GetTargetNode() const
unsigned m_weight
const VECTOR2I GetTargetPos() const
std::shared_ptr< const CN_ANCHOR > m_source
CN_EDGE(const std::shared_ptr< CN_ANCHOR > &aSource, const std::shared_ptr< CN_ANCHOR > &aTarget, unsigned aWeight=0)
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
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59