KiCad PCB EDA Suite
pns_mouse_trail_tracer.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2020 CERN
5  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software: you can redistribute it and/or modify it
8  * under the terms of the GNU General Public License as published by the
9  * Free Software Foundation, either version 3 of the License, or (at your
10  * option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License along
18  * with this program. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 #include "pns_mouse_trail_tracer.h"
22 #include "pns_router.h"
23 #include "pns_debug_decorator.h"
24 
25 namespace PNS {
26 
28 {
29  m_tolerance = 0;
30  m_disableMouse = false;
31  Clear();
32 }
33 
34 
36 
37 
39 {
40  m_forced = false;
41  m_manuallyForced = false;
42  m_trail.Clear();
43 }
44 
45 
47 {
48  if( m_trail.SegmentCount() == 0 )
49  {
50  m_trail.Append( aP );
51  }
52  else
53  {
54  SEG s_new( m_trail.CPoint( -1 ), aP );
55 
56  for( int i = 0; i < m_trail.SegmentCount() - 1; i++ )
57  {
58  const SEG& s_trail = m_trail.CSegment( i );
59 
60  if( s_trail.Distance( s_new ) <= m_tolerance )
61  {
62  m_trail = m_trail.Slice( 0, i );
63  break;
64  }
65  }
66 
67  m_trail.Append( aP );
68  }
69 
70  m_trail.Simplify();
71 
73 }
74 
75 
77 {
78  // Tuning factor for how good the "fit" of the trail must be to the posture
79  const double areaRatioThreshold = 1.3;
80 
81  // Tuning factor to minimize flutter
82  const double areaRatioEpsilon = 0.25;
83 
84  // Minimum distance factor of the trail before the min area test is used to lock the solver
85  const double minAreaCutoffDistanceFactor = 6;
86 
87  // Adjusts how far away from p0 we get before whatever posture we solved is locked in
88  const int lockDistanceFactor = 25;
89 
90  // Adjusts how close to p0 we unlock the posture again if one was locked already
91  const int unlockDistanceFactor = 4;
92 
93  if( m_trail.PointCount() < 2 || m_manuallyForced )
94  {
95  // If mouse trail detection is enabled; using the last seg direction as a starting point
96  // will give the best results. Otherwise, just assume that we switch postures every
97  // segment.
100 
101  return m_direction;
102  }
103 
105  VECTOR2I p0 = m_trail.CPoint( 0 );
106  double refLength = SEG( p0, aP ).Length();
107  SHAPE_LINE_CHAIN straight( DIRECTION_45().BuildInitialTrace( p0, aP, false, false ) );
108 
109  straight.SetClosed( true );
110  straight.Append( m_trail.Reverse() );
111  straight.Simplify();
112  dbg->AddLine( straight, m_forced ? 3 : 2, 100000 );
113 
114  double areaS = std::abs( straight.Area() );
115 
116  SHAPE_LINE_CHAIN diag( DIRECTION_45().BuildInitialTrace( p0, aP, true, false ) );
117  diag.Append( m_trail.Reverse() );
118  diag.SetClosed( true );
119  diag.Simplify();
120  dbg->AddLine( diag, 1, 100000 );
121 
122  double areaDiag = std::abs( diag.Area() );
123  double ratio = areaS / ( areaDiag + 1.0 );
124 
125  // heuristic to detect that the user dragged back the cursor to the beginning of the trace
126  // in this case, we cancel any forced posture and restart the trail
127  if( m_forced && refLength < unlockDistanceFactor * m_tolerance )
128  {
129  wxLogTrace( "PNS", "Posture: Unlocked and reset" );
130  m_forced = false;
131  VECTOR2I start = p0;
132  m_trail.Clear();
133  m_trail.Append( start );
134  }
135 
136  bool areaOk = false;
137 
138  // Check the actual trail area against the cutoff. This prevents flutter when the trail is
139  // very close to a straight line.
140  if( !m_forced && refLength > minAreaCutoffDistanceFactor * m_tolerance )
141  {
142  double areaCutoff = m_tolerance * refLength;
143  SHAPE_LINE_CHAIN trail( m_trail );
144  trail.SetClosed( true );
145 
146  if( std::abs( trail.Area() ) > areaCutoff )
147  areaOk = true;
148 }
149 
150  DIRECTION_45 straightDirection;
151  DIRECTION_45 diagDirection;
152  DIRECTION_45 newDirection = m_direction;
153 
154  straightDirection = DIRECTION_45( straight.CSegment( 0 ) );
155  diagDirection = DIRECTION_45( diag.CSegment( 0 ) );
156 
157  if( !m_forced && areaOk && ratio > areaRatioThreshold + areaRatioEpsilon )
158  newDirection = diagDirection;
159  else if( !m_forced && areaOk && ratio < ( 1.0 / areaRatioThreshold ) - areaRatioEpsilon )
160  newDirection = straightDirection;
161  else
162  newDirection = m_direction.IsDiagonal() ? diagDirection : straightDirection;
163 
164  if( !m_disableMouse && newDirection != m_direction )
165  {
166  wxLogTrace( "PNS", "Posture: direction update %s => %s", m_direction.Format(),
167  newDirection.Format() );
168  m_direction = newDirection;
169  }
170 
171  // If we have a last segment, correct the direction relative to it. For segment exit, we want
172  // to correct to the least obtuse
174  {
175  wxLogTrace( "PNS", "Posture: checking direction %s against last seg %s",
177 
178  if( straightDirection == m_lastSegDirection )
179 {
180  if( m_direction != straightDirection )
181  {
182  wxLogTrace( "PNS", "Posture: forcing straight => %s", straightDirection.Format() );
183  }
184 
185  m_direction = straightDirection;
186  }
187  else if( diagDirection == m_lastSegDirection )
188  {
189  if( m_direction != straightDirection )
190  {
191  wxLogTrace( "PNS", "Posture: forcing diagonal => %s", diagDirection.Format() );
192  }
193 
194  m_direction = diagDirection;
195  }
196  else
197  {
199  {
201  // Force a better (acute) connection
202  m_direction = m_direction.IsDiagonal() ? straightDirection : diagDirection;
203  wxLogTrace( "PNS", "Posture: correcting half full => %s", m_direction.Format() );
204  break;
205 
207  {
208  // Force a better connection by flipping if possible
209  DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
210  : diagDirection;
211 
212  if( candidate.Angle( m_lastSegDirection ) == DIRECTION_45::ANG_RIGHT )
213  {
214  wxLogTrace( "PNS", "Posture: correcting right => %s", candidate.Format() );
215  m_direction = candidate;
216  }
217 
218  break;
219 }
220 
222  {
223  // Force a better connection by flipping if possible
224  DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
225  : diagDirection;
226 
228  {
229  wxLogTrace( "PNS", "Posture: correcting obtuse => %s", candidate.Format() );
230  m_direction = candidate;
231  }
232 
233  break;
234  }
235 
236  default:
237  break;
238  }
239  }
240  }
241 
242  // If we get far away from the initial point, lock in the current solution to prevent flutter
243  if( !m_forced && refLength > lockDistanceFactor * m_tolerance )
244  {
245  wxLogTrace( "PNS", "Posture: solution locked" );
246  m_forced = true;
247  }
248 
249  return m_direction;
250 }
251 
252 
254 {
256  m_forced = true;
257  m_manuallyForced = true;
258 }
259 
260 
262 {
263  if( m_trail.PointCount() < 2 )
264  {
265  return VECTOR2I(0, 0);
266  }
267  else
268  {
269  return m_trail.CPoint( -1 ) - m_trail.CPoint( 0 );
270  }
271 }
272 
273 }
274 
int Length() const
Return the length (this).
Definition: seg.h:355
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:239
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
Definition: direction45.h:238
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
void AddTrailPoint(const VECTOR2I &aP)
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:201
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:41
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
DIRECTION_45 GetPosture(const VECTOR2I &aP)
void Clear()
Function Clear() Removes all points from the line chain.
Push and Shove diff pair dimensions (gap) settings dialog.
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
static ROUTER * GetInstance()
Definition: pns_router.cpp:79