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)
 
static bool cursorDistMinimum (const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, int &theDist, VECTOR2I &aNearest)
 
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

SHAPE_LINE_CHAIN g_pnew
 
SHAPE_LINE_CHAIN g_hnew
 
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(), 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(), GERBER_DRAW_ITEM::GetTextD_CodePrms(), ARRAY_CIRCULAR_OPTIONS::GetTransform(), 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 340 of file pns_utils.cpp.

341{
343
344 VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
345 VECTOR2I p0( aSeg.GetSeg().A - delta );
346 VECTOR2I p1( aSeg.GetSeg().B + delta );
347
348 return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
349 std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
350}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const SEG & GetSeg() const
int GetWidth() const
E_SERIE r
Definition: eserie.cpp:41
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(), r, 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:461
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:284
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(), r, 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 353 of file pns_utils.cpp.

354{
355 if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
356 {
357 const VIA* va = static_cast<const VIA*>( aItemA );
358 const VIA* vb = static_cast<const VIA*>( aItemB );
359
360 return va->ChangedArea( vb );
361 }
362 else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
363 {
364 const LINE* la = static_cast<const LINE*> ( aItemA );
365 const LINE* lb = static_cast<const LINE*> ( aItemB );
366
367 return la->ChangedArea( lb );
368 }
369
370 return OPT_BOX2I();
371}
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:157

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 373 of file pns_utils.cpp.

374{
375 return aLineA.ChangedArea( &aLineB );
376}
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1136

References PNS::LINE::ChangedArea().

◆ checkDpColliding()

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

Definition at line 1252 of file pns_optimizer.cpp.

1253{
1254 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1255
1256 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1257}
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:468

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 277 of file pns_item.h.

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

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 417 of file pns_line_placer.cpp.

418{
419 // Keep distances squared for performance
420 SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
421 VECTOR2I closest;
422
423 for( int i = 0; i < line.SegmentCount(); i++ )
424 {
425 const SEG& s = line.CSegment( i );
426 VECTOR2I a = s.NearestPoint( p );
427 int d_sq = (a - p).SquaredEuclideanNorm();
428
429 if( d_sq < min_dist_sq )
430 {
431 min_dist_sq = d_sq;
432 closest = a;
433 }
434 }
435
436 return closest;
437}
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:403
ecoord SquaredLength() const
Definition: seg.h:356
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:105

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 284 of file pns_utils.cpp.

285{
286 // this defines the horizontal and vertical lines in the hull octagon
287 BOX2I box = aConvex.BBox( aClearance );
288 box.Normalize();
289
290 SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
291 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
292 SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
293 VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
294 SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
295 box.GetOrigin() );
296 SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
297
298 const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
299
300 // top right diagonal
301 VECTOR2I corner = box.GetOrigin() + box.GetSize();
302 SEG toprightline = SEG( corner,
303 corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
304 MoveDiagonal( toprightline, vertices, aClearance );
305
306 // bottom right diagonal
307 corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
308 SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
309 corner );
310 MoveDiagonal( bottomrightline, vertices, aClearance );
311
312 // bottom left diagonal
313 corner = box.GetOrigin();
314 SEG bottomleftline = SEG( corner,
315 corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
316 MoveDiagonal( bottomleftline, vertices, aClearance );
317
318 // top left diagonal
319 corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
320 SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
321 corner );
322 MoveDiagonal( topleftline, vertices, aClearance );
323
324 SHAPE_LINE_CHAIN octagon;
325 octagon.SetClosed( true );
326
327 octagon.Append( *leftline.IntersectLines( bottomleftline ) );
328 octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
329 octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
330 octagon.Append( *rightline.IntersectLines( bottomrightline ) );
331 octagon.Append( *rightline.IntersectLines( toprightline ) );
332 octagon.Append( *topline.IntersectLines( toprightline ) );
333 octagon.Append( *topline.IntersectLines( topleftline ) );
334 octagon.Append( *leftline.IntersectLines( topleftline ) );
335
336 return octagon;
337}
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:273

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 1195 of file pns_optimizer.cpp.

1198{
1199 int vStartIdx[1024]; // fixme: possible overflow
1200 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1201 aRefBypass.CSegment( 0 ),
1202 aCoupled, aPair, vStartIdx );
1203 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1204
1205 int64_t bestLength = -1;
1206 bool found = false;
1207 SHAPE_LINE_CHAIN bestBypass;
1208 int si, ei;
1209
1210 for( int i=0; i< nStarts; i++ )
1211 {
1212 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1213 {
1214 int delta = std::abs ( vStartIdx[i] - j );
1215
1216 if( delta > 1 )
1217 {
1218 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1219 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1220 dir.IsDiagonal() );
1221
1222 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1223
1224 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1225
1226 si = vStartIdx[i];
1227 ei = j;
1228
1229 if(si < ei)
1230 newCoupled.Replace( si, ei, bypass );
1231 else
1232 newCoupled.Replace( ei, si, bypass.Reverse() );
1233
1234 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1235 newCoupled) )
1236 {
1237 bestBypass = newCoupled;
1238 bestLength = coupledLength;
1239 found = true;
1240 }
1241 }
1242 }
1243 }
1244
1245 if( found )
1246 aNewCoupled = bestBypass;
1247
1248 return found;
1249}
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().

◆ cursorDistMinimum()

static bool PNS::cursorDistMinimum ( const SHAPE_LINE_CHAIN aL,
const VECTOR2I aCursor,
double  lengthThreshold,
int &  theDist,
VECTOR2I aNearest 
)
static

Definition at line 440 of file pns_line_placer.cpp.

441{
442 std::vector<int> dists;
443 std::vector<VECTOR2I> pts;
444
445 if( aL.PointCount() == 0 )
446 return false;
447
448 VECTOR2I lastP = aL.CPoint(-1);
449 int accumulatedDist = 0;
450
451 dists.reserve( 2 * aL.PointCount() );
452
453 for( int i = 0; i < aL.SegmentCount(); i++ )
454 {
455 const SEG& s = aL.CSegment( i );
456
457 dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
458 pts.push_back( s.A );
459 auto pn = s.NearestPoint( aCursor );
460
461 if( pn != s.A && pn != s.B )
462 {
463 dists.push_back( ( pn - aCursor ).EuclideanNorm() );
464 pts.push_back( pn );
465 }
466
467 accumulatedDist += s.Length();
468
469 if ( accumulatedDist > lengthThreshold )
470 {
471 lastP = s.B;
472 break;
473 }
474 }
475
476 dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
477 pts.push_back( lastP );
478
479 int minDistLoc = std::numeric_limits<int>::max();
480 int minPLoc = -1;
481 int minDistGlob = std::numeric_limits<int>::max();
482 int minPGlob = -1;
483
484 for( int i = 0; i < dists.size(); i++ )
485 {
486 int d = dists[i];
487
488 if( d < minDistGlob )
489 {
490 minDistGlob = d;
491 minPGlob = i;
492 }
493 }
494
495 if( dists.size() >= 3 )
496 {
497 for( int i = 0; i < dists.size() - 3; i++ )
498 {
499 if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
500 {
501 int d = dists[i + 1];
502 if( d < minDistLoc )
503 {
504 minDistLoc = d;
505 minPLoc = i + 1;
506 }
507 }
508 }
509
510 if( dists.back() < minDistLoc && minPLoc >= 0 )
511 {
512 minDistLoc = dists.back();
513 minPLoc = dists.size() - 1;
514 }
515 }
516 else
517 {
518 // Too few points: just use the global
519 minDistLoc = minDistGlob;
520 minPLoc = minPGlob;
521 }
522
523// fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
524// in the code, enabling the global one by default
525 minPLoc = -1;
526
527 if( minPLoc < 0 )
528 {
529 theDist = minDistGlob;
530 aNearest = pts[minPGlob];
531 return true;
532 }
533 else
534 {
535 theDist = minDistLoc;
536 aNearest = pts[minPLoc];
537 return true;
538 }
539}
int Length() const
Return the length (this).
Definition: seg.h:351
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

References SEG::A, SEG::B, SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), EuclideanNorm(), SEG::Length(), SEG::NearestPoint(), SHAPE_LINE_CHAIN::PointCount(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by PNS::LINE_PLACER::rhWalkOnly().

◆ dragCornerInternal()

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

Definition at line 579 of file pns_line.cpp.

580{
581 std::optional<SHAPE_LINE_CHAIN> picked;
582 int i;
583 int d = 2;
584
585 wxASSERT( aOrigin.PointCount() > 0 );
586
587 if( aOrigin.PointCount() == 1 )
588 {
589 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
590 }
591 else if( aOrigin.SegmentCount() == 1 )
592 {
593 DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
594
595 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
596 }
597
598 if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
599 d = 1;
600
601 for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
602 {
603 DIRECTION_45 d_start( aOrigin.CSegment( i ) );
604 VECTOR2I p_start = aOrigin.CPoint( i );
605 SHAPE_LINE_CHAIN paths[2];
606 DIRECTION_45 dirs[2];
607 DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
608 int dirCount = 0;
609
610 for( int j = 0; j < 2; j++ )
611 {
612 paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
613
614 if( paths[j].SegmentCount() < 1 )
615 continue;
616
617 assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
618
619 dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
620 ++dirCount;
621 }
622
623 for( int j = 0; j < dirCount; j++ )
624 {
625 if( dirs[j] == d_start )
626 {
627 picked = paths[j];
628 break;
629 }
630 }
631
632 if( picked )
633 break;
634
635 for( int j = 0; j < dirCount; j++ )
636 {
637 if( dirs[j].IsObtuse( d_prev ) )
638 {
639 picked = paths[j];
640 break;
641 }
642 }
643
644 if( picked )
645 break;
646 }
647
648 if( picked )
649 {
650 SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
651 path.Append( *picked );
652
653 return path;
654 }
655
656 DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
657
658 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
659}
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.
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 1122 of file pns_line.cpp.

1123{
1124 if( aDefined )
1125 {
1126 aBox.Merge( aP );
1127 }
1128 else
1129 {
1130 aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1131 aDefined = true;
1132 }
1133}
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().

◆ findCoupledVertices()

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

Definition at line 1149 of file pns_optimizer.cpp.

1151{
1152 int count = 0;
1153
1154 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1155 {
1156 SEG s = aCoupled.CSegment( i );
1157 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1158
1159 if( s.ApproxParallel( aOrigSeg ) )
1160 {
1161 int64_t dist =
1162 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1163
1164 if( aPair->GapConstraint().Matches( dist ) )
1165 {
1166 *aIndices++ = i;
1167 count++;
1168 }
1169 }
1170 }
1171
1172 return count;
1173}
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.h:291

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 1750 of file pns_shove.cpp.

1751{
1752 JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1753
1754 if( !jt )
1755 return nullptr;
1756
1757 for( ITEM* item : jt->LinkList() )
1758 {
1759 if( item->OfKind( ITEM::VIA_T ) )
1760 {
1761 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1762 return static_cast<VIA*>( item );
1763 }
1764 }
1765
1766 return nullptr;
1767}
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:1181
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 379 of file pns_utils.cpp.

381{
383
384 if( line.PointCount() < 2 )
385 return;
386
387 hull.Intersect( line, ips_raw );
388
389 for( auto& p : ips_raw )
390 {
392
393 SEG d1[2];
394 VECTOR2I d2[2];
395 int d1_idx = 0, d2_idx = 0;
396
397 ipp = p;
398 ipp.valid = false;
399
400 if( !p.is_corner_our && !p.is_corner_their )
401 {
402 ipp.valid = true;
403 ips.push_back( ipp );
404 continue;
405 }
406
407 if( p.index_our >= hull.SegmentCount() )
408 p.index_our -= hull.SegmentCount();
409
410 if( p.is_corner_our )
411 {
412 d1[0] = hull.CSegment( p.index_our );
413 d1[1] = hull.CSegment( p.index_our - 1 );
414 d1_idx = 2;
415 }
416 else
417 {
418 d1[0] = hull.CSegment( p.index_our );
419 d1_idx = 1;
420 }
421
422 if( p.is_corner_their )
423 {
424 if( p.index_their > 0 )
425 {
426 d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
427 }
428 if( p.index_their < line.PointCount() - 1 )
429 {
430 d2[d2_idx++] = line.CSegment( p.index_their ).B;
431 }
432 }
433 else
434 {
435 d2[d2_idx++] = line.CSegment( p.index_their ).A;
436 d2[d2_idx++] = line.CSegment( p.index_their ).B;
437 }
438
439 for( int i = 0; i < d1_idx; i++ )
440 {
441 for( int j = 0; j < d2_idx; j++ )
442 {
443 if( d1[i].Side( d2[j] ) > 0 )
444 {
445 ipp.valid = true;
446 }
447 }
448 }
449
450#ifdef TOM_EXTRA_DEBUG
451 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);
452 printf("d1 %d d2 %d\n", d1_idx, d2_idx );
453#endif
454 if( ipp.valid )
455 {
456 ips.push_back( ipp );
457 }
458 }
459}
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 269 of file pns_item.h.

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

◆ 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 273 of file pns_utils.cpp.

274{
275 int dist;
276
277 aVertices.NearestPoint( aDiagonal, dist );
278 VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
279 aDiagonal.A += moveBy;
280 aDiagonal.B += moveBy;
281}
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 295 of file pns_optimizer.cpp.

296{
297 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
298 return false;
299
300 int result = 0;
301 size_t cnt = aL.PointCount();
302
303 VECTOR2I ip = aL.CPoint( 0 );
304
305 for( size_t i = 1; i <= cnt; ++i )
306 {
307 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
308
309 if( ipNext.y == aP.y )
310 {
311 if( ( ipNext.x == aP.x )
312 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
313 return true; // pt on polyground boundary
314 }
315
316 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
317 {
318 if( ip.x >=aP.x )
319 {
320 if( ipNext.x >aP.x )
321 {
322 result = 1 - result;
323 }
324 else
325 {
326 double d = static_cast<double>( ip.x - aP.x ) *
327 static_cast<double>( ipNext.y - aP.y ) -
328 static_cast<double>( ipNext.x - aP.x ) *
329 static_cast<double>( ip.y - aP.y );
330
331 if( !d )
332 return true; // pt on polyground boundary
333
334 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
335 result = 1 - result;
336 }
337 }
338 else
339 {
340 if( ipNext.x >aP.x )
341 {
342 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
343 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
344
345 if( !d )
346 return true; // pt on polyground boundary
347
348 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
349 result = 1 - result;
350 }
351 }
352 }
353
354 ip = ipNext;
355 }
356
357 return result > 0;
358}
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 ( !IsSegment45Degree( aSeg.GetSeg() ) )
197 {
198 if ( len <= kinkThreshold && len > 0 )
199 {
200 int ll = std::max( std::abs( w ), std::abs( h ) );
201
202 b = a + VECTOR2I( sgn( w ) * ll, sgn( h ) * ll );
203 }
204 }
205 else
206 {
207 if( len <= kinkThreshold )
208 {
209 int delta45 = std::abs( std::abs(w) - std::abs(h) );
210 if( std::abs(w) <= 1 ) // almost vertical
211 {
212 w = 0;
213 cl ++;
214 }
215 else if ( std::abs(h) <= 1 ) // almost horizontal
216 {
217 h = 0;
218 cl ++;
219 }
220 else if ( delta45 <= 2 ) // almost 45 degree
221 {
222 int newW = sgn( w ) * std::max( std::abs(w), std::abs( h ) );
223 int newH = sgn( h ) * std::max( std::abs(w), std::abs( h ) );
224 w = newW;
225 h = newH;
226 cl += 2;
227 //PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "almostkinky45 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
228
229 }
230
231 b.x = a.x + w;
232 b.y = a.y + h;
233 }
234 }
235
236 if( a == b )
237 {
238 int xx2 = KiROUND( 2.0 * ( 1.0 - M_SQRT2 ) * d );
239
240 return OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
241 VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
242 cl,
243 xx2 );
244 }
245
246 VECTOR2I dir = b - a;
247 VECTOR2I p0 = dir.Perpendicular().Resize( dr );
248 VECTOR2I ds = dir.Perpendicular().Resize( xr2 );
249 VECTOR2I pd = dir.Resize( xr2 );
250 VECTOR2I dp = dir.Resize( dr );
251
253
254 s.SetClosed( true );
255
256 s.Append( b + p0 + pd );
257 s.Append( b + dp + ds );
258 s.Append( b + dp - ds );
259 s.Append( b - p0 + pd );
260 s.Append( a - p0 - pd );
261 s.Append( a - dp - ds );
262 s.Append( a - dp + ds );
263 s.Append( a + p0 - pd );
264
265 // make sure the hull outline is always clockwise
266 if( s.CSegment( 0 ).Side( a ) < 0 )
267 return s.Reverse();
268 else
269 return s;
270}
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:80

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 1370 of file pns_optimizer.cpp.

1371{
1372 int64_t area = 0;
1373 const int oc = aOld.PointCount();
1374 const int nc = aNew.PointCount();
1375 const int total = oc + nc;
1376
1377 for(int i = 0; i < total; i++)
1378 {
1379 int i_next = (i + 1 == total ? 0 : i + 1);
1380
1381 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1382 : aNew.CPoint( nc - 1 - (i - oc) );
1383 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1384 : aNew.CPoint( nc - 1 - (i_next - oc) );
1385 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1386 }
1387
1388 return std::abs( area / 2 );
1389}

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

Referenced by Tighten().

◆ Tighten()

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

Definition at line 1493 of file pns_optimizer.cpp.

1495{
1496 LINE tmp;
1497
1498 if( aNewLine.SegmentCount() < 3 )
1499 return;
1500
1501 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1502
1503 for( int step = 0; step < 3; step++ )
1504 {
1505 current.Simplify();
1506
1507 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1508 {
1509 SHAPE_LINE_CHAIN l_in, l_out;
1510
1511 l_in = current.Slice( i, i + 3 );
1512
1513 for( int dir = 0; dir <= 1; dir++ )
1514 {
1515 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1516 {
1517 SHAPE_LINE_CHAIN opt = current;
1518 opt.Replace( i, i + 3, l_out );
1519 auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1520 auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1521
1522 if( optArea < prevArea )
1523 current = opt;
1524
1525 break;
1526 }
1527 }
1528 }
1529 }
1530
1531 aOptimized = LINE( aNewLine, current );
1532
1533 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1534 //dbg->AddLine ( current, 4, 100000 );
1535}
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
int SegmentCount() const
Definition: pns_line.h:139
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 1392 of file pns_optimizer.cpp.

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

1178{
1179 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1180 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1181
1182 if( refLine.Collide( &coupledLine, aNode ) )
1183 return false;
1184
1185 if( aNode->CheckColliding ( &refLine ) )
1186 return false;
1187
1188 if( aNode->CheckColliding ( &coupledLine ) )
1189 return false;
1190
1191 return true;
1192}

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

◆ g_hnew

SHAPE_LINE_CHAIN PNS::g_hnew

Definition at line 169 of file pns_line.cpp.

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

◆ g_pnew

SHAPE_LINE_CHAIN PNS::g_pnew

Definition at line 169 of file pns_line.cpp.

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

◆ HULL_MARGIN

constexpr int PNS::HULL_MARGIN = 10
constexpr

Definition at line 34 of file pns_utils.h.

◆ pnsSchemaVersion

const int PNS::pnsSchemaVersion = 0

Definition at line 29 of file pns_routing_settings.cpp.

◆ theRouter