KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
23#include "pns_router.h"
24#include "pns_debug_decorator.h"
25
26namespace PNS {
27
34
35
37
38
40{
41 m_forced = false;
42 m_manuallyForced = false;
43 m_trail.Clear();
44}
45
46
48{
49 if( m_trail.SegmentCount() == 0 )
50 {
51 m_trail.Append( aP );
52 }
53 else
54 {
55 SEG s_new( m_trail.CLastPoint(), aP );
56
57 if( m_trail.SegmentCount() > 2 )
58 {
59 SEG::ecoord limit = ( static_cast<SEG::ecoord>( m_tolerance ) * m_tolerance );
60
61 for( int i = 0; i < m_trail.SegmentCount() - 2; i++ )
62 {
63 const SEG& s_trail = m_trail.CSegment( i );
64
65 if( s_trail.SquaredDistance( s_new ) <= limit )
66 {
67 m_trail = m_trail.Slice( 0, i );
68 break;
69 }
70 }
71 }
72
73 m_trail.Append( aP );
74 }
75
76 m_trail.Simplify();
77
79
80 PNS_DBG( dbg, AddShape, &m_trail, CYAN, 50000, wxT( "mt-trail" ) );
81}
82
83
85{
86 // Tuning factor for how good the "fit" of the trail must be to the posture
87 const double areaRatioThreshold = 1.3;
88
89 // Tuning factor to minimize flutter
90 const double areaRatioEpsilon = 0.25;
91
92 // Minimum distance factor of the trail before the min area test is used to lock the solver
93 const double minAreaCutoffDistanceFactor = 6;
94
95 // Adjusts how far away from p0 we get before whatever posture we solved is locked in
96 const int lockDistanceFactor = 30;
97
98 // Adjusts how close to p0 we unlock the posture again if one was locked already
99 const int unlockDistanceFactor = 10;
100
101 if( m_trail.PointCount() < 2 || m_manuallyForced )
102 {
103 // If mouse trail detection is enabled; using the last seg direction as a starting point
104 // will give the best results. Otherwise, just assume that we switch postures every
105 // segment.
108
109 return m_direction;
110 }
111
113 VECTOR2I p0 = m_trail.CPoint( 0 );
114 double refLength = SEG( p0, aP ).Length();
115 SHAPE_LINE_CHAIN straight( DIRECTION_45().BuildInitialTrace( p0, aP, false ) );
116
117 straight.SetClosed( true );
118 straight.Append( m_trail.Reverse() );
119 straight.Simplify();
120
121 PNS_DBG( dbg, AddShape, &straight, m_forced ? BLUE : GREEN, 100000, wxT( "mt-straight" ) );
122
123 double areaS = straight.Area();
124
125 SHAPE_LINE_CHAIN diag( DIRECTION_45().BuildInitialTrace( p0, aP, true ) );
126 diag.Append( m_trail.Reverse() );
127 diag.SetClosed( true );
128 diag.Simplify();
129
130 PNS_DBG( dbg, AddShape, &diag, YELLOW, 100000, wxT( "mt-diag" ) );
131
132 double areaDiag = diag.Area();
133 double ratio = areaS / ( areaDiag + 1.0 );
134
135 // heuristic to detect that the user dragged back the cursor to the beginning of the trace
136 // in this case, we cancel any forced posture and restart the trail
137 if( m_forced && refLength < unlockDistanceFactor * m_tolerance )
138 {
139 PNS_DBG( dbg, Message, "Posture: Unlocked and reset" );
140 m_forced = false;
141 VECTOR2I start = p0;
142 m_trail.Clear();
143 m_trail.Append( start );
144 }
145
146 bool areaOk = false;
147
148 // Check the actual trail area against the cutoff. This prevents flutter when the trail is
149 // very close to a straight line.
150 if( !m_forced && refLength > minAreaCutoffDistanceFactor * m_tolerance )
151 {
152 double areaCutoff = m_tolerance * refLength;
153 SHAPE_LINE_CHAIN trail( m_trail );
154 trail.SetClosed( true );
155
156 if( trail.Area() > areaCutoff )
157 areaOk = true;
158 }
159
160 PNS_DBG( dbg, Message, wxString::Format( "Posture: rl %.0f thr %d tol %d as %.3f area OK %d forced %d\n", refLength, (int)(unlockDistanceFactor * m_tolerance), m_tolerance, ratio, areaOk?1:0, m_forced?1:0 ) );
161
162 DIRECTION_45 straightDirection;
163 DIRECTION_45 diagDirection;
164 DIRECTION_45 newDirection = m_direction;
165
166 straightDirection = DIRECTION_45( straight.CSegment( 0 ) );
167 diagDirection = DIRECTION_45( diag.CSegment( 0 ) );
168
169 if( !m_forced && areaOk && ratio > areaRatioThreshold + areaRatioEpsilon )
170 newDirection = diagDirection;
171 else if( !m_forced && areaOk && ratio < ( 1.0 / areaRatioThreshold ) - areaRatioEpsilon )
172 newDirection = straightDirection;
173 else
174 newDirection = m_direction.IsDiagonal() ? diagDirection : straightDirection;
175
176 if( !m_disableMouse && newDirection != m_direction )
177 {
178 PNS_DBG( dbg, Message, wxString::Format( "Posture: direction update %s => %s",
179 m_direction.Format(), newDirection.Format() ) );
180 m_direction = newDirection;
181 }
182
183 // If we have a last segment, correct the direction relative to it. For segment exit, we want
184 // to correct to the least obtuse
186 {
187 PNS_DBG( dbg, Message,
188 wxString::Format( wxT( "Posture: checking direction %s against last seg %s" ),
189 m_direction.Format(), m_lastSegDirection.Format() ) );
190
191 if( straightDirection == m_lastSegDirection )
192 {
193 if( m_direction != straightDirection )
194 {
195 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: forcing straight => %s" ),
196 straightDirection.Format() ) );
197 }
198
199 m_direction = straightDirection;
200 }
201 else if( diagDirection == m_lastSegDirection )
202 {
203 if( m_direction != diagDirection )
204 {
205 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: forcing diagonal => %s" ),
206 diagDirection.Format() ) );
207 }
208
209 m_direction = diagDirection;
210 }
211 else
212 {
213 switch( m_direction.Angle( m_lastSegDirection ) )
214 {
216 // Force a better (acute) connection
217 m_direction = m_direction.IsDiagonal() ? straightDirection : diagDirection;
218 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting half full => %s" ),
219 m_direction.Format() ) );
220 break;
221
223 {
224 // Force a better connection by flipping if possible
225 DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
226 : diagDirection;
227
229 {
230 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting right => %s" ),
231 candidate.Format() ) );
232 m_direction = candidate;
233 }
234
235 break;
236 }
237
239 {
240 // Force a better connection by flipping if possible
241 DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
242 : diagDirection;
243
245 {
246 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting obtuse => %s" ),
247 candidate.Format() ) );
248 m_direction = candidate;
249 }
250
251 break;
252 }
253
254 default:
255 break;
256 }
257 }
258 }
259
260 // If we get far away from the initial point, lock in the current solution to prevent flutter
261 if( !m_forced && refLength > lockDistanceFactor * m_tolerance )
262 {
263 PNS_DBG( dbg, Message, "Posture: solution locked" );
264 m_forced = true;
265 }
266
267 return m_direction;
268}
269
270
272{
273 m_direction = m_direction.Right();
274 m_forced = true;
275 m_manuallyForced = true;
276}
277
278
280{
281 if( m_trail.PointCount() < 2 )
282 {
283 return VECTOR2I(0, 0);
284 }
285 else
286 {
287 return m_trail.CLastPoint() - m_trail.CPoint( 0 );
288 }
289}
290
291}
292
Represent route directions & corner angles in a 45-degree metric.
Definition direction45.h:37
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const std::string Format() const
Format the direction in a human readable word.
void AddTrailPoint(const VECTOR2I &aP)
DIRECTION_45 GetPosture(const VECTOR2I &aP)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition pns_router.h:232
static ROUTER * GetInstance()
Definition seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:80
VECTOR2I::extended_type ecoord
Definition seg.h:44
int Length() const
Return the length (this).
Definition seg.h:343
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
@ BLUE
Definition color4d.h:56
@ GREEN
Definition color4d.h:57
@ CYAN
Definition color4d.h:58
@ YELLOW
Definition color4d.h:67
Push and Shove diff pair dimensions (gap) settings dialog.
#define PNS_DBG(dbg, method,...)
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695