KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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
49
50class CN_RATSNEST_NODES;
51class BOARD;
53class BOARD_ITEM;
54class ZONE;
56
57
63{
64public:
66 m_weight( 0 ),
67 m_visible( true )
68 {}
69
70 CN_EDGE( const std::shared_ptr<CN_ANCHOR>& aSource, const std::shared_ptr<CN_ANCHOR>& aTarget,
71 unsigned aWeight = 0 ) :
72 m_source( aSource ),
73 m_target( aTarget ),
74 m_weight( aWeight ),
75 m_visible( true )
76 {}
77
84 bool operator<( CN_EDGE aOther ) const
85 {
86 return m_weight < aOther.m_weight;
87 }
88
89 std::shared_ptr<const CN_ANCHOR> GetSourceNode() const { return m_source; }
90 std::shared_ptr<const CN_ANCHOR> GetTargetNode() const { return m_target; }
91
92 void SetSourceNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_source = aNode; }
93 void SetTargetNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_target = aNode; }
94
95 void SetWeight( unsigned weight ) { m_weight = weight; }
96 unsigned GetWeight() const { return m_weight; }
97
98 void SetVisible( bool aVisible ) { m_visible = aVisible; }
99 bool IsVisible() const { return m_visible; }
100
101 const VECTOR2I GetSourcePos() const { return m_source->Pos(); }
102 const VECTOR2I GetTargetPos() const { return m_target->Pos(); }
103 unsigned GetLength() const
104 {
105 return ( m_target->Pos() - m_source->Pos() ).EuclideanNorm();
106 }
107
108private:
109 std::shared_ptr<const CN_ANCHOR> m_source;
110 std::shared_ptr<const CN_ANCHOR> m_target;
111 unsigned m_weight;
113};
114
115
117{
118public:
120 {
124 };
125
126 using CLUSTERS = std::vector<std::shared_ptr<CN_CLUSTER>>;
127
128 /*
129 * Holds a list of CN_ITEMs for a given BOARD_CONNECTED_ITEM. For most items (pads, tracks,
130 * etc.) the list will have a single CN_ITEM, but for ZONEs it will have one item for each
131 * distinct outline on each layer.
132 */
134 {
135 public:
136 ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
137 {
138 if( aItem )
139 m_items.push_back( aItem );
140 }
141
143 {
144 for( CN_ITEM* item : m_items )
145 item->SetValid( false );
146 }
147
148 void Link( CN_ITEM* aItem )
149 {
150 m_items.push_back( aItem );
151 }
152
153 const std::list<CN_ITEM*>& GetItems() const
154 {
155 return m_items;
156 }
157
158 std::list<CN_ITEM*> m_items;
159 };
160
163
164 bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
165 {
166 return m_itemMap.find( aItem ) != m_itemMap.end();
167 }
168
170 {
171 return m_itemMap[ aItem ];
172 }
173
174 bool IsNetDirty( int aNet ) const
175 {
176 if( aNet < 0 )
177 return false;
178
179 return m_dirtyNets[ aNet ];
180 }
181
183 {
184 for( size_t ii = 0; ii < m_dirtyNets.size(); ii++ )
185 m_dirtyNets[ii] = false;
186 }
187
188 void GetDirtyClusters( CLUSTERS& aClusters ) const
189 {
190 for( const std::shared_ptr<CN_CLUSTER>& cl : m_ratsnestClusters )
191 {
192 int net = cl->OriginNet();
193
194 if( net >= 0 && m_dirtyNets[net] )
195 aClusters.push_back( cl );
196 }
197 }
198
199 int NetCount() const
200 {
201 return m_dirtyNets.size();
202 }
203
204 void Build( BOARD* aZoneLayer, PROGRESS_REPORTER* aReporter = nullptr );
205 void LocalBuild( const std::vector<BOARD_ITEM*>& aItems );
206
207 void Clear();
208
209 bool Remove( BOARD_ITEM* aItem );
210 bool Add( BOARD_ITEM* aItem );
211
213 const std::initializer_list<KICAD_T>& aTypes,
214 int aSingleNet, CN_ITEM* rootItem = nullptr );
216
221 void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
222
226 void FillIsolatedIslandsMap( std::map<ZONE*, std::map<PCB_LAYER_ID, ISOLATED_ISLANDS>>& aMap,
227 bool aConnectivityAlreadyRebuilt );
228
229 const CLUSTERS& GetClusters();
230
231 const CN_LIST& ItemList() const
232 {
233 return m_itemList;
234 }
235
236 template <typename Func>
237 void ForEachAnchor( Func&& aFunc ) const
238 {
239 for( CN_ITEM* item : m_itemList )
240 {
241 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
242 aFunc( *anchor );
243 }
244 }
245
246 template <typename Func>
247 void ForEachItem( Func&& aFunc ) const
248 {
249 for( CN_ITEM* item : m_itemList )
250 aFunc( *item );
251 }
252
253 void MarkNetAsDirty( int aNet );
254 void SetProgressReporter( PROGRESS_REPORTER* aReporter );
255
256private:
257 void searchConnections();
258
259 void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
260
261 template <class Container, class BItem>
262 void add( Container& c, BItem brditem )
263 {
264 CN_ITEM* item = c.Add( brditem );
265
266 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
267 }
268
269 void markItemNetAsDirty( const BOARD_ITEM* aItem );
270
271private:
273 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
274
275 std::vector<std::shared_ptr<CN_CLUSTER>> m_connClusters;
276 std::vector<std::shared_ptr<CN_CLUSTER>> m_ratsnestClusters;
277 std::vector<bool> m_dirtyNets;
278
280};
281
282
284{
285public:
286 CN_VISITOR( CN_ITEM* aItem ) :
287 m_item( aItem )
288 {}
289
290 bool operator()( CN_ITEM* aCandidate );
291
292protected:
293 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
294
295 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
296
297protected:
299};
300
301#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:71
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:270
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)
void FillIsolatedIslandsMap(std::map< ZONE *, std::map< PCB_LAYER_ID, ISOLATED_ISLANDS > > &aMap, bool aConnectivityAlreadyRebuilt)
Fill in the isolated islands map with copper islands that are not connected to a net.
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()
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)
unsigned GetWeight() const
std::shared_ptr< const CN_ANCHOR > GetTargetNode() const
unsigned m_weight
const VECTOR2I GetTargetPos() const
unsigned GetLength() 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:72