KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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& aArc, int aClearance, int aWalkaroundThickness )
68{
69 int cl = aClearance + ( aWalkaroundThickness + 1 ) / 2;
70
71 // If we can't route through the arc, we might as well treat it as a circle
72 if( aArc.GetCentralAngle().AsDegrees() > 180.0 && aArc.GetChord().Length() < cl )
73 {
74 int r = aArc.GetRadius();
75 return OctagonalHull( aArc.GetCenter() - VECTOR2I( r, r ),
76 VECTOR2I( 2 * r, 2 * r ),
77 cl,
78 2.0 * ( 1.0 - M_SQRT1_2 ) * ( r + cl ) );
79 }
80
81 int d = aArc.GetWidth() / 2 + cl + SHAPE_ARC::DefaultAccuracyForPCB();
82 int x = (int) ( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
83
84 auto line = aArc.ConvertToPolyline( ARC_LOW_DEF );
85
87 s.SetClosed( true );
88 std::vector<VECTOR2I> reverse_line;
89
90 auto seg = line.Segment( 0 );
91 VECTOR2I dir = seg.B - seg.A;
92 VECTOR2I p0 = -dir.Perpendicular().Resize( d );
93 VECTOR2I ds = -dir.Perpendicular().Resize( x );
94 VECTOR2I pd = dir.Resize( x );
95 VECTOR2I dp = dir.Resize( d );
96
97 // Append the first curve
98 s.Append( seg.A + p0 - pd );
99 s.Append( seg.A - dp + ds );
100 s.Append( seg.A - dp - ds );
101 s.Append( seg.A - p0 - pd );
102
103 for( int i = 1; i < line.SegmentCount(); i++ )
104 {
105 // calculate a vertex normal (average of segment normals)
106 auto pp =
107 ( line.CSegment( i - 1 ).B - line.CSegment( i - 1 ).A ).Perpendicular().Resize( d );
108 auto pp2 = ( line.CSegment( i ).B - line.CSegment( i ).A ).Perpendicular().Resize( d );
109
110 auto sa_out = line.CSegment( i - 1 ), sa_in = line.CSegment( i - 1 );
111 auto sb_out = line.CSegment( i ), sb_in = line.CSegment( i );
112
113 sa_out.A += pp;
114 sa_out.B += pp;
115 sb_out.A += pp2;
116 sb_out.B += pp2;
117
118 sa_in.A -= pp;
119 sa_in.B -= pp;
120 sb_in.A -= pp2;
121 sb_in.B -= pp2;
122
123 auto ip_out = sa_out.IntersectLines( sb_out );
124 auto ip_in = sa_in.IntersectLines( sb_in );
125
126 seg = line.CSegment( i );
127 auto lead = ( pp + pp2 ) / 2;
128
129 s.Append( *ip_out );
130 reverse_line.push_back( *ip_in );
131 }
132
133 seg = line.CSegment( -1 );
134 dir = seg.B - seg.A;
135 p0 = -dir.Perpendicular().Resize( d );
136 ds = -dir.Perpendicular().Resize( x );
137 pd = dir.Resize( x );
138 dp = dir.Resize( d );
139 s.Append( seg.B - p0 + pd );
140 s.Append( seg.B + dp - ds );
141 s.Append( seg.B + dp + ds );
142 s.Append( seg.B + p0 + pd );
143
144 for( int i = reverse_line.size() - 1; i >= 0; i-- )
145 s.Append( reverse_line[i] );
146
147 // make sure the hull outline is always clockwise
148 if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
149 return s.Reverse();
150 else
151 return s;
152}
153
154
155static bool IsSegment45Degree( const SEG& aS )
156{
157 VECTOR2I dir( aS.B - aS.A );
158
159 if( std::abs( dir.x ) <= 1 )
160 return true;
161
162 if( std::abs( dir.y ) <= 1 )
163 return true;
164
165 int delta = std::abs(dir.x) - std::abs(dir.y);
166
167 if( delta >= -1 && delta <= 1)
168 return true;
169
170 return false;
171}
172
173
174template <typename T> int sgn(T val) {
175 return (T(0) < val) - (val < T(0));
176}
177
178
179const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
180 int aWalkaroundThickness )
181{
182 const int kinkThreshold = aClearance / 10;
183
184 int cl = aClearance + aWalkaroundThickness / 2;
185 double d = (double)aSeg.GetWidth() / 2.0 + cl;
186 double x = 2.0 / ( 1.0 + M_SQRT2 ) * d;
187 int dr = KiROUND( d );
188 int xr = KiROUND( x );
189 int xr2 = KiROUND( x / 2.0 );
190
191 const VECTOR2I a = aSeg.GetSeg().A;
192 VECTOR2I b = aSeg.GetSeg().B;
193 int len = aSeg.GetSeg().Length();
194 int w = b.x - a.x;
195 int h = b.y - a.y;
196
197 /*
198 auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
199
200 if( len < kinkThreshold )
201 {
202 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 ) );
203 }
204 */
205
206 if( a != b )
207 {
208 if ( !IsSegment45Degree( aSeg.GetSeg() ) )
209 {
210 if ( len <= kinkThreshold && len > 0 )
211 {
212 int ll = std::max( std::abs( w ), std::abs( h ) );
213
214 b = a + VECTOR2I( sgn( w ) * ll, sgn( h ) * ll );
215 }
216 }
217 else
218 {
219 if( len <= kinkThreshold )
220 {
221 int delta45 = std::abs( std::abs(w) - std::abs(h) );
222 if( std::abs(w) <= 1 ) // almost vertical
223 {
224 w = 0;
225 cl ++;
226 }
227 else if ( std::abs(h) <= 1 ) // almost horizontal
228 {
229 h = 0;
230 cl ++;
231 }
232 else if ( delta45 <= 2 ) // almost 45 degree
233 {
234 int newW = sgn( w ) * std::max( std::abs(w), std::abs( h ) );
235 int newH = sgn( h ) * std::max( std::abs(w), std::abs( h ) );
236 w = newW;
237 h = newH;
238 cl += 2;
239 //PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "almostkinky45 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
240
241 }
242
243 b.x = a.x + w;
244 b.y = a.y + h;
245 }
246 }
247 }
248
249 if( a == b )
250 {
251 int xx2 = KiROUND( 2.0 * ( 1.0 - M_SQRT1_2 ) * d );
252
253 auto ohull = OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
254 VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
255 cl,
256 xx2 );
257
258 return ohull;
259 }
260
261 VECTOR2I dir = b - a;
262 VECTOR2I p0 = dir.Perpendicular().Resize( dr );
263 VECTOR2I ds = dir.Perpendicular().Resize( xr2 );
264 VECTOR2I pd = dir.Resize( xr2 );
265 VECTOR2I dp = dir.Resize( dr );
266
268
269 s.SetClosed( true );
270
271 s.Append( b + p0 + pd );
272 s.Append( b + dp + ds );
273 s.Append( b + dp - ds );
274 s.Append( b - p0 + pd );
275 s.Append( a - p0 - pd );
276 s.Append( a - dp - ds );
277 s.Append( a - dp + ds );
278 s.Append( a + p0 - pd );
279
280 // make sure the hull outline is always clockwise
281 if( s.CSegment( 0 ).Side( a ) < 0 )
282 return s.Reverse();
283 else
284 return s;
285}
286
287
288static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
289{
290 int dist;
291
292 aVertices.NearestPoint( aDiagonal, dist );
293 VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
294 aDiagonal.A += moveBy;
295 aDiagonal.B += moveBy;
296}
297
298
299const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
300{
301 // this defines the horizontal and vertical lines in the hull octagon
302 BOX2I box = aConvex.BBox( aClearance );
303 box.Normalize();
304
305 SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
306 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
307 SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
308 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
309 SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
310 box.GetOrigin() );
311 SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
312
313 const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
314
315 // top right diagonal
316 VECTOR2I corner = box.GetOrigin() + box.GetSize();
317 SEG toprightline = SEG( corner,
318 corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
319 MoveDiagonal( toprightline, vertices, aClearance );
320
321 // bottom right diagonal
322 corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
323 SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
324 corner );
325 MoveDiagonal( bottomrightline, vertices, aClearance );
326
327 // bottom left diagonal
328 corner = box.GetOrigin();
329 SEG bottomleftline = SEG( corner,
330 corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
331 MoveDiagonal( bottomleftline, vertices, aClearance );
332
333 // top left diagonal
334 corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
335 SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
336 corner );
337 MoveDiagonal( topleftline, vertices, aClearance );
338
339 SHAPE_LINE_CHAIN octagon;
340 octagon.SetClosed( true );
341
342 octagon.Append( *leftline.IntersectLines( bottomleftline ) );
343 octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
344 octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
345 octagon.Append( *rightline.IntersectLines( bottomrightline ) );
346 octagon.Append( *rightline.IntersectLines( toprightline ) );
347 octagon.Append( *topline.IntersectLines( toprightline ) );
348 octagon.Append( *topline.IntersectLines( topleftline ) );
349 octagon.Append( *leftline.IntersectLines( topleftline ) );
350
351 return octagon;
352}
353
354
356{
357 SHAPE_RECT r;
358
359 VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
360 VECTOR2I p0( aSeg.GetSeg().A - delta );
361 VECTOR2I p1( aSeg.GetSeg().B + delta );
362
363 return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
364 std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
365}
366
367
368OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
369{
370 if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
371 {
372 const VIA* va = static_cast<const VIA*>( aItemA );
373 const VIA* vb = static_cast<const VIA*>( aItemB );
374
375 return va->ChangedArea( vb );
376 }
377 else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
378 {
379 const LINE* la = static_cast<const LINE*> ( aItemA );
380 const LINE* lb = static_cast<const LINE*> ( aItemB );
381
382 return la->ChangedArea( lb );
383 }
384
385 return OPT_BOX2I();
386}
387
388OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
389{
390 return aLineA.ChangedArea( &aLineB );
391}
392
393
396{
398
399 if( line.PointCount() < 2 )
400 return;
401
402 hull.Intersect( line, ips_raw );
403
404 for( auto& p : ips_raw )
405 {
407
408 SEG d1[2];
409 VECTOR2I d2[2];
410 int d1_idx = 0, d2_idx = 0;
411
412 ipp = p;
413 ipp.valid = false;
414
415 if( !p.is_corner_our && !p.is_corner_their )
416 {
417 ipp.valid = true;
418 ips.push_back( ipp );
419 continue;
420 }
421
422 if( p.index_our >= hull.SegmentCount() )
423 p.index_our -= hull.SegmentCount();
424
425 if( p.is_corner_our )
426 {
427 d1[0] = hull.CSegment( p.index_our );
428 d1[1] = hull.CSegment( p.index_our - 1 );
429 d1_idx = 2;
430 }
431 else
432 {
433 d1[0] = hull.CSegment( p.index_our );
434 d1_idx = 1;
435 }
436
437 if( p.is_corner_their )
438 {
439 if( p.index_their > 0 )
440 {
441 d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
442 }
443 if( p.index_their < line.PointCount() - 1 )
444 {
445 d2[d2_idx++] = line.CSegment( p.index_their ).B;
446 }
447 }
448 else
449 {
450 d2[d2_idx++] = line.CSegment( p.index_their ).A;
451 d2[d2_idx++] = line.CSegment( p.index_their ).B;
452 }
453
454 for( int i = 0; i < d1_idx; i++ )
455 {
456 for( int j = 0; j < d2_idx; j++ )
457 {
458 if( d1[i].Side( d2[j] ) > 0 )
459 {
460 ipp.valid = true;
461 }
462 }
463 }
464
465#ifdef TOM_EXTRA_DEBUG
466 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);
467 printf("d1 %d d2 %d\n", d1_idx, d2_idx );
468#endif
469 if( ipp.valid )
470 {
471 ips.push_back( ipp );
472 }
473 }
474}
475
476
477const SHAPE_LINE_CHAIN BuildHullForPrimitiveShape( const SHAPE* aShape, int aClearance,
478 int aWalkaroundThickness )
479{
480 int cl = aClearance + ( aWalkaroundThickness + 1 )/ 2;
481
482 switch( aShape->Type() )
483 {
484 case SH_RECT:
485 {
486 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>( aShape );
487 return OctagonalHull( rect->GetPosition(),
488 rect->GetSize(),
489 cl,
490 0 );
491 }
492
493 case SH_CIRCLE:
494 {
495 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
496 int r = circle->GetRadius();
497 return OctagonalHull( circle->GetCenter() - VECTOR2I( r, r ),
498 VECTOR2I( 2 * r, 2 * r ),
499 cl,
500 2.0 * ( 1.0 - M_SQRT1_2 ) * ( r + cl ) );
501 }
502
503 case SH_SEGMENT:
504 {
505 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*>( aShape );
506 return SegmentHull( *seg, aClearance, aWalkaroundThickness );
507 }
508
509 case SH_ARC:
510 {
511 const SHAPE_ARC* arc = static_cast<const SHAPE_ARC*>( aShape );
512 return ArcHull( *arc, aClearance, aWalkaroundThickness );
513 }
514
515 case SH_SIMPLE:
516 {
517 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aShape );
518
519 return ConvexHull( *convex, cl );
520 }
521 default:
522 {
523 wxFAIL_MSG( wxString::Format( wxT( "Unsupported hull shape: %d (%s)." ),
524 aShape->Type(),
525 SHAPE_TYPE_asString( aShape->Type() ) ) );
526 break;
527 }
528 }
529
530 return SHAPE_LINE_CHAIN();
531}
532
533
534}
constexpr int ARC_LOW_DEF
Definition: base_units.h:119
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:880
BOX2< Vec > & Normalize()
Ensure that the height and width are positive.
Definition: box2.h:136
const Vec & GetOrigin() const
Definition: box2.h:200
const SizeVec & GetSize() const
Definition: box2.h:196
size_type GetHeight() const
Definition: box2.h:205
size_type GetWidth() const
Definition: box2.h:204
coord_type GetY() const
Definition: box2.h:198
coord_type GetX() const
Definition: box2.h:197
double AsDegrees() const
Definition: eda_angle.h:113
Base class for PNS router board items.
Definition: pns_item.h:97
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
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:1172
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:180
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
EDA_ANGLE GetCentralAngle() const
Definition: shape_arc.cpp:520
SEG GetChord() const
Definition: shape_arc.h:188
int GetWidth() const
Definition: shape_arc.h:158
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:542
double GetRadius() const
Definition: shape_arc.cpp:536
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:222
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:505
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:98
int GetRadius() const
Definition: shape_circle.h:118
const VECTOR2I GetCenter() const
Definition: shape_circle.h:123
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 VECTOR2I & GetPosition() const
Definition: shape_rect.h:127
const VECTOR2I GetSize() const
Definition: shape_rect.h:135
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
An abstract shape on 2D plane.
Definition: shape.h:126
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:309
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:380
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:394
const SHAPE_LINE_CHAIN BuildHullForPrimitiveShape(const SHAPE *aShape, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:477
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:355
const SHAPE_LINE_CHAIN ArcHull(const SHAPE_ARC &aArc, 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:299
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:179
static bool IsSegment45Degree(const SEG &aS)
Definition: pns_utils.cpp:155
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:288
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:368
int sgn(T val)
Definition: pns_utils.cpp:174
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:47
@ SH_CIRCLE
circle
Definition: shape.h:50
@ SH_SIMPLE
simple polygon
Definition: shape.h:51
@ SH_SEGMENT
line segment
Definition: shape.h:48
@ SH_ARC
circular arc
Definition: shape.h:54
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:59
Represent an intersection between two line segments.
bool valid
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
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:121
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:673