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 <reporter.h>
27 #include <board_commit.h>
28 #include <cleanup_item.h>
31 #include <tool/tool_manager.h>
32 #include <tools/pcb_actions.h>
33 #include <tools/global_edit_tool.h>
34 #include <drc/drc_rtree.h>
35 #include <tracks_cleaner.h>
36 
38  m_brd( aPcb ),
39  m_commit( aCommit ),
40  m_dryRun( true ),
41  m_itemsList( nullptr )
42 {
43 }
44 
45 
46 /* Main cleaning function.
47  * Delete
48  * - Redundant points on tracks (merge aligned segments)
49  * - vias on pad
50  * - null length segments
51  */
52 void TRACKS_CLEANER::CleanupBoard( bool aDryRun, std::vector<std::shared_ptr<CLEANUP_ITEM> >* aItemsList,
53  bool aRemoveMisConnected, bool aCleanVias, bool aMergeSegments,
54  bool aDeleteUnconnected, bool aDeleteTracksinPad, bool aDeleteDanglingVias )
55 {
56  bool has_deleted = false;
57 
58  m_dryRun = aDryRun;
59  m_itemsList = aItemsList;
60 
61  cleanup( aCleanVias, aMergeSegments || aRemoveMisConnected, aMergeSegments, aMergeSegments );
62 
63  if( aRemoveMisConnected )
65 
66  if( aDeleteTracksinPad )
68 
69  if( aDeleteUnconnected )
70  has_deleted = deleteDanglingTracks( false );
71 
72  if( aDeleteDanglingVias )
73  has_deleted |= deleteDanglingTracks( true );
74 
75  if( has_deleted && aMergeSegments )
76  cleanup( false, false, false, true );
77 }
78 
79 
81 {
82  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
83 
84  std::set<BOARD_ITEM *> toRemove;
85 
86  for( TRACK* segment : m_brd->Tracks() )
87  {
88  for( D_PAD* testedPad : connectivity->GetConnectedPads( segment ) )
89  {
90  if( segment->GetNetCode() != testedPad->GetNetCode() )
91  {
92  std::shared_ptr<CLEANUP_ITEM> item;
93 
94  if( segment->Type() == PCB_VIA_T )
95  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_SHORTING_VIA );
96  else
97  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_SHORTING_TRACK );
98 
99  item->SetItems( segment );
100  m_itemsList->push_back( item );
101 
102  toRemove.insert( segment );
103  }
104  }
105 
106  for( TRACK* testedTrack : connectivity->GetConnectedTracks( segment ) )
107  {
108  if( segment->GetNetCode() != testedTrack->GetNetCode() )
109  {
110  std::shared_ptr<CLEANUP_ITEM> item;
111 
112  if( segment->Type() == PCB_VIA_T )
113  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_SHORTING_VIA );
114  else
115  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_SHORTING_TRACK );
116 
117  item->SetItems( segment );
118  m_itemsList->push_back( item );
119 
120  toRemove.insert( segment );
121  }
122  }
123  }
124 
125  if( !m_dryRun )
126  removeItems( toRemove );
127 }
128 
129 
130 bool TRACKS_CLEANER::testTrackEndpointIsNode( TRACK* aTrack, bool aTstStart )
131 {
132  // A node is a point where more than 2 items are connected.
133 
134  auto connectivity = m_brd->GetConnectivity();
135  auto items = connectivity->GetConnectivityAlgo()->ItemEntry( aTrack ).GetItems();
136 
137  if( items.empty() )
138  return false;
139 
140  auto citem = items.front();
141 
142  if( !citem->Valid() )
143  return false;
144 
145  auto anchors = citem->Anchors();
146 
147  VECTOR2I refpoint = aTstStart ? aTrack->GetStart() : aTrack->GetEnd();
148 
149  for( const auto& anchor : anchors )
150  {
151  if( anchor->Pos() != refpoint )
152  continue;
153 
154  // The right anchor point is found: if more than one other item
155  // (pad, via, track...) is connected, it is a node:
156  return anchor->ConnectedItemsCount() > 1;
157  }
158 
159  return false;
160 }
161 
162 
164 {
165  bool item_erased = false;
166  bool modified = false;
167 
168  do // Iterate when at least one track is deleted
169  {
170  item_erased = false;
171  // Ensure the connectivity is up to date, especially after removind a dangling segment
173 
174  // Keep a duplicate deque to all deleting in the primary
175  std::deque<TRACK*> temp_tracks( m_brd->Tracks() );
176 
177  for( TRACK* track : temp_tracks )
178  {
179  if( ( aVia && track->Type() != PCB_VIA_T ) || ( !aVia && track->Type() == PCB_VIA_T ) )
180  continue;
181 
182  // Test if a track (or a via) endpoint is not connected to another track or zone.
183  if( m_brd->GetConnectivity()->TestTrackEndpointDangling( track ) )
184  {
185  std::shared_ptr<CLEANUP_ITEM> item;
186 
187  if( track->Type() == PCB_VIA_T )
188  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DANGLING_VIA );
189  else
190  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DANGLING_TRACK );
191 
192  item->SetItems( track );
193  m_itemsList->push_back( item );
194 
195  if( !m_dryRun )
196  {
197  m_brd->Remove( track );
198  m_commit.Removed( track );
199 
200  /* keep iterating, because a track connected to the deleted track
201  * now perhaps is not connected and should be deleted */
202  item_erased = true;
203  modified = true;
204  }
205  // Fix me: In dry run we should disable the track to erase and retry with this disabled track
206  // However the connectivity algo does not handle disabled items.
207  }
208  }
209  } while( item_erased ); // A segment was erased: test for some new dangling segments
210 
211  return modified;
212 }
213 
214 
216 {
217  std::set<BOARD_ITEM*> toRemove;
218 
219  // Delete tracks that start and end on the same pad
220  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
221 
222  for( TRACK* track : m_brd->Tracks() )
223  {
224  if( track->Type() == PCB_VIA_T )
225  continue;
226 
227  // Mark track if connected to pads
228  for( D_PAD* pad : connectivity->GetConnectedPads( track ) )
229  {
230  if( pad->HitTest( track->GetStart() ) && pad->HitTest( track->GetEnd() ) )
231  {
232  SHAPE_POLY_SET poly;
233  track->TransformShapeWithClearanceToPolygon( poly, track->GetLayer(), 0,
234  ARC_HIGH_DEF, ERROR_INSIDE );
235 
236  poly.BooleanSubtract( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
237 
238  if( poly.IsEmpty() )
239  {
240  std::shared_ptr<CLEANUP_ITEM> item = std::make_shared<CLEANUP_ITEM>( CLEANUP_TRACK_IN_PAD );
241  item->SetItems( track );
242  m_itemsList->push_back( item );
243 
244  toRemove.insert( track );
245  }
246  }
247  }
248  }
249 
250  if( !m_dryRun )
251  removeItems( toRemove );
252 }
253 
254 
258 void TRACKS_CLEANER::cleanup( bool aDeleteDuplicateVias, bool aDeleteNullSegments,
259  bool aDeleteDuplicateSegments, bool aMergeSegments )
260 {
261  DRC_RTREE rtree;
262 
263  for( TRACK* track : m_brd->Tracks() )
264  {
265  track->ClearFlags( IS_DELETED | SKIP_STRUCT );
266  rtree.insert( track );
267  }
268 
269  std::set<BOARD_ITEM*> toRemove;
270 
271  for( TRACK* track : m_brd->Tracks() )
272  {
273  if( track->HasFlag( IS_DELETED ) || track->IsLocked() )
274  continue;
275 
276  if( aDeleteDuplicateVias && track->Type() == PCB_VIA_T )
277  {
278  VIA* via = static_cast<VIA*>( track );
279 
280  if( via->GetStart() != via->GetEnd() )
281  via->SetEnd( via->GetStart() );
282 
283  rtree.QueryColliding( via, via->GetLayer(), via->GetLayer(), nullptr,
284  [&]( BOARD_ITEM* aItem, int ) -> bool
285  {
286  if( aItem->Type() != PCB_VIA_T )
287  return true;
288 
289  VIA* other = static_cast<VIA*>( aItem );
290 
291  if( other->HasFlag( SKIP_STRUCT ) || other->HasFlag( IS_DELETED ) )
292  return true;
293 
294  if( via->GetPosition() == other->GetPosition()
295  && via->GetViaType() == other->GetViaType()
296  && via->GetLayerSet() == other->GetLayerSet() )
297  {
298  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_REDUNDANT_VIA );
299  item->SetItems( via );
300  m_itemsList->push_back( item );
301 
302  via->SetFlags( IS_DELETED );
303  toRemove.insert( via );
304  }
305 
306  return true;
307  } );
308 
309  // To delete through Via on THT pads at same location
310  // Examine the list of connected pads: if a through pad is found, the via is redundant
311  for( D_PAD* pad : m_brd->GetConnectivity()->GetConnectedPads( via ) )
312  {
313  const LSET all_cu = LSET::AllCuMask();
314 
315  if( ( pad->GetLayerSet() & all_cu ) == all_cu )
316  {
317  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_REDUNDANT_VIA );
318  item->SetItems( via, pad );
319  m_itemsList->push_back( item );
320 
321  via->SetFlags( IS_DELETED );
322  toRemove.insert( via );
323  break;
324  }
325  }
326 
327  via->SetFlags( SKIP_STRUCT );
328  }
329 
330  if( aDeleteNullSegments && track->Type() != PCB_VIA_T )
331  {
332  if( track->IsNull() )
333  {
334  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_ZERO_LENGTH_TRACK );
335  item->SetItems( track );
336  m_itemsList->push_back( item );
337 
338  track->SetFlags( IS_DELETED );
339  toRemove.insert( track );
340  }
341  }
342 
343  if( aDeleteDuplicateSegments && track->Type() == PCB_TRACE_T )
344  {
345  rtree.QueryColliding( track, track->GetLayer(), track->GetLayer(), nullptr,
346  [&]( BOARD_ITEM* aItem, int ) -> bool
347  {
348  if( aItem->Type() != PCB_TRACE_T )
349  return true;
350 
351  TRACK* other = static_cast<TRACK*>( aItem );
352 
353  if( other->HasFlag( SKIP_STRUCT )|| other->HasFlag( IS_DELETED ) )
354  return true;
355 
356  if( track->IsPointOnEnds( other->GetStart() )
357  && track->IsPointOnEnds( other->GetEnd() )
358  && track->GetWidth() == other->GetWidth()
359  && track->GetLayer() == other->GetLayer() )
360  {
361  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DUPLICATE_TRACK );
362  item->SetItems( track );
363  m_itemsList->push_back( item );
364 
365  track->SetFlags( IS_DELETED );
366  toRemove.insert( track );
367  }
368 
369  return true;
370  } );
371 
372  track->SetFlags( SKIP_STRUCT );
373  }
374  }
375 
376  if( !m_dryRun )
377  removeItems( toRemove );
378 
379  if( aMergeSegments )
380  {
381  bool merged;
382 
383  do
384  {
385  merged = false;
387 
388  // Keep a duplicate deque to all deleting in the primary
389  std::deque<TRACK*> temp_segments( m_brd->Tracks() );
390 
391  // merge collinear segments:
392  for( TRACK* segment : temp_segments )
393  {
394  if( segment->Type() != PCB_TRACE_T ) // one can merge only track collinear segments, not vias.
395  continue;
396 
397  if( segment->HasFlag( IS_DELETED ) ) // already taken in account
398  continue;
399 
400  auto connectivity = m_brd->GetConnectivity();
401 
402  auto& entry = connectivity->GetConnectivityAlgo()->ItemEntry( segment );
403 
404  for( CN_ITEM* citem : entry.GetItems() )
405  {
406  for( CN_ITEM* connected : citem->ConnectedItems() )
407  {
408  if( !connected->Valid() )
409  continue;
410 
411  BOARD_CONNECTED_ITEM* candidateItem = connected->Parent();
412 
413  if( candidateItem->Type() == PCB_TRACE_T && !candidateItem->HasFlag( IS_DELETED ) )
414  {
415  TRACK* candidateSegment = static_cast<TRACK*>( candidateItem );
416 
417  // Do not merge segments having different widths: it is a frequent case
418  // to draw a track between 2 pads:
419  if( candidateSegment->GetWidth() != segment->GetWidth() )
420  continue;
421 
422  if( segment->ApproxCollinear( *candidateSegment ) )
423  merged = mergeCollinearSegments( segment, candidateSegment );
424  }
425  }
426  }
427  }
428  } while( merged );
429  }
430 
431  for( TRACK* track : m_brd->Tracks() )
432  track->ClearFlags( IS_DELETED | SKIP_STRUCT );
433 }
434 
435 
437 {
438  if( aSeg1->IsLocked() || aSeg2->IsLocked() )
439  return false;
440 
441  auto connectivity = m_brd->GetConnectivity();
442 
443  // Verify the removed point after merging is not a node.
444  // If it is a node (i.e. if more than one other item is connected, the segments cannot be merged
445  TRACK dummy_seg( *aSeg1 );
446 
447  // Calculate the new ends of the segment to merge, and store them to dummy_seg:
448  int min_x = std::min( aSeg1->GetStart().x,
449  std::min( aSeg1->GetEnd().x, std::min( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
450  int min_y = std::min( aSeg1->GetStart().y,
451  std::min( aSeg1->GetEnd().y, std::min( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
452  int max_x = std::max( aSeg1->GetStart().x,
453  std::max( aSeg1->GetEnd().x, std::max( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
454  int max_y = std::max( aSeg1->GetStart().y,
455  std::max( aSeg1->GetEnd().y, std::max( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
456 
457  if( ( aSeg1->GetStart().x > aSeg1->GetEnd().x )
458  == ( aSeg1->GetStart().y > aSeg1->GetEnd().y ) )
459  {
460  dummy_seg.SetStart( wxPoint( min_x, min_y ) );
461  dummy_seg.SetEnd( wxPoint( max_x, max_y ) );
462  }
463  else
464  {
465  dummy_seg.SetStart( wxPoint( min_x, max_y ) );
466  dummy_seg.SetEnd( wxPoint( max_x, min_y ) );
467  }
468 
469  // Now find the removed end(s) and stop merging if it is a node:
470  if( aSeg1->GetStart() != dummy_seg.GetStart() && aSeg1->GetStart() != dummy_seg.GetEnd() )
471  {
472  if( testTrackEndpointIsNode( aSeg1, true ) )
473  return false;
474  }
475 
476  if( aSeg1->GetEnd() != dummy_seg.GetStart() && aSeg1->GetEnd() != dummy_seg.GetEnd() )
477  {
478  if( testTrackEndpointIsNode( aSeg1, false ) )
479  return false;
480  }
481 
482  std::shared_ptr<CLEANUP_ITEM> item = std::make_shared<CLEANUP_ITEM>( CLEANUP_MERGE_TRACKS );
483  item->SetItems( aSeg1, aSeg2 );
484  m_itemsList->push_back( item );
485 
486  aSeg2->SetFlags( IS_DELETED );
487 
488  if( !m_dryRun )
489  {
490  m_commit.Modify( aSeg1 );
491  *aSeg1 = dummy_seg;
492 
493  connectivity->Update( aSeg1 );
494 
495  // Clear the status flags here after update.
496  for( auto pad : connectivity->GetConnectedPads( aSeg1 ) )
497  {
498  aSeg1->SetState( BEGIN_ONPAD, pad->HitTest( aSeg1->GetStart() ) );
499  aSeg1->SetState( END_ONPAD, pad->HitTest( aSeg1->GetEnd() ) );
500  }
501 
502  // Merge succesful, seg2 has to go away
503  m_brd->Remove( aSeg2 );
504  m_commit.Removed( aSeg2 );
505  }
506 
507  return true;
508 }
509 
510 
511 void TRACKS_CLEANER::removeItems( std::set<BOARD_ITEM*>& aItems )
512 {
513  for( auto item : aItems )
514  {
515  m_brd->Remove( item );
516  m_commit.Removed( item );
517  }
518 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:136
const CONNECTED_ITEMS & ConnectedItems() const
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Return a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:749
COMMIT & Modify(EDA_ITEM *aItem)
Modifies a given item in the model.
Definition: commit.h:103
virtual LSET GetLayerSet() const override
Function GetLayerSet returns a std::bitset of all layers on which the item physically resides.
BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class,...
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:112
#define IS_DELETED
Definition: eda_item.h:109
const wxPoint & GetStart() const
Definition: class_track.h:116
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: eda_item.h:125
TRACKS_CLEANER(BOARD *aPcb, BOARD_COMMIT &aCommit)
void removeShortingTrackSegments()
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.
LSET is a set of PCB_LAYER_IDs.
void cleanup(bool aDeleteDuplicateVias, bool aDeleteNullSegments, bool aDeleteDuplicateSegments, bool aMergeSegments)
Geometry-based cleanup: duplicate items, null items, colinear items.
void SetFlags(STATUS_FLAGS aMask)
Definition: eda_item.h:221
SHAPE_POLY_SET.
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: class_board.h:381
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 CleanupBoard(bool aDryRun, std::vector< std::shared_ptr< CLEANUP_ITEM > > *aItemsList, bool aCleanVias, bool aRemoveMisConnected, bool aMergeSegments, bool aDeleteUnconnected, bool aDeleteTracksinPad, bool aDeleteDanglingVias)
the cleanup function.
int QueryColliding(BOARD_ITEM *aRefItem, PCB_LAYER_ID aRefLayer, PCB_LAYER_ID aTargetLayer, std::function< bool(BOARD_ITEM *)> aFilter=nullptr, std::function< bool(BOARD_ITEM *, int)> aVisitor=nullptr, int aClearance=0) const
Definition: drc_rtree.h:274
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: eda_item.h:124
void SetState(int type, int state)
Definition: eda_item.h:210
int GetWidth() const
Definition: class_track.h:110
void insert(BOARD_ITEM *aItem)
Function Insert() Inserts an item into the tree.
Definition: drc_rtree.h:84
std::vector< std::shared_ptr< CLEANUP_ITEM > > * m_itemsList
Information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:186
VIATYPE GetViaType() const
Definition: class_track.h:384
const wxPoint & GetEnd() const
Definition: class_track.h:113
void SetStart(const wxPoint &aStart)
Definition: class_track.h:115
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
#define SKIP_STRUCT
flag indicating that the structure should be ignored
Definition: eda_item.h:117
bool HasFlag(STATUS_FLAGS aFlag)
Definition: eda_item.h:224
DRC_RTREE - Implements an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:44
wxPoint GetPosition() const override
Definition: class_track.h:423
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:281
KICAD_T Type() const
Function Type()
Definition: eda_item.h:182
bool testTrackEndpointIsNode(TRACK *aTrack, bool aTstStart)