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