KiCad PCB EDA Suite
PNS Namespace Reference

Push and Shove diff pair dimensions (gap) settings dialog. More...

Classes

class  ALGO_BASE
 Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc.). More...
 
class  ANGLE_CONSTRAINT_45
 
class  ARC
 
class  AREA_CONSTRAINT
 
class  COMPONENT_DRAGGER
 COMPONENT_DRAGGER. More...
 
struct  CONSTRAINT
 
class  CORNER_COUNT_LIMIT_CONSTRAINT
 
class  COST_ESTIMATOR
 Calculate the cost of a given line, taking corner angles and total length into account. More...
 
class  DEBUG_DECORATOR
 
class  DIFF_PAIR
 Basic class for a differential pair. More...
 
class  DIFF_PAIR_PLACER
 Single track placement algorithm. More...
 
class  DP_GATEWAY
 Define a "gateway" for routing a differential pair - e.g. More...
 
class  DP_GATEWAYS
 A set of gateways calculated for the cursor or starting/ending primitive pair. More...
 
class  DP_MEANDER_PLACER
 Differential Pair length-matching/meandering tool. More...
 
class  DP_PRIMITIVE_PAIR
 Store starting/ending primitives (pads, vias or segments) for a differential pair. More...
 
class  DRAG_ALGO
 DRAG_ALGO. More...
 
class  DRAGGER
 DRAGGER. More...
 
class  FIXED_TAIL
 
struct  HIT_VISITOR
 
class  INDEX
 INDEX. More...
 
class  ITEM
 Base class for PNS router board items. More...
 
class  ITEM_SET
 
class  JOINT
 A 2D point on a given set of layers and belonging to a certain net, that links together a number of board items. More...
 
class  KEEP_TOPOLOGY_CONSTRAINT
 
class  LINE
 Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads, junctions between multiple traces or two traces different widths and combinations of these). More...
 
class  LINE_PLACER
 Single track placement algorithm. More...
 
class  LINK_HOLDER
 
class  LINKED_ITEM
 
class  LOGGER
 
class  MEANDER_PLACER
 Single track length matching/meandering tool. More...
 
class  MEANDER_PLACER_BASE
 Base class for Single trace & Differential pair meandering tools, as both of them share a lot of code. More...
 
class  MEANDER_SETTINGS
 Dimensions for the meandering algorithm. More...
 
class  MEANDER_SHAPE
 The geometry of a single meander. More...
 
class  MEANDER_SKEW_PLACER
 MEANDER_SKEW_PLACER. More...
 
class  MEANDERED_LINE
 Represent a set of meanders fitted over a single or two lines. More...
 
class  MOUSE_TRAIL_TRACER
 
class  NODE
 Keep the router "world" - i.e. More...
 
struct  OBSTACLE
 Hold an object colliding with another object, along with some useful data about the collision. More...
 
class  OBSTACLE_VISITOR
 
class  OPT_CONSTRAINT
 
class  OPTIMIZER
 Perform various optimizations of the lines being routed, attempting to make the lines shorter and less cornery. More...
 
class  PLACEMENT_ALGO
 PLACEMENT_ALGO. More...
 
class  PRESERVE_VERTEX_CONSTRAINT
 
class  RESTRICT_VERTEX_RANGE_CONSTRAINT
 
class  ROUTER
 
class  ROUTER_IFACE
 ROUTER. More...
 
class  ROUTING_SETTINGS
 Contain all persistent settings of the router, such as the mode, optimization effort, etc. More...
 
class  RULE_RESOLVER
 
class  SEGMENT
 
class  SHOVE
 The actual Push and Shove algorithm. More...
 
class  SIZES_SETTINGS
 
class  SOLID
 
class  TIME_LIMIT
 
class  TOOL_BASE
 
class  TOPOLOGY
 
class  VIA
 
struct  VIA_HANDLE
 
class  VVIA
 
class  WALKAROUND
 

Enumerations

enum  LineMarker {
  MK_HEAD = ( 1 << 0 ) , MK_VIOLATION = ( 1 << 3 ) , MK_LOCKED = ( 1 << 4 ) , MK_DP_COUPLED = ( 1 << 5 ) ,
  MK_HOLE = ( 1 << 6 )
}
 
enum  MEANDER_TYPE {
  MT_SINGLE , MT_START , MT_FINISH , MT_TURN ,
  MT_CHECK_START , MT_CHECK_FINISH , MT_CORNER , MT_ARC ,
  MT_EMPTY
}
 Shapes of available meanders. More...
 
enum  MEANDER_STYLE { MEANDER_STYLE_ROUND = 1 , MEANDER_STYLE_CHAMFER }
 
enum class  CONSTRAINT_TYPE {
  CT_CLEARANCE = 1 , CT_DIFF_PAIR_GAP = 2 , CT_LENGTH = 3 , CT_WIDTH = 4 ,
  CT_VIA_DIAMETER = 5 , CT_VIA_HOLE = 6 , CT_HOLE_CLEARANCE = 7 , CT_EDGE_CLEARANCE = 8 ,
  CT_HOLE_TO_HOLE = 9
}
 An abstract function object, returning a design rule (clearance, diff pair gap, etc) required between two items. More...
 
enum  ROUTER_MODE {
  PNS_MODE_ROUTE_SINGLE = 1 , PNS_MODE_ROUTE_DIFF_PAIR , PNS_MODE_TUNE_SINGLE , PNS_MODE_TUNE_DIFF_PAIR ,
  PNS_MODE_TUNE_DIFF_PAIR_SKEW
}
 
enum  DRAG_MODE {
  DM_CORNER = 0x1 , DM_SEGMENT = 0x2 , DM_VIA = 0x4 , DM_FREE_ANGLE = 0x8 ,
  DM_ARC = 0x10 , DM_ANY = 0x17 , DM_COMPONENT = 0x20
}
 
enum  PNS_MODE { RM_MarkObstacles = 0 , RM_Shove , RM_Walkaround }
 < Routing modes More...
 
enum  PNS_OPTIMIZATION_EFFORT { OE_LOW = 0 , OE_MEDIUM = 1 , OE_FULL = 2 }
 

Functions

static DIRECTION_45::AngleType angle (const VECTOR2I &a, const VECTOR2I &b)
 
static bool checkGap (const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap)
 
static VECTOR2I makeGapVector (VECTOR2I dir, int length)
 
bool commonParallelProjection (SEG p, SEG n, SEG &pClip, SEG &nClip)
 
OPT_VECTOR2I getDanglingAnchor (NODE *aNode, ITEM *aItem)
 
template<typename T , typename S >
std::unique_ptr< T > ItemCast (std::unique_ptr< S > aPtr)
 
template<typename T >
std::unique_ptr< typename std::remove_const< T >::type > Clone (const T &aItem)
 
bool operator== (JOINT::HASH_TAG const &aP1, JOINT::HASH_TAG const &aP2)
 
static int areNeighbours (int x, int y, int max=0)
 
SHAPE_LINE_CHAIN dragCornerInternal (const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP)
 
static void extendBox (BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
 
VECTOR2I closestProjectedPoint (const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
 
int findAmplitudeBinarySearch (MEANDER_SHAPE &aCopy, int targetLength, int minAmp, int maxAmp)
 
int findAmplitudeForLength (MEANDER_SHAPE *m, int targetLength, int minAmp, int maxAmp)
 
static bool pointInside2 (const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
 Determine if a point is located within a given polygon. More...
 
int findCoupledVertices (const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
 
bool verifyDpBypass (NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
 
bool coupledBypass (NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aRef, const SHAPE_LINE_CHAIN &aRefBypass, const SHAPE_LINE_CHAIN &aCoupled, SHAPE_LINE_CHAIN &aNewCoupled)
 
bool checkDpColliding (NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
 
static int64_t shovedArea (const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
 
bool tightenSegment (bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
 
void Tighten (NODE *aNode, const SHAPE_LINE_CHAIN &aOldLine, const LINE &aNewLine, LINE &aOptimized)
 
static VIAfindViaByHandle (NODE *aNode, const VIA_HANDLE &handle)
 
static const SHAPE_LINE_CHAIN buildHullForPrimitiveShape (const SHAPE *aShape, int aClearance, int aWalkaroundThickness)
 
const SHAPE_LINE_CHAIN OctagonalHull (const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
 
const SHAPE_LINE_CHAIN ArcHull (const SHAPE_ARC &aSeg, int aClearance, int aWalkaroundThickness)
 Various utility functions. More...
 
static bool IsSegment45Degree (const SEG &aS)
 
template<typename T >
int sgn (T val)
 
const SHAPE_LINE_CHAIN SegmentHull (const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
 
static void MoveDiagonal (SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
 
const SHAPE_LINE_CHAIN ConvexHull (const SHAPE_SIMPLE &aConvex, int aClearance)
 Function ConvexHull() More...
 
SHAPE_RECT ApproximateSegmentAsRect (const SHAPE_SEGMENT &aSeg)
 
OPT_BOX2I ChangedArea (const ITEM *aItemA, const ITEM *aItemB)
 
OPT_BOX2I ChangedArea (const LINE &aLineA, const LINE &aLineB)
 
void HullIntersection (const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
 

Variables

const int LENGTH_TARGET_TOLERANCE = 20
 
static ROUTERtheRouter
 
const int pnsSchemaVersion = 0
 
constexpr int HULL_MARGIN = 10
 

Detailed Description

Push and Shove diff pair dimensions (gap) settings dialog.

Push and Shove router settings dialog.

Enumeration Type Documentation

◆ CONSTRAINT_TYPE

enum class PNS::CONSTRAINT_TYPE
strong

An abstract function object, returning a design rule (clearance, diff pair gap, etc) required between two items.

Enumerator
CT_CLEARANCE 
CT_DIFF_PAIR_GAP 
CT_LENGTH 
CT_WIDTH 
CT_VIA_DIAMETER 
CT_VIA_HOLE 
CT_HOLE_CLEARANCE 
CT_EDGE_CLEARANCE 
CT_HOLE_TO_HOLE 

Definition at line 54 of file pns_node.h.

◆ DRAG_MODE

Enumerator
DM_CORNER 
DM_SEGMENT 
DM_VIA 
DM_FREE_ANGLE 
DM_ARC 
DM_ANY 
DM_COMPONENT 

Definition at line 70 of file pns_router.h.

71{
72 DM_CORNER = 0x1,
73 DM_SEGMENT = 0x2,
74 DM_VIA = 0x4,
75 DM_FREE_ANGLE = 0x8,
76 DM_ARC = 0x10,
77 DM_ANY = 0x17,
78 DM_COMPONENT = 0x20
79};
@ DM_CORNER
Definition: pns_router.h:72
@ DM_ANY
Definition: pns_router.h:77
@ DM_FREE_ANGLE
Definition: pns_router.h:75
@ DM_VIA
Definition: pns_router.h:74
@ DM_SEGMENT
Definition: pns_router.h:73
@ DM_ARC
Definition: pns_router.h:76
@ DM_COMPONENT
Definition: pns_router.h:78

◆ LineMarker

Enumerator
MK_HEAD 
MK_VIOLATION 
MK_LOCKED 
MK_DP_COUPLED 
MK_HOLE 

Definition at line 40 of file pns_item.h.

40 {
41 MK_HEAD = ( 1 << 0 ),
42 MK_VIOLATION = ( 1 << 3 ),
43 MK_LOCKED = ( 1 << 4 ),
44 MK_DP_COUPLED = ( 1 << 5 ),
45 MK_HOLE = ( 1 << 6 )
46};
@ MK_VIOLATION
Definition: pns_item.h:42
@ MK_DP_COUPLED
Definition: pns_item.h:44
@ MK_HEAD
Definition: pns_item.h:41
@ MK_LOCKED
Definition: pns_item.h:43
@ MK_HOLE
Definition: pns_item.h:45

◆ MEANDER_STYLE

Enumerator
MEANDER_STYLE_ROUND 
MEANDER_STYLE_CHAMFER 

Definition at line 50 of file pns_meander.h.

50 {
51 MEANDER_STYLE_ROUND = 1, // rounded (90 degree arc)
52 MEANDER_STYLE_CHAMFER // chamfered (45 degree segment)
53};
@ MEANDER_STYLE_ROUND
Definition: pns_meander.h:51
@ MEANDER_STYLE_CHAMFER
Definition: pns_meander.h:52

◆ MEANDER_TYPE

Shapes of available meanders.

Enumerator
MT_SINGLE 
MT_START 
MT_FINISH 
MT_TURN 
MT_CHECK_START 
MT_CHECK_FINISH 
MT_CORNER 
MT_ARC 
MT_EMPTY 

Definition at line 37 of file pns_meander.h.

37 {
38 MT_SINGLE, // _|^|_, single-sided
39 MT_START, // _|^|
40 MT_FINISH, // |^|_
41 MT_TURN, // |^| or |_|
42 MT_CHECK_START, // try fitting a start type, but don't produce a line
43 MT_CHECK_FINISH, // try fitting a finish type, but don't produce a line
44 MT_CORNER, // line corner
45 MT_ARC, // arc corner
46 MT_EMPTY // no meander (straight line)
47};
@ MT_ARC
Definition: pns_meander.h:45
@ MT_TURN
Definition: pns_meander.h:41
@ MT_CHECK_START
Definition: pns_meander.h:42
@ MT_CHECK_FINISH
Definition: pns_meander.h:43
@ MT_START
Definition: pns_meander.h:39
@ MT_FINISH
Definition: pns_meander.h:40
@ MT_EMPTY
Definition: pns_meander.h:46
@ MT_CORNER
Definition: pns_meander.h:44
@ MT_SINGLE
Definition: pns_meander.h:38

◆ PNS_MODE

< Routing modes

Enumerator
RM_MarkObstacles 

Ignore collisions, mark obstacles.

RM_Shove 

Only shove.

RM_Walkaround 

Only walk around.

Definition at line 39 of file pns_routing_settings.h.

40{
42 RM_Shove,
44};
@ RM_MarkObstacles
Ignore collisions, mark obstacles.
@ RM_Walkaround
Only walk around.
@ RM_Shove
Only shove.

◆ PNS_OPTIMIZATION_EFFORT

Enumerator
OE_LOW 
OE_MEDIUM 
OE_FULL 

Definition at line 47 of file pns_routing_settings.h.

48{
49 OE_LOW = 0,
50 OE_MEDIUM = 1,
51 OE_FULL = 2
52};

◆ ROUTER_MODE

Enumerator
PNS_MODE_ROUTE_SINGLE 
PNS_MODE_ROUTE_DIFF_PAIR 
PNS_MODE_TUNE_SINGLE 
PNS_MODE_TUNE_DIFF_PAIR 
PNS_MODE_TUNE_DIFF_PAIR_SKEW 

Definition at line 62 of file pns_router.h.

62 {
68};
@ PNS_MODE_ROUTE_SINGLE
Definition: pns_router.h:63
@ PNS_MODE_ROUTE_DIFF_PAIR
Definition: pns_router.h:64
@ PNS_MODE_TUNE_DIFF_PAIR
Definition: pns_router.h:66
@ PNS_MODE_TUNE_SINGLE
Definition: pns_router.h:65
@ PNS_MODE_TUNE_DIFF_PAIR_SKEW
Definition: pns_router.h:67

Function Documentation

◆ angle()

static DIRECTION_45::AngleType PNS::angle ( const VECTOR2I a,
const VECTOR2I b 
)
static

Definition at line 170 of file pns_diff_pair.cpp.

171{
172 DIRECTION_45 dir_a( a );
173 DIRECTION_45 dir_b( b );
174
175 return dir_a.Angle( dir_b );
176}
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37

References DIRECTION_45::Angle().

Referenced by DXF_IMPORT_PLUGIN::addArc(), SEG::Angle(), UNITS_PROVIDER::AngleValueFromString(), EC_CIRCLE::Apply(), CADSTAR_SCH_ARCHIVE_LOADER::applyTextSettings(), PNS_LOG_VIEWER_OVERLAY::Arc(), HPGL_PLOTTER::Arc(), GEOM_TEST::ArePerpendicular(), BuildCornersList_S_Shape(), PNS::DP_GATEWAYS::BuildGeneric(), CalcArcCenter(), PNS::OPTIMIZER::circleBreakouts(), SHAPE_ARC::ConstructFromStartEndCenter(), ConvertOutlineToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), CornerListToPolygon(), MICROWAVE_TOOL::createFootprint(), PNS::OPTIMIZER::customBreakouts(), KIGFX::PCB_PAINTER::draw(), drawCursorStrings(), DRAWING_TOOL::DrawDimension(), ROUTER_PREVIEW_ITEM::drawLineChain(), AR_MATRIX::drawSegmentQcq(), ROUTER_PREVIEW_ITEM::drawShape(), EDA_SHAPE_DESC::EDA_SHAPE_DESC(), GBR_TO_PCB_EXPORTER::export_non_copper_item(), CADSTAR_SCH_ARCHIVE_LOADER::fixUpLibraryPins(), DSN::SPECCTRA_DB::FromBOARD(), RENDER_3D_OPENGL::generateRing(), GERBER_DRAW_ITEM::GetBoundingBox(), FP_TEXT::GetBoundingBox(), SHAPE_ARC::GetEndAngle(), SCH_SCREEN::GetLabelOrientationForPoint(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetStartAngle(), SHAPE_ARC::GetStartAngle(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetSubtended(), KIFONT::OUTLINE_FONT::getTextAsGlyphs(), GERBER_DRAW_ITEM::GetTextD_CodePrms(), ARRAY_CIRCULAR_OPTIONS::GetTransform(), PG_UNIT_EDITOR::GetValueFromControl(), GRCSegm(), PNS::LINE_PLACER::handlePullback(), HelperShapeLineChainFromAltiumVertices(), idf_export_footprint(), DIALOG_PAD_PROPERTIES::initValues(), DXF_IMPORT_PLUGIN::insertArc(), isLine45Degree(), CADSTAR_PCB_ARCHIVE_LOADER::loadDimensions(), LEGACY_PLUGIN::loadFP_SHAPE(), LEGACY_PLUGIN::loadPCB_LINE(), LEGACY_PLUGIN::loadPCB_TEXT(), EAGLE_PLUGIN::loadPlain(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), DSN::SPECCTRA_DB::makeIMAGE(), EDIT_TOOL::MoveExact(), EAGLE_PLUGIN::packageCircle(), EAGLE_PLUGIN::packagePolygon(), SHAPE_LINE_CHAIN::Parse(), GPCB_FPL_CACHE::parseFOOTPRINT(), PCB_PARSER::parsePCB_SHAPE(), SCH_SEXPR_PARSER::parseSchSheetPin(), LIB_PIN::PlotPinTexts(), FABMASTER::processArc(), processLabel(), PCB_DIM_ORTHOGONAL::Rotate(), PCB_TEXTBOX::Rotate(), RotatePoint(), SCH_SEXPR_PLUGIN::saveSymbol(), SCH_SEXPR_PLUGIN::saveText(), EDA_SHAPE::SetArcAngleAndEnd(), FP_SHAPE::SetArcAngleAndEnd0(), SetTextPositioning(), EDA_SHAPE::ShapeGetMsgPanelInfo(), PNS::LINE_PLACER::Start(), AR_MATRIX::traceArc(), AR_MATRIX::traceCircle(), AR_MATRIX::TraceFilledRectangle(), DIALOG_CREATE_ARRAY::TransferDataFromWindow(), TransformCircleToPolygon(), TransformOvalToPolygon(), and FP_TEXT::ViewBBox().

◆ ApproximateSegmentAsRect()

SHAPE_RECT PNS::ApproximateSegmentAsRect ( const SHAPE_SEGMENT aSeg)

Definition at line 345 of file pns_utils.cpp.

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}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const SEG & GetSeg() const
int GetWidth() const
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
constexpr int delta

References SEG::A, std::abs(), SEG::B, delta, SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by PNS::OPTIMIZER::computeBreakouts().

◆ ArcHull()

const SHAPE_LINE_CHAIN PNS::ArcHull ( const SHAPE_ARC aSeg,
int  aClearance,
int  aWalkaroundThickness 
)

Various utility functions.

Definition at line 67 of file pns_utils.cpp.

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}
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.
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.
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

References SHAPE_LINE_CHAIN::Append(), SHAPE_ARC::ConvertToPolyline(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_ARC::DefaultAccuracyForPCB(), SHAPE_ARC::GetWidth(), VECTOR2< T >::Perpendicular(), VECTOR2< T >::Resize(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SetClosed(), and SEG::Side().

Referenced by buildHullForPrimitiveShape(), and PNS::ARC::Hull().

◆ areNeighbours()

static int PNS::areNeighbours ( int  x,
int  y,
int  max = 0 
)
static

Definition at line 156 of file pns_line.cpp.

157{
158 if( x > 0 && x - 1 == y )
159 return true;
160
161 if( x < max - 1 && x + 1 == y )
162 return true;
163
164 return false;
165}

Referenced by PNS::LINE::Walkaround().

◆ buildHullForPrimitiveShape()

static const SHAPE_LINE_CHAIN PNS::buildHullForPrimitiveShape ( const SHAPE aShape,
int  aClearance,
int  aWalkaroundThickness 
)
static

Definition at line 40 of file pns_solid.cpp.

42{
43 int cl = aClearance + ( aWalkaroundThickness + 1 )/ 2;
44
45 switch( aShape->Type() )
46 {
47 case SH_RECT:
48 {
49 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>( aShape );
50 return OctagonalHull( rect->GetPosition(),
51 rect->GetSize(),
52 cl,
53 0 );
54 }
55
56 case SH_CIRCLE:
57 {
58 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
59 int r = circle->GetRadius();
60 return OctagonalHull( circle->GetCenter() - VECTOR2I( r, r ),
61 VECTOR2I( 2 * r, 2 * r ),
62 cl,
63 2.0 * ( 1.0 - M_SQRT1_2 ) * ( r + cl ) );
64 }
65
66 case SH_SEGMENT:
67 {
68 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*>( aShape );
69 return SegmentHull( *seg, aClearance, aWalkaroundThickness );
70 }
71
72 case SH_ARC:
73 {
74 const SHAPE_ARC* arc = static_cast<const SHAPE_ARC*>( aShape );
75 return ArcHull( *arc, aClearance, aWalkaroundThickness );
76 }
77
78 case SH_SIMPLE:
79 {
80 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aShape );
81
82 return ConvexHull( *convex, cl );
83 }
84 default:
85 {
86 wxFAIL_MSG( wxString::Format( wxT( "Unsupported hull shape: %d (%s)." ),
87 aShape->Type(),
88 SHAPE_TYPE_asString( aShape->Type() ) ) );
89 break;
90 }
91 }
92
93 return SHAPE_LINE_CHAIN();
94}
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:95
int GetRadius() const
Definition: shape_circle.h:108
const VECTOR2I GetCenter() const
Definition: shape_circle.h:113
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:127
const VECTOR2I GetSize() const
Definition: shape_rect.h:135
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:42
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:36
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
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
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:44
@ SH_CIRCLE
circle
Definition: shape.h:47
@ SH_SIMPLE
simple polygon
Definition: shape.h:48
@ SH_SEGMENT
line segment
Definition: shape.h:45
@ SH_ARC
circular arc
Definition: shape.h:51
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:56
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References ArcHull(), ConvexHull(), Format(), SHAPE_CIRCLE::GetCenter(), SHAPE_RECT::GetPosition(), SHAPE_CIRCLE::GetRadius(), SHAPE_RECT::GetSize(), OctagonalHull(), SegmentHull(), SH_ARC, SH_CIRCLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, SHAPE_TYPE_asString(), and SHAPE_BASE::Type().

Referenced by PNS::SOLID::HoleHull(), and PNS::SOLID::Hull().

◆ ChangedArea() [1/2]

OPT_BOX2I PNS::ChangedArea ( const ITEM aItemA,
const ITEM aItemB 
)

Definition at line 358 of file pns_utils.cpp.

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}
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:850
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:140
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:200

References PNS::LINE::ChangedArea(), PNS::VIA::ChangedArea(), PNS::ITEM::LINE_T, PNS::ITEM::OfKind(), and PNS::ITEM::VIA_T.

Referenced by PNS::SHOVE::replaceItems(), and PNS::SHOVE::replaceLine().

◆ ChangedArea() [2/2]

OPT_BOX2I PNS::ChangedArea ( const LINE aLineA,
const LINE aLineB 
)

Definition at line 378 of file pns_utils.cpp.

379{
380 return aLineA.ChangedArea( &aLineB );
381}
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1152

References PNS::LINE::ChangedArea().

◆ checkDpColliding()

bool PNS::checkDpColliding ( NODE aNode,
DIFF_PAIR aPair,
bool  aIsP,
const SHAPE_LINE_CHAIN aPath 
)

Definition at line 1261 of file pns_optimizer.cpp.

1262{
1263 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1264
1265 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1266}
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:472

References PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::NLine(), and PNS::DIFF_PAIR::PLine().

◆ checkGap()

static bool PNS::checkGap ( const SHAPE_LINE_CHAIN p,
const SHAPE_LINE_CHAIN n,
int  gap 
)
static

Definition at line 179 of file pns_diff_pair.cpp.

180{
181 int i, j;
182
183 for( i = 0; i < p.SegmentCount(); i++ )
184 {
185 for( j = 0; j < n.SegmentCount() ; j++ )
186 {
187 int dist = p.CSegment( i ).Distance( n.CSegment( j ) );
188
189 if( dist < gap - 100 )
190 return false;
191 }
192 }
193
194 return true;
195}
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:319
int SegmentCount() const
Return the number of segments in this line chain.

References SHAPE_LINE_CHAIN::CSegment(), SEG::Distance(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by PNS::DIFF_PAIR::BuildInitial().

◆ Clone()

template<typename T >
std::unique_ptr< typename std::remove_const< T >::type > PNS::Clone ( const T &  aItem)

Definition at line 279 of file pns_item.h.

280{
281 static_assert( std::is_base_of<ITEM, T>::value, "Need to be handed an ITEM!" );
282 return std::unique_ptr<typename std::remove_const<T>::type>( aItem.Clone() );
283}

Referenced by PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::SHOVE::pushOrShoveVia(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::LINE_PLACER::SplitAdjacentSegments(), and PNS_KICAD_IFACE_BASE::syncPad().

◆ closestProjectedPoint()

VECTOR2I PNS::closestProjectedPoint ( const SHAPE_LINE_CHAIN line,
const VECTOR2I p 
)

Definition at line 395 of file pns_line_placer.cpp.

396{
397 // Keep distances squared for performance
398 SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
399 VECTOR2I closest;
400
401 for( int i = 0; i < line.SegmentCount(); i++ )
402 {
403 const SEG& s = line.CSegment( i );
404 VECTOR2I a = s.NearestPoint( p );
405 int d_sq = (a - p).SquaredEuclideanNorm();
406
407 if( d_sq < min_dist_sq )
408 {
409 min_dist_sq = d_sq;
410 closest = a;
411 }
412 }
413
414 return closest;
415}
Definition: seg.h:42
VECTOR2I::extended_type ecoord
Definition: seg.h:44
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:261
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79

References SHAPE_LINE_CHAIN::CSegment(), VECTOR2< int >::ECOORD_MAX, SEG::NearestPoint(), and SHAPE_LINE_CHAIN::SegmentCount().

◆ commonParallelProjection()

bool PNS::commonParallelProjection ( SEG  p,
SEG  n,
SEG pClip,
SEG nClip 
)

Definition at line 773 of file pns_diff_pair.cpp.

774{
775 SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
776
777 int64_t t_a = 0;
778 int64_t t_b = p.TCoef( p.B );
779
780 int64_t tproj_a = p.TCoef( n_proj_p.A );
781 int64_t tproj_b = p.TCoef( n_proj_p.B );
782
783 if( t_b < t_a )
784 std::swap( t_b, t_a );
785
786 if( tproj_b < tproj_a )
787 std::swap( tproj_b, tproj_a );
788
789 if( t_b <= tproj_a )
790 return false;
791
792 if( t_a >= tproj_b )
793 return false;
794
795 int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
796 std::vector<int64_t> tv( t, t + 4 );
797 std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
798
799 int64_t pLenSq = p.SquaredLength();
800
801 VECTOR2I dp = p.B - p.A;
802 pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
803 pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
804
805 pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
806 pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
807
808 nClip.A = n.LineProject( pClip.A );
809 nClip.B = n.LineProject( pClip.B );
810
811 return true;
812}
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:380
ecoord SquaredLength() const
Definition: seg.h:331
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:302
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:118

References SEG::A, SEG::B, SEG::LineProject(), rescale(), SEG::SquaredLength(), SEG::TCoef(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::DIFF_PAIR::CoupledLength(), and PNS::DIFF_PAIR::CoupledSegmentPairs().

◆ ConvexHull()

const SHAPE_LINE_CHAIN PNS::ConvexHull ( const SHAPE_SIMPLE aConvex,
int  aClearance 
)

Function ConvexHull()

Creates an octagonal hull around a convex polygon.

Parameters
aConvexThe convex polygon.
aClearanceThe minimum distance between polygon and hull.
Returns
A closed line chain describing the octagon.

Definition at line 289 of file pns_utils.cpp.

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}
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
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
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
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:278

References SHAPE_LINE_CHAIN::Append(), SHAPE_SIMPLE::BBox(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetOrigin(), BOX2< Vec >::GetSize(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), SEG::IntersectLines(), MoveDiagonal(), BOX2< Vec >::Normalize(), SHAPE_LINE_CHAIN::SetClosed(), and SHAPE_SIMPLE::Vertices().

Referenced by buildHullForPrimitiveShape().

◆ coupledBypass()

bool PNS::coupledBypass ( NODE aNode,
DIFF_PAIR aPair,
bool  aRefIsP,
const SHAPE_LINE_CHAIN aRef,
const SHAPE_LINE_CHAIN aRefBypass,
const SHAPE_LINE_CHAIN aCoupled,
SHAPE_LINE_CHAIN aNewCoupled 
)

Definition at line 1204 of file pns_optimizer.cpp.

1207{
1208 int vStartIdx[1024]; // fixme: possible overflow
1209 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1210 aRefBypass.CSegment( 0 ),
1211 aCoupled, aPair, vStartIdx );
1212 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1213
1214 int64_t bestLength = -1;
1215 bool found = false;
1216 SHAPE_LINE_CHAIN bestBypass;
1217 int si, ei;
1218
1219 for( int i=0; i< nStarts; i++ )
1220 {
1221 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1222 {
1223 int delta = std::abs ( vStartIdx[i] - j );
1224
1225 if( delta > 1 )
1226 {
1227 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1228 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1229 dir.IsDiagonal() );
1230
1231 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1232
1233 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1234
1235 si = vStartIdx[i];
1236 ei = j;
1237
1238 if(si < ei)
1239 newCoupled.Replace( si, ei, bypass );
1240 else
1241 newCoupled.Replace( ei, si, bypass.Reverse() );
1242
1243 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1244 newCoupled) )
1245 {
1246 bestBypass = newCoupled;
1247 bestLength = coupledLength;
1248 found = true;
1249 }
1250 }
1251 }
1252 }
1253
1254 if( found )
1255 aNewCoupled = bestBypass;
1256
1257 return found;
1258}
double CoupledLength() const
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)

References std::abs(), DIRECTION_45::BuildInitialTrace(), PNS::DIFF_PAIR::CoupledLength(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), delta, findCoupledVertices(), DIRECTION_45::IsDiagonal(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Replace(), SHAPE_LINE_CHAIN::Reverse(), and verifyDpBypass().

Referenced by PNS::OPTIMIZER::mergeDpStep().

◆ dragCornerInternal()

SHAPE_LINE_CHAIN PNS::dragCornerInternal ( const SHAPE_LINE_CHAIN aOrigin,
const VECTOR2I aP 
)

Definition at line 594 of file pns_line.cpp.

595{
596 std::optional<SHAPE_LINE_CHAIN> picked;
597 int i;
598 int d = 2;
599
600 wxASSERT( aOrigin.PointCount() > 0 );
601
602 if( aOrigin.PointCount() == 1 )
603 {
604 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
605 }
606 else if( aOrigin.SegmentCount() == 1 )
607 {
608 DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
609
610 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
611 }
612
613 if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
614 d = 1;
615
616 for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
617 {
618 DIRECTION_45 d_start( aOrigin.CSegment( i ) );
619 VECTOR2I p_start = aOrigin.CPoint( i );
620 SHAPE_LINE_CHAIN paths[2];
621 DIRECTION_45 dirs[2];
622 DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
623 int dirCount = 0;
624
625 for( int j = 0; j < 2; j++ )
626 {
627 paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
628
629 if( paths[j].SegmentCount() < 1 )
630 continue;
631
632 assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
633
634 dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
635 ++dirCount;
636 }
637
638 for( int j = 0; j < dirCount; j++ )
639 {
640 if( dirs[j] == d_start )
641 {
642 picked = paths[j];
643 break;
644 }
645 }
646
647 if( picked )
648 break;
649
650 for( int j = 0; j < dirCount; j++ )
651 {
652 if( dirs[j].IsObtuse( d_prev ) )
653 {
654 picked = paths[j];
655 break;
656 }
657 }
658
659 if( picked )
660 break;
661 }
662
663 if( picked )
664 {
665 SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
666 path.Append( *picked );
667
668 return path;
669 }
670
671 DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
672
673 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
674}
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
int Length() const
Return the length (this).
Definition: seg.h:326
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.

References DIRECTION_45::BuildInitialTrace(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), DIRECTION_45::IsDiagonal(), SEG::Length(), path, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SegmentCount(), and SHAPE_LINE_CHAIN::Slice().

Referenced by PNS::LINE::dragCorner45().

◆ extendBox()

static void PNS::extendBox ( BOX2I aBox,
bool &  aDefined,
const VECTOR2I aP 
)
static

Definition at line 1138 of file pns_line.cpp.

1139{
1140 if( aDefined )
1141 {
1142 aBox.Merge( aP );
1143 }
1144 else
1145 {
1146 aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1147 aDefined = true;
1148 }
1149}
BOX2< VECTOR2I > BOX2I
Definition: box2.h:847
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588

References BOX2< Vec >::Merge().

Referenced by PNS::LINE::ChangedArea().

◆ findAmplitudeBinarySearch()

int PNS::findAmplitudeBinarySearch ( MEANDER_SHAPE aCopy,
int  targetLength,
int  minAmp,
int  maxAmp 
)

Definition at line 136 of file pns_meander_placer_base.cpp.

137{
138 if( minAmp == maxAmp )
139 return maxAmp;
140
141 aCopy.Resize( minAmp );
142 int minLen = aCopy.CurrentLength();
143
144 aCopy.Resize( maxAmp );
145 int maxLen = aCopy.CurrentLength();
146
147 if( minLen > targetLength )
148 return 0;
149
150 if( maxLen < targetLength )
151 return 0;
152
153 int minError = minLen - targetLength;
154 int maxError = maxLen - targetLength;
155
156 if( std::abs( minError ) < LENGTH_TARGET_TOLERANCE
157 || std::abs( maxError ) < LENGTH_TARGET_TOLERANCE )
158 {
159 return std::abs( minError ) < std::abs( maxError ) ? minAmp : maxAmp;
160 }
161 else
162 {
163 int left =
164 findAmplitudeBinarySearch( aCopy, targetLength, minAmp, ( minAmp + maxAmp ) / 2 );
165
166 if( left )
167 return left;
168
169 int right =
170 findAmplitudeBinarySearch( aCopy, targetLength, ( minAmp + maxAmp ) / 2, maxAmp );
171
172 if( right )
173 return right;
174 }
175
176 return 0;
177}
long long int CurrentLength() const
void Resize(int aAmpl)
Change the amplitude of the meander shape to aAmpl and recalculates the resulting line chain.
const int LENGTH_TARGET_TOLERANCE
int findAmplitudeBinarySearch(MEANDER_SHAPE &aCopy, int targetLength, int minAmp, int maxAmp)

References std::abs(), PNS::MEANDER_SHAPE::CurrentLength(), findAmplitudeBinarySearch(), left, LENGTH_TARGET_TOLERANCE, PNS::MEANDER_SHAPE::Resize(), and right.

Referenced by findAmplitudeBinarySearch(), and findAmplitudeForLength().

◆ findAmplitudeForLength()

int PNS::findAmplitudeForLength ( MEANDER_SHAPE m,
int  targetLength,
int  minAmp,
int  maxAmp 
)

Definition at line 180 of file pns_meander_placer_base.cpp.

181{
182 MEANDER_SHAPE copy = *m;
183
184 // Try to keep the same baseline length
185 copy.SetTargetBaselineLength( m->BaselineLength() );
186
187 long long initialGuess = m->Amplitude() - ( m->CurrentLength() - targetLength ) / 2;
188
189 if( initialGuess >= minAmp && initialGuess <= maxAmp )
190 {
191 copy.Resize( minAmp );
192
193 if( std::abs( copy.CurrentLength() - targetLength ) < LENGTH_TARGET_TOLERANCE )
194 return initialGuess;
195 }
196
197 // The length is non-trivial, use binary search
198 return findAmplitudeBinarySearch( copy, targetLength, minAmp, maxAmp );
199}
The geometry of a single meander.
Definition: pns_meander.h:115
int Amplitude() const
Definition: pns_meander.h:174
int BaselineLength() const

References std::abs(), PNS::MEANDER_SHAPE::Amplitude(), PNS::MEANDER_SHAPE::BaselineLength(), copy, PNS::MEANDER_SHAPE::CurrentLength(), findAmplitudeBinarySearch(), and LENGTH_TARGET_TOLERANCE.

Referenced by PNS::MEANDER_PLACER_BASE::tuneLineLength().

◆ findCoupledVertices()

int PNS::findCoupledVertices ( const VECTOR2I aVertex,
const SEG aOrigSeg,
const SHAPE_LINE_CHAIN aCoupled,
DIFF_PAIR aPair,
int *  aIndices 
)

Definition at line 1158 of file pns_optimizer.cpp.

1160{
1161 int count = 0;
1162
1163 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1164 {
1165 SEG s = aCoupled.CSegment( i );
1166 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1167
1168 if( s.ApproxParallel( aOrigSeg ) )
1169 {
1170 int64_t dist =
1171 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1172
1173 if( aPair->GapConstraint().Matches( dist ) )
1174 {
1175 *aIndices++ = i;
1176 count++;
1177 }
1178 }
1179 }
1180
1181 return count;
1182}
int Width() const
const RANGED_NUM< int > GapConstraint() const
bool Matches(const T &aOther) const
Definition: ranged_num.h:43
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:393
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

References SEG::ApproxParallel(), SHAPE_LINE_CHAIN::CSegment(), EuclideanNorm(), PNS::DIFF_PAIR::GapConstraint(), SEG::LineProject(), RANGED_NUM< T >::Matches(), SHAPE_LINE_CHAIN::SegmentCount(), and PNS::DIFF_PAIR::Width().

Referenced by coupledBypass().

◆ findViaByHandle()

static VIA * PNS::findViaByHandle ( NODE aNode,
const VIA_HANDLE handle 
)
static

Definition at line 1754 of file pns_shove.cpp.

1755{
1756 JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1757
1758 if( !jt )
1759 return nullptr;
1760
1761 for( ITEM* item : jt->LinkList() )
1762 {
1763 if( item->OfKind( ITEM::VIA_T ) )
1764 {
1765 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1766 return static_cast<VIA*>( item );
1767 }
1768 }
1769
1770 return nullptr;
1771}
int Start() const
Definition: pns_layerset.h:82
Base class for PNS router board items.
Definition: pns_item.h:56
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:241
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1197
VECTOR2I pos
Definition: pns_via.h:44
LAYER_RANGE layers
Definition: pns_via.h:45

References PNS::NODE::FindJoint(), PNS::VIA_HANDLE::layers, PNS::JOINT::LinkList(), PNS::VIA_HANDLE::net, PNS::VIA_HANDLE::pos, LAYER_RANGE::Start(), and PNS::ITEM::VIA_T.

Referenced by PNS::SHOVE::ShoveDraggingVia().

◆ getDanglingAnchor()

OPT_VECTOR2I PNS::getDanglingAnchor ( NODE aNode,
ITEM aItem 
)

Definition at line 433 of file pns_diff_pair_placer.cpp.

434{
435 switch( aItem->Kind() )
436 {
437 case ITEM::VIA_T:
438 case ITEM::SOLID_T:
439 return aItem->Anchor( 0 );
440
441 case ITEM::ARC_T:
442 case ITEM::SEGMENT_T:
443 {
444 SEGMENT* s = static_cast<SEGMENT*>( aItem );
445
446 JOINT* jA = aNode->FindJoint( aItem->Anchor( 0 ), aItem );
447 JOINT* jB = aNode->FindJoint( aItem->Anchor( 1 ), aItem );
448
449 if( jA && jA->LinkCount() == 1 )
450 return s->Seg().A;
451 else if( jB && jB->LinkCount() == 1 )
452 return s->Seg().B;
453 else
454 return OPT_VECTOR2I();
455 }
456
457 default:
458 return OPT_VECTOR2I();
459 }
460}
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:132
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:219
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:256
const SEG & Seg() const
Definition: pns_segment.h:84
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39

References SEG::A, PNS::ITEM::Anchor(), PNS::ITEM::ARC_T, SEG::B, PNS::NODE::FindJoint(), PNS::ITEM::Kind(), PNS::JOINT::LinkCount(), PNS::SEGMENT::Seg(), PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

Referenced by PNS::DIFF_PAIR_PLACER::FindDpPrimitivePair().

◆ HullIntersection()

void PNS::HullIntersection ( const SHAPE_LINE_CHAIN hull,
const SHAPE_LINE_CHAIN line,
SHAPE_LINE_CHAIN::INTERSECTIONS ips 
)

Definition at line 384 of file pns_utils.cpp.

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}
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
Represent an intersection between two line segments.

References SEG::A, SEG::B, SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::Intersect(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SegmentCount(), and SHAPE_LINE_CHAIN::INTERSECTION::valid.

Referenced by PNS::NODE::NearestObstacle(), and PNS::LINE::Walkaround().

◆ IsSegment45Degree()

static bool PNS::IsSegment45Degree ( const SEG aS)
static

Definition at line 145 of file pns_utils.cpp.

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}

References SEG::A, std::abs(), SEG::B, delta, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SegmentHull().

◆ ItemCast()

template<typename T , typename S >
std::unique_ptr< T > PNS::ItemCast ( std::unique_ptr< S >  aPtr)

Definition at line 271 of file pns_item.h.

272{
273 static_assert( std::is_base_of<ITEM, S>::value, "Need to be handed a ITEM!" );
274 static_assert( std::is_base_of<ITEM, T>::value, "Need to cast to an ITEM!" );
275 return std::unique_ptr<T>( static_cast<T*>( aPtr.release() ) );
276}

◆ makeGapVector()

static VECTOR2I PNS::makeGapVector ( VECTOR2I  dir,
int  length 
)
static

Definition at line 408 of file pns_diff_pair.cpp.

409{
410 int l = length / 2;
411 VECTOR2I rv;
412
413 if( dir.EuclideanNorm() == 0 )
414 return dir;
415
416 do
417 {
418 rv = dir.Resize( l );
419 l++;
420 } while( ( rv * 2 ).EuclideanNorm() < length );
421
422 return rv;
423}
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293

References VECTOR2< T >::EuclideanNorm(), EuclideanNorm(), and VECTOR2< T >::Resize().

Referenced by PNS::DP_GATEWAYS::buildDpContinuation(), PNS::DP_GATEWAYS::BuildForCursor(), PNS::DP_GATEWAYS::BuildFromPrimitivePair(), and PNS::DP_GATEWAYS::BuildGeneric().

◆ MoveDiagonal()

static void PNS::MoveDiagonal ( SEG aDiagonal,
const SHAPE_LINE_CHAIN aVertices,
int  aClearance 
)
static

Definition at line 278 of file pns_utils.cpp.

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}
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.

References SEG::A, SEG::B, SHAPE_LINE_CHAIN::NearestPoint(), and VECTOR2< T >::Resize().

Referenced by ConvexHull().

◆ OctagonalHull()

const SHAPE_LINE_CHAIN PNS::OctagonalHull ( const VECTOR2I aP0,
const VECTOR2I aSize,
int  aClearance,
int  aChamfer 
)

Definition at line 36 of file pns_utils.cpp.

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}

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::SetClosed(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by buildHullForPrimitiveShape(), PNS::VIA::HoleHull(), PNS::VIA::Hull(), and SegmentHull().

◆ operator==()

bool PNS::operator== ( JOINT::HASH_TAG const &  aP1,
JOINT::HASH_TAG const &  aP2 
)
inline

Definition at line 311 of file pns_joint.h.

312{
313 return aP1.pos == aP2.pos && aP1.net == aP2.net;
314}

References PNS::JOINT::HASH_TAG::net, and PNS::JOINT::HASH_TAG::pos.

◆ pointInside2()

static bool PNS::pointInside2 ( const SHAPE_LINE_CHAIN aL,
const VECTOR2I aP 
)
static

Determine if a point is located within a given polygon.

Todo:
fixme: integrate into SHAPE_LINE_CHAIN, check corner cases against current PointInside implementation
Parameters
aLPolygon
aPPoint to check for location within the polygon
Returns
false if point is not polygon boundary aL, true if within or on the polygon boundary

Definition at line 298 of file pns_optimizer.cpp.

299{
300 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
301 return false;
302
303 int result = 0;
304 size_t cnt = aL.PointCount();
305
306 VECTOR2I ip = aL.CPoint( 0 );
307
308 for( size_t i = 1; i <= cnt; ++i )
309 {
310 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
311
312 if( ipNext.y == aP.y )
313 {
314 if( ( ipNext.x == aP.x )
315 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
316 return true; // pt on polyground boundary
317 }
318
319 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
320 {
321 if( ip.x >=aP.x )
322 {
323 if( ipNext.x >aP.x )
324 {
325 result = 1 - result;
326 }
327 else
328 {
329 double d = static_cast<double>( ip.x - aP.x ) *
330 static_cast<double>( ipNext.y - aP.y ) -
331 static_cast<double>( ipNext.x - aP.x ) *
332 static_cast<double>( ip.y - aP.y );
333
334 if( !d )
335 return true; // pt on polyground boundary
336
337 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
338 result = 1 - result;
339 }
340 }
341 else
342 {
343 if( ipNext.x >aP.x )
344 {
345 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
346 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
347
348 if( !d )
349 return true; // pt on polyground boundary
350
351 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
352 result = 1 - result;
353 }
354 }
355 }
356
357 ip = ipNext;
358 }
359
360 return result > 0;
361}
bool IsClosed() const override

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::IsClosed(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SegmentCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by PNS::KEEP_TOPOLOGY_CONSTRAINT::Check().

◆ SegmentHull()

const SHAPE_LINE_CHAIN PNS::SegmentHull ( const SHAPE_SEGMENT aSeg,
int  aClearance,
int  aWalkaroundThickness 
)

Definition at line 169 of file pns_utils.cpp.

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}
static bool IsSegment45Degree(const SEG &aS)
Definition: pns_utils.cpp:145
int sgn(T aVal)
Definition: seg.cpp:33
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

References SEG::A, std::abs(), SHAPE_LINE_CHAIN::Append(), SEG::B, SHAPE_LINE_CHAIN::CSegment(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), IsSegment45Degree(), KiROUND(), SEG::Length(), OctagonalHull(), VECTOR2< T >::Perpendicular(), VECTOR2< T >::Resize(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SetClosed(), sgn(), SEG::Side(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by buildHullForPrimitiveShape(), and PNS::SEGMENT::Hull().

◆ sgn()

template<typename T >
int PNS::sgn ( val)

Definition at line 164 of file pns_utils.cpp.

164 {
165 return (T(0) < val) - (val < T(0));
166}

Referenced by SegmentHull().

◆ shovedArea()

static int64_t PNS::shovedArea ( const SHAPE_LINE_CHAIN aOld,
const SHAPE_LINE_CHAIN aNew 
)
static

Definition at line 1379 of file pns_optimizer.cpp.

1380{
1381 int64_t area = 0;
1382 const int oc = aOld.PointCount();
1383 const int nc = aNew.PointCount();
1384 const int total = oc + nc;
1385
1386 for(int i = 0; i < total; i++)
1387 {
1388 int i_next = (i + 1 == total ? 0 : i + 1);
1389
1390 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1391 : aNew.CPoint( nc - 1 - (i - oc) );
1392 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1393 : aNew.CPoint( nc - 1 - (i_next - oc) );
1394 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1395 }
1396
1397 return std::abs( area / 2 );
1398}
T y
Definition: vector3.h:62
T x
Definition: vector3.h:61
VECTOR3I v1(5, 5, 5)

References std::abs(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), v1, VECTOR2< T >::x, VECTOR3< T >::x, VECTOR2< T >::y, and VECTOR3< T >::y.

Referenced by Tighten().

◆ Tighten()

void PNS::Tighten ( NODE aNode,
const SHAPE_LINE_CHAIN aOldLine,
const LINE aNewLine,
LINE aOptimized 
)

Definition at line 1502 of file pns_optimizer.cpp.

1504{
1505 LINE tmp;
1506
1507 if( aNewLine.SegmentCount() < 3 )
1508 return;
1509
1510 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1511
1512 for( int step = 0; step < 3; step++ )
1513 {
1514 current.Simplify();
1515
1516 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1517 {
1518 SHAPE_LINE_CHAIN l_in, l_out;
1519
1520 l_in = current.Slice( i, i + 3 );
1521
1522 for( int dir = 0; dir <= 1; dir++ )
1523 {
1524 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1525 {
1526 SHAPE_LINE_CHAIN opt = current;
1527 opt.Replace( i, i + 3, l_out );
1528 auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1529 auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1530
1531 if( optArea < prevArea )
1532 current = opt;
1533
1534 break;
1535 }
1536 }
1537 }
1538 }
1539
1540 aOptimized = LINE( aNewLine, current );
1541
1542 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1543 //dbg->AddLine ( current, 4, 100000 );
1544}
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:142
int SegmentCount() const
Definition: pns_line.h:144
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)

References std::abs(), PNS::LINE::CLine(), SHAPE_LINE_CHAIN::Replace(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SegmentCount(), shovedArea(), SHAPE_LINE_CHAIN::Simplify(), SHAPE_LINE_CHAIN::Slice(), and tightenSegment().

◆ tightenSegment()

bool PNS::tightenSegment ( bool  dir,
NODE aNode,
const LINE cur,
const SHAPE_LINE_CHAIN in,
SHAPE_LINE_CHAIN out 
)

Definition at line 1401 of file pns_optimizer.cpp.

1403{
1404 SEG a = in.CSegment(0);
1405 SEG center = in.CSegment(1);
1406 SEG b = in.CSegment(2);
1407
1408 DIRECTION_45 dirA ( a );
1409 DIRECTION_45 dirCenter ( center );
1410 DIRECTION_45 dirB ( b );
1411
1412 if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1413 return false;
1414
1415 //VECTOR2I perp = (center.B - center.A).Perpendicular();
1416 VECTOR2I guideA, guideB ;
1417
1418 SEG guide;
1419 int initial;
1420
1421 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1422 if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1423 return false;
1424
1425 {
1426 /*
1427 auto rC = *a.IntersectLines( b );
1428 dbg->AddSegment ( SEG( center.A, rC ), 1 );
1429 dbg->AddSegment ( SEG( center.B, rC ), 2 );
1430 auto perp = dirCenter.Left().Left();
1431
1432 SEG sperp ( center.A, center.A + perp.ToVector() );
1433
1434 auto vpc = sperp.LineProject( rC );
1435 auto vpa = sperp.LineProject( a.A );
1436 auto vpb = sperp.LineProject( b.B );
1437
1438 auto da = (vpc - vpa).EuclideanNorm();
1439 auto db = (vpc - vpb).EuclideanNorm();
1440
1441 auto vp = (da < db) ? vpa : vpb;
1442 dbg->AddSegment ( SEG( vpc, vp ), 5 );
1443
1444
1445 guide = SEG ( vpc, vp );
1446 */
1447 }
1448
1449 int da = a.Length();
1450 int db = b.Length();
1451
1452 if( da < db )
1453 guide = a;
1454 else
1455 guide = b;
1456
1457 initial = guide.Length();
1458
1459 int step = initial;
1460 int current = step;
1461 SHAPE_LINE_CHAIN snew;
1462
1463 while( step > 1 )
1464 {
1465 LINE l( cur );
1466
1467 snew.Clear();
1468 snew.Append( a.A );
1469 snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1470 snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1471 snew.Append( b.B );
1472
1473 step /= 2;
1474
1475 l.SetShape(snew);
1476
1477 if( aNode->CheckColliding(&l) )
1478 current -= step;
1479 else if ( current + step >= initial )
1480 current = initial;
1481 else
1482 current += step;
1483
1484 //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1485 //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1486 //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1487
1488 if ( current == initial )
1489 break;
1490
1491
1492 }
1493
1494 out = snew;
1495
1496 //dbg->AddLine ( snew, 3, 100000 );
1497
1498 return true;
1499}
void Clear()
Remove all points from the line chain.

References SEG::A, DIRECTION_45::ANG_RIGHT, DIRECTION_45::Angle(), SHAPE_LINE_CHAIN::Append(), SEG::B, PNS::NODE::CheckColliding(), SHAPE_LINE_CHAIN::Clear(), SHAPE_LINE_CHAIN::CSegment(), DIRECTION_45::IsObtuse(), SEG::Length(), VECTOR2< T >::Resize(), and PNS::LINE::SetShape().

Referenced by Tighten().

◆ verifyDpBypass()

bool PNS::verifyDpBypass ( NODE aNode,
DIFF_PAIR aPair,
bool  aRefIsP,
const SHAPE_LINE_CHAIN aNewRef,
const SHAPE_LINE_CHAIN aNewCoupled 
)

Definition at line 1185 of file pns_optimizer.cpp.

1187{
1188 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1189 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1190
1191 if( refLine.Collide( &coupledLine, aNode ) )
1192 return false;
1193
1194 if( aNode->CheckColliding ( &refLine ) )
1195 return false;
1196
1197 if( aNode->CheckColliding ( &coupledLine ) )
1198 return false;
1199
1200 return true;
1201}

References PNS::NODE::CheckColliding(), PNS::ITEM::Collide(), PNS::DIFF_PAIR::NLine(), and PNS::DIFF_PAIR::PLine().

Referenced by coupledBypass(), and PNS::OPTIMIZER::mergeDpStep().

Variable Documentation

◆ HULL_MARGIN

constexpr int PNS::HULL_MARGIN = 10
constexpr

Definition at line 34 of file pns_utils.h.

◆ LENGTH_TARGET_TOLERANCE

const int PNS::LENGTH_TARGET_TOLERANCE = 20

◆ pnsSchemaVersion

const int PNS::pnsSchemaVersion = 0

Definition at line 29 of file pns_routing_settings.cpp.

◆ theRouter