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 <[email protected]>
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
22#include "pns_router.h"
23#include "pns_debug_decorator.h"
24
25namespace 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 if( m_trail.SegmentCount() > 2 )
57 {
58 SEG::ecoord limit = ( static_cast<SEG::ecoord>( m_tolerance ) * m_tolerance );
59
60 for( int i = 0; i < m_trail.SegmentCount() - 2; i++ )
61 {
62 const SEG& s_trail = m_trail.CSegment( i );
63
64 if( s_trail.SquaredDistance( s_new ) <= limit )
65 {
66 m_trail = m_trail.Slice( 0, i );
67 break;
68 }
69 }
70 }
71
72 m_trail.Append( aP );
73 }
74
76
78
79 PNS_DBG( dbg, AddShape, &m_trail, CYAN, 50000, wxT( "mt-trail" ) );
80}
81
82
84{
85 // Tuning factor for how good the "fit" of the trail must be to the posture
86 const double areaRatioThreshold = 1.3;
87
88 // Tuning factor to minimize flutter
89 const double areaRatioEpsilon = 0.25;
90
91 // Minimum distance factor of the trail before the min area test is used to lock the solver
92 const double minAreaCutoffDistanceFactor = 6;
93
94 // Adjusts how far away from p0 we get before whatever posture we solved is locked in
95 const int lockDistanceFactor = 30;
96
97 // Adjusts how close to p0 we unlock the posture again if one was locked already
98 const int unlockDistanceFactor = 10;
99
100 if( m_trail.PointCount() < 2 || m_manuallyForced )
101 {
102 // If mouse trail detection is enabled; using the last seg direction as a starting point
103 // will give the best results. Otherwise, just assume that we switch postures every
104 // segment.
107
108 return m_direction;
109 }
110
112 VECTOR2I p0 = m_trail.CPoint( 0 );
113 double refLength = SEG( p0, aP ).Length();
114 SHAPE_LINE_CHAIN straight( DIRECTION_45().BuildInitialTrace( p0, aP, false ) );
115
116 straight.SetClosed( true );
117 straight.Append( m_trail.Reverse() );
118 straight.Simplify();
119
120 PNS_DBG( dbg, AddShape, &straight, m_forced ? BLUE : GREEN, 100000, wxT( "mt-straight" ) );
121
122 double areaS = straight.Area();
123
124 SHAPE_LINE_CHAIN diag( DIRECTION_45().BuildInitialTrace( p0, aP, true ) );
125 diag.Append( m_trail.Reverse() );
126 diag.SetClosed( true );
127 diag.Simplify();
128
129 PNS_DBG( dbg, AddShape, &diag, YELLOW, 100000, wxT( "mt-diag" ) );
130
131 double areaDiag = diag.Area();
132 double ratio = areaS / ( areaDiag + 1.0 );
133
134 // heuristic to detect that the user dragged back the cursor to the beginning of the trace
135 // in this case, we cancel any forced posture and restart the trail
136 if( m_forced && refLength < unlockDistanceFactor * m_tolerance )
137 {
138 PNS_DBG( dbg, Message, "Posture: Unlocked and reset" );
139 m_forced = false;
140 VECTOR2I start = p0;
141 m_trail.Clear();
142 m_trail.Append( start );
143 }
144
145 bool areaOk = false;
146
147 // Check the actual trail area against the cutoff. This prevents flutter when the trail is
148 // very close to a straight line.
149 if( !m_forced && refLength > minAreaCutoffDistanceFactor * m_tolerance )
150 {
151 double areaCutoff = m_tolerance * refLength;
152 SHAPE_LINE_CHAIN trail( m_trail );
153 trail.SetClosed( true );
154
155 if( trail.Area() > areaCutoff )
156 areaOk = true;
157 }
158
159 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 ) );
160
161 DIRECTION_45 straightDirection;
162 DIRECTION_45 diagDirection;
163 DIRECTION_45 newDirection = m_direction;
164
165 straightDirection = DIRECTION_45( straight.CSegment( 0 ) );
166 diagDirection = DIRECTION_45( diag.CSegment( 0 ) );
167
168 if( !m_forced && areaOk && ratio > areaRatioThreshold + areaRatioEpsilon )
169 newDirection = diagDirection;
170 else if( !m_forced && areaOk && ratio < ( 1.0 / areaRatioThreshold ) - areaRatioEpsilon )
171 newDirection = straightDirection;
172 else
173 newDirection = m_direction.IsDiagonal() ? diagDirection : straightDirection;
174
175 if( !m_disableMouse && newDirection != m_direction )
176 {
177 PNS_DBG( dbg, Message, wxString::Format( "Posture: direction update %s => %s",
178 m_direction.Format(), newDirection.Format() ) );
179 m_direction = newDirection;
180 }
181
182 // If we have a last segment, correct the direction relative to it. For segment exit, we want
183 // to correct to the least obtuse
185 {
186 PNS_DBG( dbg, Message,
187 wxString::Format( wxT( "Posture: checking direction %s against last seg %s" ),
189
190 if( straightDirection == m_lastSegDirection )
191 {
192 if( m_direction != straightDirection )
193 {
194 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: forcing straight => %s" ),
195 straightDirection.Format() ) );
196 }
197
198 m_direction = straightDirection;
199 }
200 else if( diagDirection == m_lastSegDirection )
201 {
202 if( m_direction != diagDirection )
203 {
204 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: forcing diagonal => %s" ),
205 diagDirection.Format() ) );
206 }
207
208 m_direction = diagDirection;
209 }
210 else
211 {
213 {
215 // Force a better (acute) connection
216 m_direction = m_direction.IsDiagonal() ? straightDirection : diagDirection;
217 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting half full => %s" ),
218 m_direction.Format() ) );
219 break;
220
222 {
223 // Force a better connection by flipping if possible
224 DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
225 : diagDirection;
226
228 {
229 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting right => %s" ),
230 candidate.Format() ) );
231 m_direction = candidate;
232 }
233
234 break;
235 }
236
238 {
239 // Force a better connection by flipping if possible
240 DIRECTION_45 candidate = m_direction.IsDiagonal() ? straightDirection
241 : diagDirection;
242
244 {
245 PNS_DBG( dbg, Message, wxString::Format( wxT( "Posture: correcting obtuse => %s" ),
246 candidate.Format() ) );
247 m_direction = candidate;
248 }
249
250 break;
251 }
252
253 default:
254 break;
255 }
256 }
257 }
258
259 // If we get far away from the initial point, lock in the current solution to prevent flutter
260 if( !m_forced && refLength > lockDistanceFactor * m_tolerance )
261 {
262 PNS_DBG( dbg, Message, "Posture: solution locked" );
263 m_forced = true;
264 }
265
266 return m_direction;
267}
268
269
271{
273 m_forced = true;
274 m_manuallyForced = true;
275}
276
277
279{
280 if( m_trail.PointCount() < 2 )
281 {
282 return VECTOR2I(0, 0);
283 }
284 else
285 {
286 return m_trail.CPoint( -1 ) - m_trail.CPoint( 0 );
287 }
288}
289
290}
291
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.
Definition: direction45.h:181
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:213
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
Definition: direction45.h:251
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:129
void AddTrailPoint(const VECTOR2I &aP)
DIRECTION_45 GetPosture(const VECTOR2I &aP)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
int Length() const
Return the length (this).
Definition: seg.h:326
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
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 VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this 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,...)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618