KiCad PCB EDA Suite
pns_utils.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016 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
22#include "pns_utils.h"
23#include "pns_line.h"
24#include "pns_via.h"
25#include "pns_router.h"
26#include "pns_debug_decorator.h"
27
28#include <geometry/shape_arc.h>
30#include <math/box2.h>
31
32#include <cmath>
33
34namespace PNS {
35
36const SHAPE_LINE_CHAIN OctagonalHull( const VECTOR2I& aP0, const VECTOR2I& aSize,
37 int aClearance, int aChamfer )
38{
40
41 s.SetClosed( true );
42
43 s.Append( aP0.x - aClearance, aP0.y - aClearance + aChamfer );
44
45 if( aChamfer )
46 s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
47
48 s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
49
50 if( aChamfer )
51 s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
52
53 s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
54
55 if( aChamfer )
56 s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
57
58 s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
59
60 if( aChamfer )
61 s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
62
63 return s;
64}
65
66
67const SHAPE_LINE_CHAIN ArcHull( const SHAPE_ARC& aSeg, int aClearance, int aWalkaroundThickness )
68{
69 int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2
71 int x = (int) ( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
72
73 auto line = aSeg.ConvertToPolyline();
74
76 s.SetClosed( true );
77 std::vector<VECTOR2I> reverse_line;
78
79 auto seg = line.Segment( 0 );
80 VECTOR2I dir = seg.B - seg.A;
81 VECTOR2I p0 = -dir.Perpendicular().Resize( d );
82 VECTOR2I ds = -dir.Perpendicular().Resize( x );
83 VECTOR2I pd = dir.Resize( x );
84 VECTOR2I dp = dir.Resize( d );
85
86 // Append the first curve
87 s.Append( seg.A + p0 - pd );
88 s.Append( seg.A - dp + ds );
89 s.Append( seg.A - dp - ds );
90 s.Append( seg.A - p0 - pd );
91
92 for( int i = 1; i < line.SegmentCount(); i++ )
93 {
94 // calculate a vertex normal (average of segment normals)
95 auto pp =
96 ( line.CSegment( i - 1 ).B - line.CSegment( i - 1 ).A ).Perpendicular().Resize( d );
97 auto pp2 = ( line.CSegment( i ).B - line.CSegment( i ).A ).Perpendicular().Resize( d );
98
99 auto sa_out = line.CSegment( i - 1 ), sa_in = line.CSegment( i - 1 );
100 auto sb_out = line.CSegment( i ), sb_in = line.CSegment( i );
101
102 sa_out.A += pp;
103 sa_out.B += pp;
104 sb_out.A += pp2;
105 sb_out.B += pp2;
106
107 sa_in.A -= pp;
108 sa_in.B -= pp;
109 sb_in.A -= pp2;
110 sb_in.B -= pp2;
111
112 auto ip_out = sa_out.IntersectLines( sb_out );
113 auto ip_in = sa_in.IntersectLines( sb_in );
114
115 seg = line.CSegment( i );
116 auto lead = ( pp + pp2 ) / 2;
117
118 s.Append( *ip_out );
119 reverse_line.push_back( *ip_in );
120 }
121
122 seg = line.CSegment( -1 );
123 dir = seg.B - seg.A;
124 p0 = -dir.Perpendicular().Resize( d );
125 ds = -dir.Perpendicular().Resize( x );
126 pd = dir.Resize( x );
127 dp = dir.Resize( d );
128 s.Append( seg.B - p0 + pd );
129 s.Append( seg.B + dp - ds );
130 s.Append( seg.B + dp + ds );
131 s.Append( seg.B + p0 + pd );
132
133 for( int i = reverse_line.size() - 1; i >= 0; i-- )
134 s.Append( reverse_line[i] );
135
136 // make sure the hull outline is always clockwise
137 // make sure the hull outline is always clockwise
138 if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
139 return s.Reverse();
140 else
141 return s;
142}
143
144
145static bool IsSegment45Degree( const SEG& aS )
146{
147 VECTOR2I dir( aS.B - aS.A );
148
149 if( std::abs( dir.x ) <= 1 )
150 return true;
151
152 if( std::abs( dir.y ) <= 1 )
153 return true;
154
155 int delta = std::abs(dir.x) - std::abs(dir.y);
156
157 if( delta >= -1 && delta <= 1)
158 return true;
159
160 return false;
161}
162
163
164template <typename T> int sgn(T val) {
165 return (T(0) < val) - (val < T(0));
166}
167
168
169const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
170 int aWalkaroundThickness )
171{
172 const int kinkThreshold = aClearance / 10;
173
174 int cl = aClearance + aWalkaroundThickness / 2;
175 double d = (double)aSeg.GetWidth() / 2.0 + cl;
176 double x = 2.0 / ( 1.0 + M_SQRT2 ) * d;
177 int dr = KiROUND( d );
178 int xr = KiROUND( x );
179 int xr2 = KiROUND( x / 2.0 );
180
181 const VECTOR2I a = aSeg.GetSeg().A;
182 VECTOR2I b = aSeg.GetSeg().B;
183 int len = aSeg.GetSeg().Length();
184 int w = b.x - a.x;
185 int h = b.y - a.y;
186
187 /*
188 auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
189
190 if( len < kinkThreshold )
191 {
192 PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "kinky-seg 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
193 }
194 */
195
196 if( a != b )
197 {
198 if ( !IsSegment45Degree( aSeg.GetSeg() ) )
199 {
200 if ( len <= kinkThreshold && len > 0 )
201 {
202 int ll = std::max( std::abs( w ), std::abs( h ) );
203
204 b = a + VECTOR2I( sgn( w ) * ll, sgn( h ) * ll );
205 }
206 }
207 else
208 {
209 if( len <= kinkThreshold )
210 {
211 int delta45 = std::abs( std::abs(w) - std::abs(h) );
212 if( std::abs(w) <= 1 ) // almost vertical
213 {
214 w = 0;
215 cl ++;
216 }
217 else if ( std::abs(h) <= 1 ) // almost horizontal
218 {
219 h = 0;
220 cl ++;
221 }
222 else if ( delta45 <= 2 ) // almost 45 degree
223 {
224 int newW = sgn( w ) * std::max( std::abs(w), std::abs( h ) );
225 int newH = sgn( h ) * std::max( std::abs(w), std::abs( h ) );
226 w = newW;
227 h = newH;
228 cl += 2;
229 //PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "almostkinky45 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
230
231 }
232
233 b.x = a.x + w;
234 b.y = a.y + h;
235 }
236 }
237 }
238
239 if( a == b )
240 {
241 int xx2 = KiROUND( 2.0 * ( 1.0 - M_SQRT1_2 ) * d );
242
243 auto ohull = OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
244 VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
245 cl,
246 xx2 );
247
248 return ohull;
249 }
250
251 VECTOR2I dir = b - a;
252 VECTOR2I p0 = dir.Perpendicular().Resize( dr );
253 VECTOR2I ds = dir.Perpendicular().Resize( xr2 );
254 VECTOR2I pd = dir.Resize( xr2 );
255 VECTOR2I dp = dir.Resize( dr );
256
258
259 s.SetClosed( true );
260
261 s.Append( b + p0 + pd );
262 s.Append( b + dp + ds );
263 s.Append( b + dp - ds );
264 s.Append( b - p0 + pd );
265 s.Append( a - p0 - pd );
266 s.Append( a - dp - ds );
267 s.Append( a - dp + ds );
268 s.Append( a + p0 - pd );
269
270 // make sure the hull outline is always clockwise
271 if( s.CSegment( 0 ).Side( a ) < 0 )
272 return s.Reverse();
273 else
274 return s;
275}
276
277
278static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
279{
280 int dist;
281
282 aVertices.NearestPoint( aDiagonal, dist );
283 VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
284 aDiagonal.A += moveBy;
285 aDiagonal.B += moveBy;
286}
287
288
289const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
290{
291 // this defines the horizontal and vertical lines in the hull octagon
292 BOX2I box = aConvex.BBox( aClearance );
293 box.Normalize();
294
295 SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
296 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
297 SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
298 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
299 SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
300 box.GetOrigin() );
301 SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
302
303 const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
304
305 // top right diagonal
306 VECTOR2I corner = box.GetOrigin() + box.GetSize();
307 SEG toprightline = SEG( corner,
308 corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
309 MoveDiagonal( toprightline, vertices, aClearance );
310
311 // bottom right diagonal
312 corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
313 SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
314 corner );
315 MoveDiagonal( bottomrightline, vertices, aClearance );
316
317 // bottom left diagonal
318 corner = box.GetOrigin();
319 SEG bottomleftline = SEG( corner,
320 corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
321 MoveDiagonal( bottomleftline, vertices, aClearance );
322
323 // top left diagonal
324 corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
325 SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
326 corner );
327 MoveDiagonal( topleftline, vertices, aClearance );
328
329 SHAPE_LINE_CHAIN octagon;
330 octagon.SetClosed( true );
331
332 octagon.Append( *leftline.IntersectLines( bottomleftline ) );
333 octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
334 octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
335 octagon.Append( *rightline.IntersectLines( bottomrightline ) );
336 octagon.Append( *rightline.IntersectLines( toprightline ) );
337 octagon.Append( *topline.IntersectLines( toprightline ) );
338 octagon.Append( *topline.IntersectLines( topleftline ) );
339 octagon.Append( *leftline.IntersectLines( topleftline ) );
340
341 return octagon;
342}
343
344
346{
347 SHAPE_RECT r;
348
349 VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
350 VECTOR2I p0( aSeg.GetSeg().A - delta );
351 VECTOR2I p1( aSeg.GetSeg().B + delta );
352
353 return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
354 std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
355}
356
357
358OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
359{
360 if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
361 {
362 const VIA* va = static_cast<const VIA*>( aItemA );
363 const VIA* vb = static_cast<const VIA*>( aItemB );
364
365 return va->ChangedArea( vb );
366 }
367 else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
368 {
369 const LINE* la = static_cast<const LINE*> ( aItemA );
370 const LINE* lb = static_cast<const LINE*> ( aItemB );
371
372 return la->ChangedArea( lb );
373 }
374
375 return OPT_BOX2I();
376}
377
378OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
379{
380 return aLineA.ChangedArea( &aLineB );
381}
382
383
386{
388
389 if( line.PointCount() < 2 )
390 return;
391
392 hull.Intersect( line, ips_raw );
393
394 for( auto& p : ips_raw )
395 {
397
398 SEG d1[2];
399 VECTOR2I d2[2];
400 int d1_idx = 0, d2_idx = 0;
401
402 ipp = p;
403 ipp.valid = false;
404
405 if( !p.is_corner_our && !p.is_corner_their )
406 {
407 ipp.valid = true;
408 ips.push_back( ipp );
409 continue;
410 }
411
412 if( p.index_our >= hull.SegmentCount() )
413 p.index_our -= hull.SegmentCount();
414
415 if( p.is_corner_our )
416 {
417 d1[0] = hull.CSegment( p.index_our );
418 d1[1] = hull.CSegment( p.index_our - 1 );
419 d1_idx = 2;
420 }
421 else
422 {
423 d1[0] = hull.CSegment( p.index_our );
424 d1_idx = 1;
425 }
426
427 if( p.is_corner_their )
428 {
429 if( p.index_their > 0 )
430 {
431 d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
432 }
433 if( p.index_their < line.PointCount() - 1 )
434 {
435 d2[d2_idx++] = line.CSegment( p.index_their ).B;
436 }
437 }
438 else
439 {
440 d2[d2_idx++] = line.CSegment( p.index_their ).A;
441 d2[d2_idx++] = line.CSegment( p.index_their ).B;
442 }
443
444 for( int i = 0; i < d1_idx; i++ )
445 {
446 for( int j = 0; j < d2_idx; j++ )
447 {
448 if( d1[i].Side( d2[j] ) > 0 )
449 {
450 ipp.valid = true;
451 }
452 }
453 }
454
455#ifdef TOM_EXTRA_DEBUG
456 printf("p %d %d hi %d their %d co %d ct %d ipv %d\n", p.p.x, p.p.y, p.index_our, p.index_their, p.is_corner_our?1:0, p.is_corner_their?1:0, ipp.valid ?1:0);
457 printf("d1 %d d2 %d\n", d1_idx, d2_idx );
458#endif
459 if( ipp.valid )
460 {
461 ips.push_back( ipp );
462 }
463 }
464}
465
466}
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:850
BOX2< Vec > & Normalize()
Ensure that the height and width are positive.
Definition: box2.h:119
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetY() const
Definition: box2.h:181
coord_type GetWidth() const
Definition: box2.h:187
coord_type GetX() const
Definition: box2.h:180
const Vec & GetSize() const
Definition: box2.h:179
Base class for PNS router board items.
Definition: pns_item.h:56
@ LINE_T
Definition: pns_item.h:64
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:140
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1152
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:200
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Length() const
Return the length (this).
Definition: seg.h:326
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
int GetWidth() const
Definition: shape_arc.h:157
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:470
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:221
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.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
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.
std::vector< INTERSECTION > INTERSECTIONS
const SEG & GetSeg() const
int GetWidth() const
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:42
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:78
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:307
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378
Push and Shove diff pair dimensions (gap) settings dialog.
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:384
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:36
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:345
const SHAPE_LINE_CHAIN ArcHull(const SHAPE_ARC &aSeg, int aClearance, int aWalkaroundThickness)
Various utility functions.
Definition: pns_utils.cpp:67
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:289
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:169
static bool IsSegment45Degree(const SEG &aS)
Definition: pns_utils.cpp:145
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:278
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:358
int sgn(T val)
Definition: pns_utils.cpp:164
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
Represent an intersection between two line segments.
constexpr int delta
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:85
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618