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-2019 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 <pcb_edit_frame.h>
28 #include <pcbnew.h>
29 #include <class_board.h>
30 #include <class_track.h>
32 #include <reporter.h>
33 #include <board_commit.h>
34 #include <drc/drc_item.h>
37 #include <tool/tool_manager.h>
38 #include <tools/pcb_actions.h>
39 #include <tools/global_edit_tool.h>
40 #include <tracks_cleaner.h>
41 
42 
43 /* Install the cleanup dialog frame to know what should be cleaned
44 */
46 {
47  PCB_EDIT_FRAME* editFrame = getEditFrame<PCB_EDIT_FRAME>();
48  DIALOG_CLEANUP_TRACKS_AND_VIAS dlg( editFrame );
49 
50  dlg.ShowModal();
51  return 0;
52 }
53 
54 
56  : m_units( aUnits ),
57  m_brd( aPcb ),
58  m_commit( aCommit ),
59  m_dryRun( true ),
60  m_itemsList( nullptr )
61 {
62 }
63 
64 
65 /* Main cleaning function.
66  * Delete
67  * - Redundant points on tracks (merge aligned segments)
68  * - vias on pad
69  * - null length segments
70  */
71 bool TRACKS_CLEANER::CleanupBoard( bool aDryRun, std::vector<DRC_ITEM*>* aItemsList,
72  bool aRemoveMisConnected, bool aCleanVias, bool aMergeSegments,
73  bool aDeleteUnconnected, bool aDeleteTracksinPad )
74 {
75  m_dryRun = aDryRun;
76  m_itemsList = aItemsList;
77  bool modified = false;
78 
79  // Clear the flag used to mark some segments as deleted, in dry run:
80  for( auto segment : m_brd->Tracks() )
81  segment->ClearFlags( IS_DELETED );
82 
83  // delete redundant vias
84  if( aCleanVias )
85  modified |= cleanupVias();
86 
87  // Remove null segments and intermediate points on aligned segments
88  // If not asked, remove null segments only if remove misconnected is asked
89  if( aMergeSegments )
90  modified |= cleanupSegments();
91  else if( aRemoveMisConnected )
92  modified |= deleteNullSegments( m_brd->Tracks() );
93 
94  if( aRemoveMisConnected )
95  modified |= removeBadTrackSegments();
96 
97  if( aDeleteTracksinPad )
98  modified |= deleteTracksInPads();
99 
100  // Delete dangling tracks
101  if( aDeleteUnconnected )
102  {
103  if( deleteDanglingTracks() )
104  {
105  modified = true;
106 
107  // Removed tracks can leave aligned segments
108  // (when a T was formed by tracks and the "vertical" segment is removed)
109  if( aMergeSegments )
110  cleanupSegments();
111  }
112  }
113 
114  // Clear the flag used to mark some segments:
115  for( auto segment : m_brd->Tracks() )
116  segment->ClearFlags( IS_DELETED );
117 
118  return modified;
119 }
120 
121 
123 {
124  auto connectivity = m_brd->GetConnectivity();
125 
126  std::set<BOARD_ITEM *> toRemove;
127 
128  for( auto segment : m_brd->Tracks() )
129  {
130  segment->SetState( FLAG0, false );
131 
132  for( auto testedPad : connectivity->GetConnectedPads( segment ) )
133  {
134  if( segment->GetNetCode() != testedPad->GetNetCode() )
135  {
136  DRC_ITEM* item = new DRC_ITEM();
137  item->SetData( m_units, DRCE_SHORT, segment, segment->GetPosition() );
138  m_itemsList->push_back( item );
139 
140  toRemove.insert( segment );
141  }
142  }
143 
144  for( auto testedTrack : connectivity->GetConnectedTracks( segment ) )
145  {
146  if( segment->GetNetCode() != testedTrack->GetNetCode() && !testedTrack->GetState( FLAG0 ) )
147  {
148  DRC_ITEM* item = new DRC_ITEM();
149  item->SetData( m_units, DRCE_SHORT, segment, segment->GetPosition() );
150  m_itemsList->push_back( item );
151 
152  toRemove.insert( segment );
153  }
154  }
155  }
156 
157  return removeItems( toRemove );
158 }
159 
160 
162 {
163  std::set<BOARD_ITEM*> toRemove;
164  std::vector<VIA*> vias;
165 
166  for( auto track : m_brd->Tracks() )
167  {
168  if( auto via = dyn_cast<VIA*>( track ) )
169  vias.push_back( via );
170  }
171 
172  for( auto via1_it = vias.begin(); via1_it != vias.end(); via1_it++ )
173  {
174  auto via1 = *via1_it;
175 
176  if( via1->IsLocked() )
177  continue;
178 
179  if( via1->GetStart() != via1->GetEnd() )
180  via1->SetEnd( via1->GetStart() );
181 
182  // To delete through Via on THT pads at same location
183  // Examine the list of connected pads:
184  // if a through pad is found, the via can be removed
185 
186  const auto pads = m_brd->GetConnectivity()->GetConnectedPads( via1 );
187  for( const auto pad : pads )
188  {
189  const LSET all_cu = LSET::AllCuMask();
190 
191  if( ( pad->GetLayerSet() & all_cu ) == all_cu )
192  {
193  DRC_ITEM* item = new DRC_ITEM();
194  item->SetData( m_units, DRCE_REDUNDANT_VIA, via1, via1->GetPosition(), pad,
195  pad->GetPosition() );
196  m_itemsList->push_back( item );
197 
198  // redundant: delete the via
199  toRemove.insert( via1 );
200  break;
201  }
202  }
203 
204  for( auto via2_it = via1_it + 1; via2_it != vias.end(); via2_it++ )
205  {
206  auto via2 = *via2_it;
207 
208  if( via1->GetPosition() != via2->GetPosition() || via2->IsLocked() )
209  continue;
210 
211  if( via1->GetViaType() == via2->GetViaType() )
212  {
213  DRC_ITEM* item = new DRC_ITEM();
214  item->SetData( m_units, DRCE_REDUNDANT_VIA, via1, via1->GetPosition(), via2,
215  via2->GetPosition() );
216  m_itemsList->push_back( item );
217 
218  toRemove.insert( via2 );
219  break;
220  }
221  }
222  }
223 
224 
225  return removeItems( toRemove );
226 }
227 
228 
230 {
231  auto connectivity = m_brd->GetConnectivity();
232  auto items = connectivity->GetConnectivityAlgo()->ItemEntry( aTrack ).GetItems();
233 
234  // Not in the connectivity system. This is a bug!
235  if( items.empty() )
236  {
237  wxASSERT( !items.empty() );
238  return false;
239  }
240 
241  auto citem = items.front();
242 
243  if( !citem->Valid() )
244  return false;
245 
246  auto anchors = citem->Anchors();
247 
248  for( const auto& anchor : anchors )
249  {
250  if( anchor->IsDangling() )
251  return true;
252  }
253 
254  return false;
255 }
256 
257 
258 bool TRACKS_CLEANER::testTrackEndpointIsNode( TRACK* aTrack, bool aTstStart )
259 {
260  // A node is a point where more than 2 items are connected.
261 
262  auto connectivity = m_brd->GetConnectivity();
263  auto items = connectivity->GetConnectivityAlgo()->ItemEntry( aTrack ).GetItems();
264 
265  if( items.empty() )
266  return false;
267 
268  auto citem = items.front();
269 
270  if( !citem->Valid() )
271  return false;
272 
273  auto anchors = citem->Anchors();
274 
275  VECTOR2I refpoint = aTstStart ? aTrack->GetStart() : aTrack->GetEnd();
276 
277  for( const auto& anchor : anchors )
278  {
279  if( anchor->Pos() != refpoint )
280  continue;
281 
282  // The right anchor point is found: if more than one other item
283  // (pad, via, track...) is connected, it is a node:
284  return anchor->ConnectedItemsCount() > 1;
285  }
286 
287  return false;
288 }
289 
290 
292 {
293  bool item_erased = false;
294  bool modified = false;
295 
296  do // Iterate when at least one track is deleted
297  {
298  item_erased = false;
299  // Ensure the connectivity is up to date, especially after removind a dangling segment
301 
302  for( TRACK* track : m_brd->Tracks() )
303  {
304  bool flag_erase = false; // Start without a good reason to erase it
305 
306  // Tst if a track (or a via) endpoint is not connected to another track or to a zone.
307  if( testTrackEndpointDangling( track ) )
308  flag_erase = true;
309 
310  if( flag_erase )
311  {
312  int code = track->IsTrack() ? DRCE_DANGLING_TRACK : DRCE_DANGLING_VIA;
313  DRC_ITEM* item = new DRC_ITEM();
314  item->SetData( m_units, code, track, track->GetPosition() );
315  m_itemsList->push_back( item );
316 
317  if( !m_dryRun )
318  {
319  m_brd->Remove( track );
320  m_commit.Removed( track );
321 
322  /* keep iterating, because a track connected to the deleted track
323  * now perhaps is not connected and should be deleted */
324  item_erased = true;
325  modified = true;
326  }
327  // Fix me: In dry run we should disable the track to erase and retry with this disabled track
328  // However the connectivity algo does not handle disabled items.
329  }
330  }
331  } while( item_erased ); // A segment was erased: test for some new dangling segments
332 
333  return modified;
334 }
335 
336 
337 // Delete null length track segments
338 bool TRACKS_CLEANER::deleteNullSegments( TRACKS& aTracks )
339 {
340  std::set<BOARD_ITEM *> toRemove;
341 
342  for( auto segment : aTracks )
343  {
344  if( segment->IsNull() && segment->Type() == PCB_TRACE_T && !segment->IsLocked() )
345  {
346  DRC_ITEM* item = new DRC_ITEM();
347  item->SetData( m_units, DRCE_ZERO_LENGTH_TRACK, segment, segment->GetPosition() );
348  m_itemsList->push_back( item );
349 
350  toRemove.insert( segment );
351  }
352  }
353 
354  return removeItems( toRemove );
355 }
356 
357 
359 {
360  std::set<BOARD_ITEM*> toRemove;
361 
362  // Delete tracks that start and end on the same pad
363  auto connectivity = m_brd->GetConnectivity();
364 
365  for( auto track : m_brd->Tracks() )
366  {
367  // Mark track if connected to pads
368  for( auto pad : connectivity->GetConnectedPads( track ) )
369  {
370  if( pad->HitTest( track->GetStart() ) && pad->HitTest( track->GetEnd() ) )
371  {
372  DRC_ITEM* item = new DRC_ITEM();
373  item->SetData( m_units, DRCE_TRACK_IN_PAD, track, track->GetPosition() );
374  m_itemsList->push_back( item );
375 
376  toRemove.insert( track );
377  }
378  }
379  }
380 
381  return removeItems( toRemove );
382 }
383 
384 
385 // Delete null length segments, and intermediate points ..
387 {
388  bool modified = false;
389 
390  // Easy things first
391  modified |= deleteNullSegments( m_brd->Tracks() );
392 
393  std::set<BOARD_ITEM*> toRemove;
394 
395  // Remove duplicate segments (2 superimposed identical segments):
396  for( auto it = m_brd->Tracks().begin(); it != m_brd->Tracks().end(); it++ )
397  {
398  auto track1 = *it;
399 
400  if( track1->Type() != PCB_TRACE_T || track1->HasFlag( IS_DELETED ) || track1->IsLocked() )
401  continue;
402 
403  for( auto it2 = it + 1; it2 != m_brd->Tracks().end(); it2++ )
404  {
405  auto track2 = *it2;
406 
407  if( track2->HasFlag( IS_DELETED ) )
408  continue;
409 
410  if( track1->IsPointOnEnds( track2->GetStart() )
411  && track1->IsPointOnEnds( track2->GetEnd() )
412  && track1->GetWidth() == track2->GetWidth()
413  && track1->GetLayer() == track2->GetLayer() )
414  {
415  DRC_ITEM* item = new DRC_ITEM();
416  item->SetData( m_units, DRCE_DUPLICATE_TRACK, track2, track2->GetPosition() );
417  m_itemsList->push_back( item );
418 
419  track2->SetFlags( IS_DELETED );
420  toRemove.insert( track2 );
421  }
422  }
423  }
424 
425  modified |= removeItems( toRemove );
426 
427  // merge collinear segments:
428  for( TRACK* segment : m_brd->Tracks() )
429  {
430  if( segment->Type() != PCB_TRACE_T ) // one can merge only track collinear segments, not vias.
431  continue;
432 
433  if( segment->HasFlag( IS_DELETED ) ) // already taken in account
434  continue;
435 
436  auto connectivity = m_brd->GetConnectivity();
437 
438  auto& entry = connectivity->GetConnectivityAlgo()->ItemEntry( segment );
439 
440  for( auto citem : entry.GetItems() )
441  {
442  for( auto connected : citem->ConnectedItems() )
443  {
444  if( !connected->Valid() )
445  continue;
446 
447  BOARD_CONNECTED_ITEM* candidateItem = connected->Parent();
448 
449  if( candidateItem->Type() == PCB_TRACE_T && !candidateItem->HasFlag( IS_DELETED ) )
450  {
451  TRACK* candidateSegment = static_cast<TRACK*>( candidateItem );
452 
453  // Do not merge segments having different widths: it is a frequent case
454  // to draw a track between 2 pads:
455  if( candidateSegment->GetWidth() != segment->GetWidth() )
456  continue;
457 
458  if( segment->ApproxCollinear( *candidateSegment ) )
459  modified |= mergeCollinearSegments( segment, candidateSegment );
460  }
461  }
462  }
463  }
464 
465  return modified;
466 }
467 
468 
470 {
471  if( aSeg1->IsLocked() || aSeg2->IsLocked() )
472  return false;
473 
474  auto connectivity = m_brd->GetConnectivity();
475 
476  // Verify the removed point after merging is not a node.
477  // If it is a node (i.e. if more than one other item is connected, the segments cannot be merged
478  TRACK dummy_seg( *aSeg1 );
479 
480  // Calculate the new ends of the segment to merge, and store them to dummy_seg:
481  int min_x = std::min( aSeg1->GetStart().x,
482  std::min( aSeg1->GetEnd().x, std::min( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
483  int min_y = std::min( aSeg1->GetStart().y,
484  std::min( aSeg1->GetEnd().y, std::min( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
485  int max_x = std::max( aSeg1->GetStart().x,
486  std::max( aSeg1->GetEnd().x, std::max( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
487  int max_y = std::max( aSeg1->GetStart().y,
488  std::max( aSeg1->GetEnd().y, std::max( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
489 
490  if( ( aSeg1->GetStart().x > aSeg1->GetEnd().x )
491  == ( aSeg1->GetStart().y > aSeg1->GetEnd().y ) )
492  {
493  dummy_seg.SetStart( wxPoint( min_x, min_y ) );
494  dummy_seg.SetEnd( wxPoint( max_x, max_y ) );
495  }
496  else
497  {
498  dummy_seg.SetStart( wxPoint( min_x, max_y ) );
499  dummy_seg.SetEnd( wxPoint( max_x, min_y ) );
500  }
501 
502  // Now find the removed end(s) and stop merging if it is a node:
503  if( aSeg1->GetStart() != dummy_seg.GetStart() && aSeg1->GetStart() != dummy_seg.GetEnd() )
504  {
505  if( testTrackEndpointIsNode( aSeg1, true ) )
506  return false;
507  }
508 
509  if( aSeg1->GetEnd() != dummy_seg.GetStart() && aSeg1->GetEnd() != dummy_seg.GetEnd() )
510  {
511  if( testTrackEndpointIsNode( aSeg1, false ) )
512  return false;
513  }
514 
515  DRC_ITEM* item = new DRC_ITEM();
516  item->SetData( m_units, DRCE_MERGE_TRACKS, aSeg1, aSeg1->GetPosition(), aSeg2,
517  aSeg2->GetPosition() );
518  m_itemsList->push_back( item );
519 
520  aSeg2->SetFlags( IS_DELETED );
521 
522  if( !m_dryRun )
523  {
524  m_commit.Modify( aSeg1 );
525  *aSeg1 = dummy_seg;
526 
527  connectivity->Update( aSeg1 );
528 
529  // Clear the status flags here after update.
530  for( auto pad : connectivity->GetConnectedPads( aSeg1 ) )
531  {
532  aSeg1->SetState( BEGIN_ONPAD, pad->HitTest( aSeg1->GetStart() ) );
533  aSeg1->SetState( END_ONPAD, pad->HitTest( aSeg1->GetEnd() ) );
534  }
535 
536  // Merge succesful, seg2 has to go away
537  m_brd->Remove( aSeg2 );
538  m_commit.Removed( aSeg2 );
539  }
540 
541  return true;
542 }
543 
544 
545 bool TRACKS_CLEANER::removeItems( std::set<BOARD_ITEM*>& aItems )
546 {
547  if( m_dryRun )
548  return false;
549 
550  for( auto item : aItems )
551  {
552  m_brd->Remove( item );
553  m_commit.Removed( item );
554  }
555 
556  return !aItems.empty();
557 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:126
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:686
Definition: drc.h:94
EDA_UNITS
Definition: common.h:184
COMMIT & Modify(EDA_ITEM *aItem)
Modifies a given item in the model.
Definition: commit.h:103
bool CleanupBoard(bool aDryRun, std::vector< DRC_ITEM * > *aItemsList, bool aCleanVias, bool aRemoveMisConnected, bool aMergeSegments, bool aDeleteUnconnected, bool aDeleteTracksinPad)
the cleanup function.
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: base_struct.h:139
void SetData(EDA_UNITS aUnits, int aErrorCode, EDA_ITEM *aMainItem, EDA_ITEM *bAuxItem=nullptr)
Function SetData initialize all data in item.
Definition: rc_item.h:128
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:107
const wxPoint & GetStart() const
Definition: class_track.h:111
bool deleteDanglingTracks()
Removes dangling tracks.
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: base_struct.h:138
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
bool deleteNullSegments(TRACKS &aTracks)
Delete null length track segments.
Definitions for tracks, vias and zones.
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
LSET is a set of PCB_LAYER_IDs.
void SetFlags(STATUS_FLAGS aMask)
Definition: base_struct.h:257
const wxPoint GetPosition() const override
Definition: class_track.h:102
#define IS_DELETED
Definition: base_struct.h:123
TOOL_EVENT.
Definition: tool_event.h:171
bool removeBadTrackSegments()
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Function GetConnectivity() returns list of missing connections between components/tracks.
Definition: class_board.h:306
bool mergeCollinearSegments(TRACK *aSeg1, TRACK *aSeg2)
helper function merge aTrackRef and aCandidate, when possible, i.e.
EDA_UNITS m_units
TRACKS_CLEANER(EDA_UNITS aUnits, BOARD *aPcb, BOARD_COMMIT &aCommit)
void BuildConnectivity()
Builds or rebuilds the board connectivity database for the board, especially the list of connected it...
#define FLAG0
Pcbnew: flag used in local computations.
Definition: base_struct.h:137
std::vector< DRC_ITEM * > * m_itemsList
void SetState(int type, int state)
Definition: base_struct.h:246
int GetWidth() const
Definition: class_track.h:105
BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:163
bool deleteTracksInPads()
Removes tracks that are fully inside pads.
PCB_EDIT_FRAME is the main frame for Pcbnew.
const wxPoint & GetEnd() const
Definition: class_track.h:108
int CleanupTracksAndVias(const TOOL_EVENT &aEvent)
void SetStart(const wxPoint &aStart)
Definition: class_track.h:110
bool testTrackEndpointDangling(TRACK *aTrack)
bool cleanupSegments()
Merge collinear segments and remove duplicated and null len segments.
bool HasFlag(STATUS_FLAGS aFlag)
Definition: base_struct.h:260
void Remove(BOARD_ITEM *aBoardItem) override
Removes an item from the container.
TRACKS & Tracks()
Definition: class_board.h:220
bool removeItems(std::set< BOARD_ITEM * > &aItems)
KICAD_T Type() const
Function Type()
Definition: base_struct.h:212
bool testTrackEndpointIsNode(TRACK *aTrack, bool aTstStart)
bool cleanupVias()
Removes redundant vias like vias at same location or on pad through.