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( PCB_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( PCB_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( PCB_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 removing a dangling segment
176 
177  // Keep a duplicate deque to all deleting in the primary
178  std::deque<PCB_TRACK*> temp_tracks( m_brd->Tracks() );
179 
180  for( PCB_TRACK* track : temp_tracks )
181  {
182  if( track->IsLocked() || ( track->GetFlags() & IS_DELETED ) > 0 )
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  track->SetFlags( IS_DELETED );
204 
205  // keep iterating, because a track connected to the deleted track
206  // now perhaps is not connected and should be deleted
207  item_erased = true;
208 
209  if( !m_dryRun )
210  {
211  m_brd->Remove( track );
212  m_commit.Removed( track );
213  modified = true;
214  }
215  }
216  }
217  } while( item_erased ); // A segment was erased: test for some new dangling segments
218 
219  return modified;
220 }
221 
222 
224 {
225  std::set<BOARD_ITEM*> toRemove;
226 
227  // Delete tracks that start and end on the same pad
228  std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_brd->GetConnectivity();
229 
230  for( PCB_TRACK* track : m_brd->Tracks() )
231  {
232  if( track->IsLocked() )
233  continue;
234 
235  if( track->Type() == PCB_VIA_T )
236  continue;
237 
238  // Mark track if connected to pads
239  for( PAD* pad : connectivity->GetConnectedPads( track ) )
240  {
241  if( pad->HitTest( track->GetStart() ) && pad->HitTest( track->GetEnd() ) )
242  {
243  SHAPE_POLY_SET poly;
244  track->TransformShapeWithClearanceToPolygon( poly, track->GetLayer(), 0,
245  ARC_HIGH_DEF, ERROR_INSIDE );
246 
247  poly.BooleanSubtract( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
248 
249  if( poly.IsEmpty() )
250  {
251  auto item = std::make_shared<CLEANUP_ITEM>( CLEANUP_TRACK_IN_PAD );
252  item->SetItems( track );
253  m_itemsList->push_back( item );
254 
255  toRemove.insert( track );
256  track->SetFlags( IS_DELETED );
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( PCB_TRACK* track : m_brd->Tracks() )
276  {
277  track->ClearFlags( IS_DELETED | SKIP_STRUCT );
278  rtree.Insert( track, track->GetLayer() );
279  }
280 
281  std::set<BOARD_ITEM*> toRemove;
282 
283  for( PCB_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  PCB_VIA* via = static_cast<PCB_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  PCB_VIA* other = static_cast<PCB_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  PCB_TRACK* other = static_cast<PCB_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<PCB_TRACK*> temp_segments( m_brd->Tracks() );
406 
407  // merge collinear segments:
408  for( PCB_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  PCB_TRACK* candidateSegment = static_cast<PCB_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( PCB_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  PCB_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 successful, 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
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
wxPoint GetPosition() const override
Definition: pcb_track.h:392
const wxPoint & GetEnd() const
Definition: pcb_track.h:105
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:80
void SetEnd(const wxPoint &aEnd)
Definition: pcb_track.h:104
VIATYPE GetViaType() const
Definition: pcb_track.h:354
bool IsEmpty() const
bool HasFlag(EDA_ITEM_FLAGS aFlag) const
Definition: eda_item.h:156
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:153
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition: pcb_track.cpp:402
TRACKS_CLEANER(BOARD *aPcb, BOARD_COMMIT &aCommit)
int GetWidth() const
Definition: pcb_track.h:102
void removeShortingTrackSegments()
virtual bool IsLocked() const
Definition: board_item.cpp:78
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
class PCB_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(EDA_ITEM_FLAGS type, bool state)
Definition: eda_item.h:142
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:502
void cleanup(bool aDeleteDuplicateVias, bool aDeleteNullSegments, bool aDeleteDuplicateSegments, bool aMergeSegments)
Geometry-based cleanup: duplicate items, null items, colinear items.
#define IS_DELETED
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:344
void removeItems(std::set< BOARD_ITEM * > &aItems)
void SetStart(const wxPoint &aStart)
Definition: pcb_track.h:107
void BuildConnectivity()
Build or rebuild the board connectivity database for the board, especially the list of connected item...
Definition: board.cpp:136
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.
#define SKIP_STRUCT
flag indicating that the structure should be ignored
std::vector< std::shared_ptr< CLEANUP_ITEM > > * m_itemsList
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:190
bool mergeCollinearSegments(PCB_TRACK *aSeg1, PCB_TRACK *aSeg2)
helper function merge aTrackRef and aCandidate, when possible, i.e.
bool testTrackEndpointIsNode(PCB_TRACK *aTrack, bool aTstStart)
void Remove(BOARD_ITEM *aBoardItem, REMOVE_MODE aMode=REMOVE_MODE::NORMAL) override
Removes an item from the container.
Definition: board.cpp:709
void Insert(BOARD_ITEM *aItem, PCB_LAYER_ID aLayer, int aWorstClearance=0)
Insert an item into the tree on a particular layer with an optional worst clearance.
Definition: drc_rtree.h:86
class PCB_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.
Definition: pad.h:57
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:44
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:171
TRACKS & Tracks()
Definition: board.h:230
const wxPoint & GetStart() const
Definition: pcb_track.h:108
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113
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:165