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