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  has_deleted = deleteDanglingTracks( aDeleteUnconnected, aDeleteDanglingVias );
70 
71  if( has_deleted && aMergeSegments )
72  cleanup( false, false, false, true );
73 }
74 
75 
77 {
78  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
79 
80  std::set<BOARD_ITEM *> toRemove;
81 
82  for( TRACK* segment : m_brd->Tracks() )
83  {
84  // Assume that the user knows what they are doing
85  if( segment->IsLocked() )
86  continue;
87 
88  for( 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 
163 bool TRACKS_CLEANER::deleteDanglingTracks( bool aTrack, bool aVia )
164 {
165  bool item_erased = false;
166  bool modified = false;
167 
168  if( !aTrack && !aVia )
169  return false;
170 
171  do // Iterate when at least one track is deleted
172  {
173  item_erased = false;
174  // Ensure the connectivity is up to date, especially after removind a dangling segment
176 
177  // Keep a duplicate deque to all deleting in the primary
178  std::deque<TRACK*> temp_tracks( m_brd->Tracks() );
179 
180  for( TRACK* track : temp_tracks )
181  {
182  if( track->IsLocked() )
183  continue;
184 
185  if( !aVia && track->Type() == PCB_VIA_T )
186  continue;
187 
188  if( !aTrack && ( track->Type() == PCB_TRACE_T || track->Type() == PCB_ARC_T ) )
189  continue;
190 
191  // Test if a track (or a via) endpoint is not connected to another track or zone.
192  if( m_brd->GetConnectivity()->TestTrackEndpointDangling( track ) )
193  {
194  std::shared_ptr<CLEANUP_ITEM> item;
195 
196  if( track->Type() == PCB_VIA_T )
197  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DANGLING_VIA );
198  else
199  item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DANGLING_TRACK );
200 
201  item->SetItems( track );
202  m_itemsList->push_back( item );
203 
204  if( !m_dryRun )
205  {
206  m_brd->Remove( track );
207  m_commit.Removed( track );
208 
209  /* keep iterating, because a track connected to the deleted track
210  * now perhaps is not connected and should be deleted */
211  item_erased = true;
212  modified = true;
213  }
214  // Fix me: In dry run we should disable the track to erase and retry with this disabled track
215  // However the connectivity algo does not handle disabled items.
216  }
217  }
218  } while( item_erased ); // A segment was erased: test for some new dangling segments
219 
220  return modified;
221 }
222 
223 
225 {
226  std::set<BOARD_ITEM*> toRemove;
227 
228  // Delete tracks that start and end on the same pad
229  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
230 
231  for( TRACK* track : m_brd->Tracks() )
232  {
233  if( track->IsLocked() )
234  continue;
235 
236  if( track->Type() == PCB_VIA_T )
237  continue;
238 
239  // Mark track if connected to pads
240  for( PAD* pad : connectivity->GetConnectedPads( track ) )
241  {
242  if( pad->HitTest( track->GetStart() ) && pad->HitTest( track->GetEnd() ) )
243  {
244  SHAPE_POLY_SET poly;
245  track->TransformShapeWithClearanceToPolygon( poly, track->GetLayer(), 0,
246  ARC_HIGH_DEF, ERROR_INSIDE );
247 
248  poly.BooleanSubtract( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
249 
250  if( poly.IsEmpty() )
251  {
252  std::shared_ptr<CLEANUP_ITEM> item = std::make_shared<CLEANUP_ITEM>( CLEANUP_TRACK_IN_PAD );
253  item->SetItems( track );
254  m_itemsList->push_back( item );
255 
256  toRemove.insert( track );
257  }
258  }
259  }
260  }
261 
262  if( !m_dryRun )
263  removeItems( toRemove );
264 }
265 
266 
270 void TRACKS_CLEANER::cleanup( bool aDeleteDuplicateVias, bool aDeleteNullSegments,
271  bool aDeleteDuplicateSegments, bool aMergeSegments )
272 {
273  DRC_RTREE rtree;
274 
275  for( TRACK* track : m_brd->Tracks() )
276  {
277  track->ClearFlags( IS_DELETED | SKIP_STRUCT );
278  rtree.Insert( track );
279  }
280 
281  std::set<BOARD_ITEM*> toRemove;
282 
283  for( TRACK* track : m_brd->Tracks() )
284  {
285  if( track->HasFlag( IS_DELETED ) || track->IsLocked() )
286  continue;
287 
288  if( aDeleteDuplicateVias && track->Type() == PCB_VIA_T )
289  {
290  VIA* via = static_cast<VIA*>( track );
291 
292  if( via->GetStart() != via->GetEnd() )
293  via->SetEnd( via->GetStart() );
294 
295  rtree.QueryColliding( via, via->GetLayer(), via->GetLayer(),
296  // Filter:
297  [&]( BOARD_ITEM* aItem ) -> bool
298  {
299  return aItem->Type() == PCB_VIA_T
300  && !aItem->HasFlag( SKIP_STRUCT )
301  && !aItem->HasFlag( IS_DELETED );
302  },
303  // Visitor:
304  [&]( BOARD_ITEM* aItem ) -> bool
305  {
306  VIA* other = static_cast<VIA*>( aItem );
307 
308  if( via->GetPosition() == other->GetPosition()
309  && via->GetViaType() == other->GetViaType()
310  && via->GetLayerSet() == other->GetLayerSet() )
311  {
312  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_REDUNDANT_VIA );
313  item->SetItems( via );
314  m_itemsList->push_back( item );
315 
316  via->SetFlags( IS_DELETED );
317  toRemove.insert( via );
318  }
319 
320  return true;
321  } );
322 
323  // To delete through Via on THT pads at same location
324  // Examine the list of connected pads: if a through pad is found, the via is redundant
325  for( PAD* pad : m_brd->GetConnectivity()->GetConnectedPads( via ) )
326  {
327  const LSET all_cu = LSET::AllCuMask();
328 
329  if( ( pad->GetLayerSet() & all_cu ) == all_cu )
330  {
331  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_REDUNDANT_VIA );
332  item->SetItems( via, pad );
333  m_itemsList->push_back( item );
334 
335  via->SetFlags( IS_DELETED );
336  toRemove.insert( via );
337  break;
338  }
339  }
340 
341  via->SetFlags( SKIP_STRUCT );
342  }
343 
344  if( aDeleteNullSegments && track->Type() != PCB_VIA_T )
345  {
346  if( track->IsNull() )
347  {
348  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_ZERO_LENGTH_TRACK );
349  item->SetItems( track );
350  m_itemsList->push_back( item );
351 
352  track->SetFlags( IS_DELETED );
353  toRemove.insert( track );
354  }
355  }
356 
357  if( aDeleteDuplicateSegments && track->Type() == PCB_TRACE_T )
358  {
359  rtree.QueryColliding( track, track->GetLayer(), track->GetLayer(),
360  // Filter:
361  [&]( BOARD_ITEM* aItem ) -> bool
362  {
363  return aItem->Type() == PCB_TRACE_T
364  && !aItem->HasFlag( SKIP_STRUCT )
365  && !aItem->HasFlag( IS_DELETED );
366  },
367  // Visitor:
368  [&]( BOARD_ITEM* aItem ) -> bool
369  {
370  TRACK* other = static_cast<TRACK*>( aItem );
371 
372  if( track->IsPointOnEnds( other->GetStart() )
373  && track->IsPointOnEnds( other->GetEnd() )
374  && track->GetWidth() == other->GetWidth()
375  && track->GetLayer() == other->GetLayer() )
376  {
377  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_DUPLICATE_TRACK );
378  item->SetItems( track );
379  m_itemsList->push_back( item );
380 
381  track->SetFlags( IS_DELETED );
382  toRemove.insert( track );
383  }
384 
385  return true;
386  } );
387 
388  track->SetFlags( SKIP_STRUCT );
389  }
390  }
391 
392  if( !m_dryRun )
393  removeItems( toRemove );
394 
395  if( aMergeSegments )
396  {
397  bool merged;
398 
399  do
400  {
401  merged = false;
403 
404  // Keep a duplicate deque to all deleting in the primary
405  std::deque<TRACK*> temp_segments( m_brd->Tracks() );
406 
407  // merge collinear segments:
408  for( TRACK* segment : temp_segments )
409  {
410  if( segment->Type() != PCB_TRACE_T ) // one can merge only track collinear segments, not vias.
411  continue;
412 
413  if( segment->HasFlag( IS_DELETED ) ) // already taken in account
414  continue;
415 
416  auto connectivity = m_brd->GetConnectivity();
417 
418  auto& entry = connectivity->GetConnectivityAlgo()->ItemEntry( segment );
419 
420  for( CN_ITEM* citem : entry.GetItems() )
421  {
422  for( CN_ITEM* connected : citem->ConnectedItems() )
423  {
424  if( !connected->Valid() )
425  continue;
426 
427  BOARD_CONNECTED_ITEM* candidateItem = connected->Parent();
428 
429  if( candidateItem->Type() == PCB_TRACE_T && !candidateItem->HasFlag( IS_DELETED ) )
430  {
431  TRACK* candidateSegment = static_cast<TRACK*>( candidateItem );
432 
433  // Do not merge segments having different widths: it is a frequent case
434  // to draw a track between 2 pads:
435  if( candidateSegment->GetWidth() != segment->GetWidth() )
436  continue;
437 
438  if( segment->ApproxCollinear( *candidateSegment ) )
439  merged = mergeCollinearSegments( segment, candidateSegment );
440  }
441  }
442  }
443  }
444  } while( merged );
445  }
446 
447  for( TRACK* track : m_brd->Tracks() )
448  track->ClearFlags( IS_DELETED | SKIP_STRUCT );
449 }
450 
451 
453 {
454  if( aSeg1->IsLocked() || aSeg2->IsLocked() )
455  return false;
456 
457  auto connectivity = m_brd->GetConnectivity();
458 
459  // Verify the removed point after merging is not a node.
460  // If it is a node (i.e. if more than one other item is connected, the segments cannot be merged
461  TRACK dummy_seg( *aSeg1 );
462 
463  // Calculate the new ends of the segment to merge, and store them to dummy_seg:
464  int min_x = std::min( aSeg1->GetStart().x,
465  std::min( aSeg1->GetEnd().x, std::min( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
466  int min_y = std::min( aSeg1->GetStart().y,
467  std::min( aSeg1->GetEnd().y, std::min( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
468  int max_x = std::max( aSeg1->GetStart().x,
469  std::max( aSeg1->GetEnd().x, std::max( aSeg2->GetStart().x, aSeg2->GetEnd().x ) ) );
470  int max_y = std::max( aSeg1->GetStart().y,
471  std::max( aSeg1->GetEnd().y, std::max( aSeg2->GetStart().y, aSeg2->GetEnd().y ) ) );
472 
473  if( ( aSeg1->GetStart().x > aSeg1->GetEnd().x )
474  == ( aSeg1->GetStart().y > aSeg1->GetEnd().y ) )
475  {
476  dummy_seg.SetStart( wxPoint( min_x, min_y ) );
477  dummy_seg.SetEnd( wxPoint( max_x, max_y ) );
478  }
479  else
480  {
481  dummy_seg.SetStart( wxPoint( min_x, max_y ) );
482  dummy_seg.SetEnd( wxPoint( max_x, min_y ) );
483  }
484 
485  // Now find the removed end(s) and stop merging if it is a node:
486  if( aSeg1->GetStart() != dummy_seg.GetStart() && aSeg1->GetStart() != dummy_seg.GetEnd() )
487  {
488  if( testTrackEndpointIsNode( aSeg1, true ) )
489  return false;
490  }
491 
492  if( aSeg1->GetEnd() != dummy_seg.GetStart() && aSeg1->GetEnd() != dummy_seg.GetEnd() )
493  {
494  if( testTrackEndpointIsNode( aSeg1, false ) )
495  return false;
496  }
497 
498  std::shared_ptr<CLEANUP_ITEM> item = std::make_shared<CLEANUP_ITEM>( CLEANUP_MERGE_TRACKS );
499  item->SetItems( aSeg1, aSeg2 );
500  m_itemsList->push_back( item );
501 
502  aSeg2->SetFlags( IS_DELETED );
503 
504  if( !m_dryRun )
505  {
506  m_commit.Modify( aSeg1 );
507  *aSeg1 = dummy_seg;
508 
509  connectivity->Update( aSeg1 );
510 
511  // Clear the status flags here after update.
512  for( auto pad : connectivity->GetConnectedPads( aSeg1 ) )
513  {
514  aSeg1->SetState( BEGIN_ONPAD, pad->HitTest( aSeg1->GetStart() ) );
515  aSeg1->SetState( END_ONPAD, pad->HitTest( aSeg1->GetEnd() ) );
516  }
517 
518  // Merge succesful, seg2 has to go away
519  m_brd->Remove( aSeg2 );
520  m_commit.Removed( aSeg2 );
521  }
522 
523  return true;
524 }
525 
526 
527 void TRACKS_CLEANER::removeItems( std::set<BOARD_ITEM*>& aItems )
528 {
529  for( auto item : aItems )
530  {
531  m_brd->Remove( item );
532  m_commit.Removed( item );
533  }
534 }
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:750
Definition: track.h:343
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition: track.cpp:376
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:82
void SetEnd(const wxPoint &aEnd)
Definition: track.h:112
#define IS_DELETED
Definition: eda_item.h:109
const wxPoint & GetStart() const
Definition: track.h:116
bool IsEmpty() const
class ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: eda_item.h:127
TRACKS_CLEANER(BOARD *aPcb, BOARD_COMMIT &aCommit)
void removeShortingTrackSegments()
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
void Insert(BOARD_ITEM *aItem, int aWorstClearance=0, int aLayer=UNDEFINED_LAYER)
Function Insert() Inserts an item into the tree.
Definition: drc_rtree.h:86
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
BOARD_COMMIT & m_commit
COMMIT & Removed(EDA_ITEM *aItem)
Modify a given item in the model.
Definition: commit.h:96
void SetState(int type, bool state)
Definition: eda_item.h:191
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:202
bool deleteDanglingTracks(bool aTrack, bool aVia)
Removes tracks or vias only connected on one end.
Represent a set of closed polygons.
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:414
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...
Definition: board.cpp:133
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.
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: eda_item.h:126
virtual bool IsLocked() const
Definition: board_item.h:249
int GetWidth() const
Definition: track.h:110
std::vector< std::shared_ptr< CLEANUP_ITEM > > * m_itemsList
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:190
VIATYPE GetViaType() const
Definition: track.h:373
void Remove(BOARD_ITEM *aBoardItem, REMOVE_MODE aMode=REMOVE_MODE::NORMAL) override
Removes an item from the container.
Definition: board.cpp:665
const wxPoint & GetEnd() const
Definition: track.h:113
void SetStart(const wxPoint &aStart)
Definition: track.h:115
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
#define SKIP_STRUCT
flag indicating that the structure should be ignored
Definition: eda_item.h:117
Definition: pad.h:60
DRC_RTREE - Implements an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:43
wxPoint GetPosition() const override
Definition: track.h:411
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:173
TRACKS & Tracks()
Definition: board.h:300
Definition: track.h:83
bool HasFlag(STATUS_FLAGS aFlag) const
Definition: eda_item.h:205
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:162
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 *)> aVisitor=nullptr, int aClearance=0) const
This is a fast test which essentially does bounding-box overlap given a worst-case clearance.
Definition: drc_rtree.h:190
bool testTrackEndpointIsNode(TRACK *aTrack, bool aTstStart)