KiCad PCB EDA Suite
tracks_cleaner.cpp
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) 2004-2018 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
6  * Copyright (C) 1992-2020 KiCad Developers, see AUTHORS.txt for contributors.
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #include <fctsys.h>
27 #include <reporter.h>
28 #include <board_commit.h>
29 #include <cleanup_item.h>
32 #include <tool/tool_manager.h>
33 #include <tools/pcb_actions.h>
34 #include <tools/global_edit_tool.h>
35 #include <tracks_cleaner.h>
36 
37 
39  m_brd( aPcb ),
40  m_commit( aCommit ),
41  m_dryRun( true ),
42  m_itemsList( nullptr )
43 {
44 }
45 
46 
47 /* Main cleaning function.
48  * Delete
49  * - Redundant points on tracks (merge aligned segments)
50  * - vias on pad
51  * - null length segments
52  */
53 void TRACKS_CLEANER::CleanupBoard( bool aDryRun, std::vector<CLEANUP_ITEM*>* aItemsList,
54  bool aRemoveMisConnected, bool aCleanVias, bool aMergeSegments,
55  bool aDeleteUnconnected, bool aDeleteTracksinPad, bool aDeleteDanglingVias )
56 {
57  bool has_deleted = false;
58 
59  m_dryRun = aDryRun;
60  m_itemsList = aItemsList;
61 
62  // Clear the flag used to mark some segments as deleted, in dry run:
63  for( TRACK* segment : m_brd->Tracks() )
64  segment->ClearFlags( IS_DELETED );
65 
66  // delete redundant vias
67  if( aCleanVias )
68  cleanupVias();
69 
70  // Remove null segments and intermediate points on aligned segments
71  // If not asked, remove null segments only if remove misconnected is asked
72  if( aMergeSegments )
74  else if( aRemoveMisConnected )
76 
77  if( aRemoveMisConnected )
79 
80  if( aDeleteTracksinPad )
82 
83  // Delete dangling tracks
84  if( aDeleteUnconnected )
85  has_deleted = deleteDanglingTracks( false );
86 
87  // Delete dangling vias
88  if( aDeleteDanglingVias )
89  has_deleted |= deleteDanglingTracks( true );
90 
91  if( has_deleted && aMergeSegments )
93 
94  // Clear the flag used to mark some segments:
95  for( TRACK* segment : m_brd->Tracks() )
96  segment->ClearFlags( IS_DELETED );
97 }
98 
99 
101 {
102  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
103 
104  std::set<BOARD_ITEM *> toRemove;
105 
106  for( TRACK* segment : m_brd->Tracks() )
107  {
108  for( D_PAD* testedPad : connectivity->GetConnectedPads( segment ) )
109  {
110  if( segment->GetNetCode() != testedPad->GetNetCode() )
111  {
112  CLEANUP_ITEM* item = new CLEANUP_ITEM( CLEANUP_SHORT );
113  item->SetItems( segment );
114  m_itemsList->push_back( item );
115 
116  toRemove.insert( segment );
117  }
118  }
119 
120  for( TRACK* testedTrack : connectivity->GetConnectedTracks( segment ) )
121  {
122  if( segment->GetNetCode() != testedTrack->GetNetCode() )
123  {
124  CLEANUP_ITEM* item = new CLEANUP_ITEM( CLEANUP_SHORT );
125  item->SetItems( segment );
126  m_itemsList->push_back( item );
127 
128  toRemove.insert( segment );
129  }
130  }
131  }
132 
133  if( !m_dryRun )
134  removeItems( toRemove );
135 }
136 
137 
139 {
140  std::set<BOARD_ITEM*> toRemove;
141  std::vector<VIA*> vias;
142 
143  for( TRACK* track : m_brd->Tracks() )
144  {
145  if( auto via = dyn_cast<VIA*>( track ) )
146  vias.push_back( via );
147  }
148 
149  for( auto via1_it = vias.begin(); via1_it != vias.end(); via1_it++ )
150  {
151  VIA* via1 = *via1_it;
152 
153  if( via1->IsLocked() )
154  continue;
155 
156  if( via1->GetStart() != via1->GetEnd() )
157  via1->SetEnd( via1->GetStart() );
158 
159  // To delete through Via on THT pads at same location
160  // Examine the list of connected pads:
161  // if a through pad is found, the via can be removed
162 
163  const std::vector<D_PAD*> pads = m_brd->GetConnectivity()->GetConnectedPads( via1 );
164 
165  for( D_PAD* pad : pads )
166  {
167  const LSET all_cu = LSET::AllCuMask();
168 
169  if( ( pad->GetLayerSet() & all_cu ) == all_cu )
170  {
172  item->SetItems( via1, pad );
173  m_itemsList->push_back( item );
174 
175  // redundant: delete the via
176  toRemove.insert( via1 );
177  break;
178  }
179  }
180 
181  for( auto via2_it = via1_it + 1; via2_it != vias.end(); via2_it++ )
182  {
183  VIA* via2 = *via2_it;
184 
185  if( via1->GetPosition() != via2->GetPosition() || via2->IsLocked() )
186  continue;
187 
188  if( via1->GetViaType() == via2->GetViaType() )
189  {
191  item->SetItems( via1, via2 );
192  m_itemsList->push_back( item );
193 
194  toRemove.insert( via2 );
195  break;
196  }
197  }
198  }
199 
200  if( !m_dryRun )
201  removeItems( toRemove );
202 }
203 
204 
205 bool TRACKS_CLEANER::testTrackEndpointIsNode( TRACK* aTrack, bool aTstStart )
206 {
207  // A node is a point where more than 2 items are connected.
208 
209  auto connectivity = m_brd->GetConnectivity();
210  auto items = connectivity->GetConnectivityAlgo()->ItemEntry( aTrack ).GetItems();
211 
212  if( items.empty() )
213  return false;
214 
215  auto citem = items.front();
216 
217  if( !citem->Valid() )
218  return false;
219 
220  auto anchors = citem->Anchors();
221 
222  VECTOR2I refpoint = aTstStart ? aTrack->GetStart() : aTrack->GetEnd();
223 
224  for( const auto& anchor : anchors )
225  {
226  if( anchor->Pos() != refpoint )
227  continue;
228 
229  // The right anchor point is found: if more than one other item
230  // (pad, via, track...) is connected, it is a node:
231  return anchor->ConnectedItemsCount() > 1;
232  }
233 
234  return false;
235 }
236 
237 
239 {
240  bool item_erased = false;
241  bool modified = false;
242 
243  do // Iterate when at least one track is deleted
244  {
245  item_erased = false;
246  // Ensure the connectivity is up to date, especially after removind a dangling segment
248 
249  // Keep a duplicate deque to all deleting in the primary
250  std::deque<TRACK*> temp_tracks( m_brd->Tracks() );
251 
252  for( TRACK* track : temp_tracks )
253  {
254  bool flag_erase = false; // Start without a good reason to erase it
255 
256  if( aVia && track->Type() != PCB_VIA_T )
257  continue;
258  else if( !aVia && track->Type() == PCB_VIA_T )
259  continue;
260 
261  // Tst if a track (or a via) endpoint is not connected to another track or to a zone.
262  if( m_brd->GetConnectivity()->TestTrackEndpointDangling( track ) )
263  flag_erase = true;
264 
265  if( flag_erase )
266  {
267  int errorCode =
268  ( track->Type() != PCB_VIA_T ) ?
270  CLEANUP_ITEM* item = new CLEANUP_ITEM( errorCode );
271  item->SetItems( track );
272  m_itemsList->push_back( item );
273 
274  if( !m_dryRun )
275  {
276  m_brd->Remove( track );
277  m_commit.Removed( track );
278 
279  /* keep iterating, because a track connected to the deleted track
280  * now perhaps is not connected and should be deleted */
281  item_erased = true;
282  modified = true;
283  }
284  // Fix me: In dry run we should disable the track to erase and retry with this disabled track
285  // However the connectivity algo does not handle disabled items.
286  }
287  }
288  } while( item_erased ); // A segment was erased: test for some new dangling segments
289 
290  return modified;
291 }
292 
293 
294 // Delete null length track segments
295 void TRACKS_CLEANER::deleteNullSegments( TRACKS& aTracks )
296 {
297  std::set<BOARD_ITEM *> toRemove;
298 
299  for( TRACK* segment : aTracks )
300  {
301  if( segment->IsNull() && segment->Type() == PCB_TRACE_T && !segment->IsLocked() )
302  {
304  item->SetItems( segment );
305  m_itemsList->push_back( item );
306 
307  toRemove.insert( segment );
308  }
309  }
310 
311  if( !m_dryRun )
312  removeItems( toRemove );
313 }
314 
315 
317 {
318  std::set<BOARD_ITEM*> toRemove;
319 
320  // Delete tracks that start and end on the same pad
321  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
322 
323  for( TRACK* track : m_brd->Tracks() )
324  {
325  if( track->Type() == PCB_VIA_T )
326  continue;
327 
328  // Mark track if connected to pads
329  for( D_PAD* pad : connectivity->GetConnectedPads( track ) )
330  {
331  if( pad->HitTest( track->GetStart() ) && pad->HitTest( track->GetEnd() ) )
332  {
333  SHAPE_POLY_SET poly;
334  track->TransformShapeWithClearanceToPolygon( poly, 0 );
335 
336  poly.BooleanSubtract( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
337 
338  if( poly.IsEmpty() )
339  {
341  item->SetItems( track );
342  m_itemsList->push_back( item );
343 
344  toRemove.insert( track );
345  }
346  }
347  }
348  }
349 
350  if( !m_dryRun )
351  removeItems( toRemove );
352 }
353 
354 
355 // Delete null length segments, and intermediate points ..
357 {
358  // Easy things first
360 
361  std::set<BOARD_ITEM*> toRemove;
362 
363  // Remove duplicate segments (2 superimposed identical segments):
364  for( auto it = m_brd->Tracks().begin(); it != m_brd->Tracks().end(); it++ )
365  {
366  TRACK* track1 = *it;
367 
368  if( track1->Type() != PCB_TRACE_T || track1->HasFlag( IS_DELETED ) || track1->IsLocked() )
369  continue;
370 
371  for( auto it2 = it + 1; it2 != m_brd->Tracks().end(); it2++ )
372  {
373  TRACK* track2 = *it2;
374 
375  if( track2->HasFlag( IS_DELETED ) )
376  continue;
377 
378  if( track1->IsPointOnEnds( track2->GetStart() )
379  && track1->IsPointOnEnds( track2->GetEnd() )
380  && track1->GetWidth() == track2->GetWidth()
381  && track1->GetLayer() == track2->GetLayer() )
382  {
384  item->SetItems( track2 );
385  m_itemsList->push_back( item );
386 
387  track2->SetFlags( IS_DELETED );
388  toRemove.insert( track2 );
389  }
390  }
391  }
392 
393  if( !m_dryRun )
394  removeItems( toRemove );
395 
396  bool merged = false;
397 
398  do
399  {
401 
402  // Keep a duplicate deque to all deleting in the primary
403  std::deque<TRACK*> temp_segments( m_brd->Tracks() );
404 
405  // merge collinear segments:
406  for( TRACK* segment : temp_segments )
407  {
408  if( segment->Type() != PCB_TRACE_T ) // one can merge only track collinear segments, not vias.
409  continue;
410 
411  if( segment->HasFlag( IS_DELETED ) ) // already taken in account
412  continue;
413 
414  auto connectivity = m_brd->GetConnectivity();
415 
416  auto& entry = connectivity->GetConnectivityAlgo()->ItemEntry( segment );
417 
418  for( CN_ITEM* citem : entry.GetItems() )
419  {
420  for( CN_ITEM* connected : citem->ConnectedItems() )
421  {
422  if( !connected->Valid() )
423  continue;
424 
425  BOARD_CONNECTED_ITEM* candidateItem = connected->Parent();
426 
427  if( candidateItem->Type() == PCB_TRACE_T && !candidateItem->HasFlag( IS_DELETED ) )
428  {
429  TRACK* candidateSegment = static_cast<TRACK*>( candidateItem );
430 
431  // Do not merge segments having different widths: it is a frequent case
432  // to draw a track between 2 pads:
433  if( candidateSegment->GetWidth() != segment->GetWidth() )
434  continue;
435 
436  if( segment->ApproxCollinear( *candidateSegment ) )
437  merged = mergeCollinearSegments( segment, candidateSegment );
438  }
439  }
440  }
441  }
442  } while( merged );
443 }
444 
445 
447 {
448  if( aSeg1->IsLocked() || aSeg2->IsLocked() )
449  return false;
450 
451  auto connectivity = m_brd->GetConnectivity();
452 
453  // Verify the removed point after merging is not a node.
454  // If it is a node (i.e. if more than one other item is connected, the segments cannot be merged
455  TRACK dummy_seg( *aSeg1 );
456 
457  // Calculate the new ends of the segment to merge, and store them to dummy_seg:
458  int min_x = std::min( aSeg1->GetStart().x,
459  std::min( aSeg1->GetEnd().x, std::min( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
460  int min_y = std::min( aSeg1->GetStart().y,
461  std::min( aSeg1->GetEnd().y, std::min( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
462  int max_x = std::max( aSeg1->GetStart().x,
463  std::max( aSeg1->GetEnd().x, std::max( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
464  int max_y = std::max( aSeg1->GetStart().y,
465  std::max( aSeg1->GetEnd().y, std::max( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
466 
467  if( ( aSeg1->GetStart().x > aSeg1->GetEnd().x )
468  == ( aSeg1->GetStart().y > aSeg1->GetEnd().y ) )
469  {
470  dummy_seg.SetStart( wxPoint( min_x, min_y ) );
471  dummy_seg.SetEnd( wxPoint( max_x, max_y ) );
472  }
473  else
474  {
475  dummy_seg.SetStart( wxPoint( min_x, max_y ) );
476  dummy_seg.SetEnd( wxPoint( max_x, min_y ) );
477  }
478 
479  // Now find the removed end(s) and stop merging if it is a node:
480  if( aSeg1->GetStart() != dummy_seg.GetStart() && aSeg1->GetStart() != dummy_seg.GetEnd() )
481  {
482  if( testTrackEndpointIsNode( aSeg1, true ) )
483  return false;
484  }
485 
486  if( aSeg1->GetEnd() != dummy_seg.GetStart() && aSeg1->GetEnd() != dummy_seg.GetEnd() )
487  {
488  if( testTrackEndpointIsNode( aSeg1, false ) )
489  return false;
490  }
491 
493  item->SetItems( aSeg1, aSeg2 );
494  m_itemsList->push_back( item );
495 
496  aSeg2->SetFlags( IS_DELETED );
497 
498  if( !m_dryRun )
499  {
500  m_commit.Modify( aSeg1 );
501  *aSeg1 = dummy_seg;
502 
503  connectivity->Update( aSeg1 );
504 
505  // Clear the status flags here after update.
506  for( auto pad : connectivity->GetConnectedPads( aSeg1 ) )
507  {
508  aSeg1->SetState( BEGIN_ONPAD, pad->HitTest( aSeg1->GetStart() ) );
509  aSeg1->SetState( END_ONPAD, pad->HitTest( aSeg1->GetEnd() ) );
510  }
511 
512  // Merge succesful, seg2 has to go away
513  m_brd->Remove( aSeg2 );
514  m_commit.Removed( aSeg2 );
515  }
516 
517  return true;
518 }
519 
520 
521 void TRACKS_CLEANER::removeItems( std::set<BOARD_ITEM*>& aItems )
522 {
523  for( auto item : aItems )
524  {
525  m_brd->Remove( item );
526  m_commit.Removed( item );
527  }
528 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:138
const CONNECTED_ITEMS & ConnectedItems() const
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Function AllCuMask returns a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:712
COMMIT & Modify(EDA_ITEM *aItem)
Modifies a given item in the model.
Definition: commit.h:103
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: base_struct.h:136
void deleteNullSegments(TRACKS &aTracks)
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:114
const wxPoint & GetStart() const
Definition: class_track.h:118
void SetItems(EDA_ITEM *aItem, EDA_ITEM *bItem=nullptr, EDA_ITEM *cItem=nullptr, EDA_ITEM *dItem=nullptr)
Definition: rc_item.h:115
std::vector< CLEANUP_ITEM * > * m_itemsList
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
void cleanupVias()
Removes redundant vias like vias at same location or on pad through.
TRACKS_CLEANER(BOARD *aPcb, BOARD_COMMIT &aCommit)
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: base_struct.h:135
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:96
BOARD_COMMIT & m_commit
COMMIT & Removed(EDA_ITEM *aItem)
Notifies observers that aItem has been removed
Definition: commit.h:96
bool deleteDanglingTracks(bool aVia)
Removes tracks or vias only connected on one end.
void cleanupSegments()
Merge collinear segments and remove duplicated and null length segments.
LSET is a set of PCB_LAYER_IDs.
void SetFlags(STATUS_FLAGS aMask)
Definition: base_struct.h:232
SHAPE_POLY_SET.
#define IS_DELETED
Definition: base_struct.h:120
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Function GetConnectivity() returns list of missing connections between components/tracks.
Definition: class_board.h:355
bool mergeCollinearSegments(TRACK *aSeg1, TRACK *aSeg2)
helper function merge aTrackRef and aCandidate, when possible, i.e.
void removeItems(std::set< BOARD_ITEM * > &aItems)
void BuildConnectivity()
Builds or rebuilds the board connectivity database for the board, especially the list of connected it...
void SetState(int type, int state)
Definition: base_struct.h:221
int GetWidth() const
Definition: class_track.h:112
STATUS_FLAGS IsPointOnEnds(const wxPoint &point, int min_dist=0) const
Function IsPointOnEnds returns STARTPOINT if point if near (dist = min_dist) start point,...
BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:180
void CleanupBoard(bool aDryRun, std::vector< CLEANUP_ITEM * > *aItemsList, bool aCleanVias, bool aRemoveMisConnected, bool aMergeSegments, bool aDeleteUnconnected, bool aDeleteTracksinPad, bool aDeleteDanglingVias)
the cleanup function.
VIATYPE GetViaType() const
Definition: class_track.h:378
const wxPoint & GetEnd() const
Definition: class_track.h:115
void removeBadTrackSegments()
void SetStart(const wxPoint &aStart)
Definition: class_track.h:117
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
bool HasFlag(STATUS_FLAGS aFlag)
Definition: base_struct.h:235
wxPoint GetPosition() const override
Definition: class_track.h:416
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
void Remove(BOARD_ITEM *aBoardItem) override
Removes an item from the container.
TRACKS & Tracks()
Definition: class_board.h:257
KICAD_T Type() const
Function Type()
Definition: base_struct.h:193
bool testTrackEndpointIsNode(TRACK *aTrack, bool aTstStart)