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  CONSTRAINT_TYPE {
  CONSTRAINT_TYPE::CT_CLEARANCE = 1, CONSTRAINT_TYPE::CT_DIFF_PAIR_GAP = 2, CONSTRAINT_TYPE::CT_LENGTH = 3, CONSTRAINT_TYPE::CT_WIDTH = 4,
  CONSTRAINT_TYPE::CT_VIA_DIAMETER = 5, CONSTRAINT_TYPE::CT_VIA_HOLE = 6, CONSTRAINT_TYPE::CT_HOLE_CLEARANCE = 7, CONSTRAINT_TYPE::CT_EDGE_CLEARANCE = 8,
  CONSTRAINT_TYPE::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...
 
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 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 };

◆ 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 };

◆ 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_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 };

◆ 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 {
41  RM_MarkObstacles = 0,
42  RM_Shove,
44 };
Ignore collisions, mark obstacles.
Only walk around.

◆ PNS_OPTIMIZATION_EFFORT

Enumerator
OE_LOW 
OE_MEDIUM 
OE_FULL 

Definition at line 47 of file pns_routing_settings.h.

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

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:36

References DIRECTION_45::Angle().

Referenced by DXF_IMPORT_PLUGIN::addArc(), EC_CIRCLE::Apply(), PNS_LOG_VIEWER_OVERLAY::Arc(), HPGL_PLOTTER::Arc(), GEOM_TEST::ArePerpendicular(), BuildCornersList_S_Shape(), PNS::DP_GATEWAYS::BuildGeneric(), CalcArcAngle(), PNS::OPTIMIZER::circleBreakouts(), EDA_SHAPE::computeArcBBox(), SHAPE_ARC::ConstructFromStartEndCenter(), ConvertOutlineToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), MICROWAVE_TOOL::createFootprint(), SCH_GLOBALLABEL::CreateGraphicShape(), PNS::OPTIMIZER::customBreakouts(), KIGFX::PCB_PAINTER::draw(), DRAWING_TOOL::DrawDimension(), ROUTER_PREVIEW_ITEM::drawLineChain(), AR_MATRIX::drawSegmentQcq(), ROUTER_PREVIEW_ITEM::drawShape(), GBR_TO_PCB_EXPORTER::export_non_copper_item(), DSN::SPECCTRA_DB::FromBOARD(), RENDER_3D_OPENGL::generateRing(), FP_TEXT::GetBoundingBox(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetStartAngle(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetSubtended(), ARRAY_CIRCULAR_OPTIONS::GetTransform(), GRCSegm(), PNS::LINE_PLACER::handlePullback(), HelperShapeLineChainFromAltiumVertices(), idf_export_footprint(), DIALOG_PAD_PROPERTIES::initValues(), DXF_IMPORT_PLUGIN::insertArc(), PNS::LINE::Is45Degree(), 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(), EAGLE_PLUGIN::packageCircle(), EAGLE_PLUGIN::packagePolygon(), SHAPE_LINE_CHAIN::Parse(), ALTIUM_PCB::ParseArcs6Data(), GPCB_FPL_CACHE::parseFOOTPRINT(), PCB_PARSER::parsePCB_SHAPE(), SCH_SEXPR_PARSER::parseSchSheetPin(), FABMASTER::processArc(), processLabel(), AR_AUTOPLACER::rotateFootprint(), RotatePoint(), SCH_SEXPR_PLUGIN::saveSymbol(), SCH_SEXPR_PLUGIN::saveText(), FP_TEXT::SetDrawCoord(), PAD::SetDrawCoord(), FP_SHAPE::SetLocalCoord(), FP_TEXT::SetLocalCoord(), SetTextPositioning(), PNS::LINE_PLACER::Start(), AR_MATRIX::traceArc(), AR_MATRIX::traceCircle(), AR_MATRIX::TraceFilledRectangle(), TransformCircleToPolygon(), TransformOvalToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and FP_TEXT::ViewBBox().

◆ ApproximateSegmentAsRect()

SHAPE_RECT PNS::ApproximateSegmentAsRect ( const SHAPE_SEGMENT aSeg)

Definition at line 236 of file pns_utils.cpp.

237 {
238  SHAPE_RECT r;
239 
240  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
241  VECTOR2I p0( aSeg.GetSeg().A - delta );
242  VECTOR2I p1( aSeg.GetSeg().B + delta );
243 
244  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
245  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
246 }
const SEG & GetSeg() const
E_SERIE r
Definition: eserie.cpp:41
VECTOR2I A
Definition: seg.h:48
constexpr int delta
int GetWidth() const
VECTOR2I B
Definition: seg.h:49

References SEG::A, SEG::B, delta, SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), and r.

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

68 {
69  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
70  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
71 
72  auto line = aSeg.ConvertToPolyline();
73 
75  s.SetClosed( true );
76  std::vector<VECTOR2I> reverse_line;
77 
78  auto seg = line.Segment( 0 );
79  VECTOR2I dir = seg.B - seg.A;
80  VECTOR2I p0 = dir.Perpendicular().Resize( d );
81  VECTOR2I ds = dir.Perpendicular().Resize( x );
82  VECTOR2I pd = dir.Resize( x );
83  VECTOR2I dp = dir.Resize( d );
84 
85  // Append the first curve
86  s.Append( seg.A + p0 - pd );
87  s.Append( seg.A - dp + ds );
88  s.Append( seg.A - dp - ds );
89  s.Append( seg.A - p0 - pd );
90 
91  for( int i = 1; i < line.SegmentCount(); i++ )
92  {
93  auto old_seg = seg;
94  auto endpt = ( old_seg.A - old_seg.B ).Resize( seg.Length() );
95  old_seg.A = old_seg.B + endpt;
96 
97  seg = line.Segment( i );
98  auto dir2 = old_seg.A - seg.B;
99 
100  p0 = dir2.Perpendicular().Resize( d );
101  s.Append( seg.A - p0 );
102  reverse_line.push_back( seg.A + p0 );
103  }
104 
105  pd = dir.Resize( x );
106  dp = dir.Resize( d );
107  s.Append( seg.B - p0 + pd );
108  s.Append( seg.B + dp - ds );
109  s.Append( seg.B + dp + ds );
110  s.Append( seg.B + p0 + pd );
111 
112  for( int i = reverse_line.size() - 1; i >= 0; i-- )
113  s.Append( reverse_line[i] );
114 
115  // make sure the hull outline is always clockwise
116  if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
117  return s.Reverse();
118  else
119  return s;
120 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
int GetWidth() const
Definition: shape_arc.h:156
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:458
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142

References SHAPE_LINE_CHAIN::Append(), SHAPE_ARC::ConvertToPolyline(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_ARC::GetWidth(), HULL_MARGIN, 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 + 1,
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 + 1,
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( "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 }
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:180
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:41
int GetRadius() const
Definition: shape_circle.h:107
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:123
const VECTOR2I GetSize() const
Definition: shape_rect.h:124
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:116
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:55
circular arc
Definition: shape.h:50
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:35
E_SERIE r
Definition: eserie.cpp:41
circle
Definition: shape.h:46
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
const SHAPE_LINE_CHAIN ArcHull(const SHAPE_ARC &aSeg, int aClearance, int aWalkaroundThickness)
Various utility functions.
Definition: pns_utils.cpp:66
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
axis-aligned rectangle
Definition: shape.h:43
simple polygon
Definition: shape.h:47
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
line segment
Definition: shape.h:44

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

250 {
251  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
252  {
253  const VIA* va = static_cast<const VIA*>( aItemA );
254  const VIA* vb = static_cast<const VIA*>( aItemB );
255 
256  return va->ChangedArea( vb );
257  }
258  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
259  {
260  const LINE* la = static_cast<const LINE*> ( aItemA );
261  const LINE* lb = static_cast<const LINE*> ( aItemB );
262 
263  return la->ChangedArea( lb );
264  }
265 
266  return OPT_BOX2I();
267 }
Normal via.
Definition: router_tool.cpp:72
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509

References PNS::VIA::ChangedArea(), PNS::LINE::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 269 of file pns_utils.cpp.

270 {
271  return aLineA.ChangedArea( &aLineB );
272 }

References PNS::LINE::ChangedArea().

◆ checkDpColliding()

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

Definition at line 1245 of file pns_optimizer.cpp.

1246 {
1247  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1248 
1249  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1250 }

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:285
int SegmentCount() const
Return the number of segments in this line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.

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

272 {
273  static_assert( std::is_base_of<ITEM, T>::value, "Need to be handed an ITEM!" );
274  return std::unique_ptr<typename std::remove_const<T>::type>( aItem.Clone() );
275 }

Referenced by PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::SHOVE::pushOrShoveVia(), DIALOG_PAD_PROPERTIES::redraw(), 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 401 of file pns_line_placer.cpp.

402 {
403  // Keep distances squared for performance
404  SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
405  VECTOR2I closest;
406 
407  for( int i = 0; i < line.SegmentCount(); i++ )
408  {
409  const SEG& s = line.CSegment( i );
410  VECTOR2I a = s.NearestPoint( p );
411  int d_sq = (a - p).SquaredEuclideanNorm();
412 
413  if( d_sq < min_dist_sq )
414  {
415  min_dist_sq = d_sq;
416  closest = a;
417  }
418  }
419 
420  return closest;
421 }
VECTOR2I::extended_type ecoord
Definition: seg.h:43
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.

References SHAPE_LINE_CHAIN::CSegment(), VECTOR2< T >::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 SquaredLength() const
Definition: seg.h:355
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:268
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:402
Definition: seg.h:40
VECTOR2I A
Definition: seg.h:48
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
VECTOR2I B
Definition: seg.h:49

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

181 {
182  // this defines the horizontal and vertical lines in the hull octagon
183  BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
184  box.Normalize();
185 
186  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
187  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
188  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
189  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
190  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
191  box.GetOrigin() );
192  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
193 
194  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
195 
196  // top right diagonal
197  VECTOR2I corner = box.GetOrigin() + box.GetSize();
198  SEG toprightline = SEG( corner,
199  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
200  MoveDiagonal( toprightline, vertices, aClearance );
201 
202  // bottom right diagonal
203  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
204  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
205  corner );
206  MoveDiagonal( bottomrightline, vertices, aClearance );
207 
208  // bottom left diagonal
209  corner = box.GetOrigin();
210  SEG bottomleftline = SEG( corner,
211  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
212  MoveDiagonal( bottomleftline, vertices, aClearance );
213 
214  // top left diagonal
215  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
216  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
217  corner );
218  MoveDiagonal( topleftline, vertices, aClearance );
219 
220  SHAPE_LINE_CHAIN octagon;
221  octagon.SetClosed( true );
222 
223  octagon.Append( *leftline.IntersectLines( bottomleftline ) );
224  octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
225  octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
226  octagon.Append( *rightline.IntersectLines( bottomrightline ) );
227  octagon.Append( *rightline.IntersectLines( toprightline ) );
228  octagon.Append( *topline.IntersectLines( toprightline ) );
229  octagon.Append( *topline.IntersectLines( topleftline ) );
230  octagon.Append( *leftline.IntersectLines( topleftline ) );
231 
232  return octagon;
233 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
coord_type GetX() const
Definition: box2.h:173
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:78
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:168
coord_type GetWidth() const
Definition: box2.h:180
BOX2< Vec > & Normalize()
Ensure that the height ant width are positive.
Definition: box2.h:112
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
Definition: seg.h:40
coord_type GetY() const
Definition: box2.h:174
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
coord_type GetHeight() const
Definition: box2.h:181
const Vec & GetSize() const
Definition: box2.h:172
const Vec & GetOrigin() const
Definition: box2.h:176

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(), HULL_MARGIN, 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 1188 of file pns_optimizer.cpp.

1191 {
1192  int vStartIdx[1024]; // fixme: possible overflow
1193  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1194  aRefBypass.CSegment( 0 ),
1195  aCoupled, aPair, vStartIdx );
1196  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1197 
1198  int64_t bestLength = -1;
1199  bool found = false;
1200  SHAPE_LINE_CHAIN bestBypass;
1201  int si, ei;
1202 
1203  for( int i=0; i< nStarts; i++ )
1204  {
1205  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1206  {
1207  int delta = std::abs ( vStartIdx[i] - j );
1208 
1209  if( delta > 1 )
1210  {
1211  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1212  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1213  dir.IsDiagonal() );
1214 
1215  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1216 
1217  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1218 
1219  si = vStartIdx[i];
1220  ei = j;
1221 
1222  if(si < ei)
1223  newCoupled.Replace( si, ei, bypass );
1224  else
1225  newCoupled.Replace( ei, si, bypass.Reverse() );
1226 
1227  if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1228  newCoupled) )
1229  {
1230  bestBypass = newCoupled;
1231  bestLength = coupledLength;
1232  found = true;
1233  }
1234  }
1235  }
1236  }
1237 
1238  if( found )
1239  aNewCoupled = bestBypass;
1240 
1241  return found;
1242 }
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
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)
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
constexpr int delta
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), delta, findCoupledVertices(), 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 424 of file pns_line_placer.cpp.

425 {
426  std::vector<int> dists;
427  std::vector<VECTOR2I> pts;
428 
429  if( aL.PointCount() == 0 )
430  return false;
431 
432  VECTOR2I lastP = aL.CPoint(-1);
433  int accumulatedDist = 0;
434 
435  dists.reserve( 2 * aL.PointCount() );
436 
437  for( int i = 0; i < aL.SegmentCount(); i++ )
438  {
439  const SEG& s = aL.CSegment( i );
440 
441  dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
442  pts.push_back( s.A );
443  auto pn = s.NearestPoint( aCursor );
444 
445  if( pn != s.A && pn != s.B )
446  {
447  dists.push_back( ( pn - aCursor ).EuclideanNorm() );
448  pts.push_back( pn );
449  }
450 
451  accumulatedDist += s.Length();
452 
453  if ( accumulatedDist > lengthThreshold )
454  {
455  lastP = s.B;
456  break;
457  }
458  }
459 
460  dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
461  pts.push_back( lastP );
462 
463  int minDistLoc = std::numeric_limits<int>::max();
464  int minPLoc = -1;
465  int minDistGlob = std::numeric_limits<int>::max();
466  int minPGlob = -1;
467 
468  for( int i = 0; i < dists.size(); i++ )
469  {
470  int d = dists[i];
471 
472  if( d < minDistGlob )
473  {
474  minDistGlob = d;
475  minPGlob = i;
476  }
477  }
478 
479  if( dists.size() >= 3 )
480  {
481  for( int i = 0; i < dists.size() - 3; i++ )
482  {
483  if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
484  {
485  int d = dists[i + 1];
486  if( d < minDistLoc )
487  {
488  minDistLoc = d;
489  minPLoc = i + 1;
490  }
491  }
492  }
493 
494  if( dists.back() < minDistLoc && minPLoc >= 0 )
495  {
496  minDistLoc = dists.back();
497  minPLoc = dists.size() - 1;
498  }
499  }
500  else
501  {
502  // Too few points: just use the global
503  minDistLoc = minDistGlob;
504  minPLoc = minPGlob;
505  }
506 
507 // fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
508 // in the code, enabling the global one by default
509  minPLoc = -1;
510 
511  if( minPLoc < 0 )
512  {
513  theDist = minDistGlob;
514  aNearest = pts[minPGlob];
515  return true;
516  }
517  else
518  {
519  theDist = minDistLoc;
520  aNearest = pts[minPLoc];
521  return true;
522  }
523 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
int Length() const
Return the length (this).
Definition: seg.h:350
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

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 609 of file pns_line.cpp.

610 {
611  OPT<SHAPE_LINE_CHAIN> picked;
612  int i;
613  int d = 2;
614 
615  wxASSERT( aOrigin.PointCount() > 0 );
616 
617  if( aOrigin.PointCount() == 1 )
618  {
619  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
620  }
621  else if( aOrigin.SegmentCount() == 1 )
622  {
623  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
624 
625  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
626  }
627 
628  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
629  d = 1;
630 
631  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
632  {
633  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
634  VECTOR2I p_start = aOrigin.CPoint( i );
635  SHAPE_LINE_CHAIN paths[2];
636  DIRECTION_45 dirs[2];
637  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
638  int dirCount = 0;
639 
640  for( int j = 0; j < 2; j++ )
641  {
642  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
643 
644  if( paths[j].SegmentCount() < 1 )
645  continue;
646 
647  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
648 
649  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
650  ++dirCount;
651  }
652 
653  for( int j = 0; j < dirCount; j++ )
654  {
655  if( dirs[j] == d_start )
656  {
657  picked = paths[j];
658  break;
659  }
660  }
661 
662  if( picked )
663  break;
664 
665  for( int j = 0; j < dirCount; j++ )
666  {
667  if( dirs[j].IsObtuse( d_prev ) )
668  {
669  picked = paths[j];
670  break;
671  }
672  }
673 
674  if( picked )
675  break;
676  }
677 
678  if( picked )
679  {
680  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
681  path.Append( *picked );
682 
683  return path;
684  }
685 
686  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
687 
688  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
689 }
int Length() const
Return the length (this).
Definition: seg.h:350
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.
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 PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
int SegmentCount() const
Return the number of segments in this line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
boost::optional< T > OPT
Definition: optional.h:7

References DIRECTION_45::BuildInitialTrace(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), 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 1152 of file pns_line.cpp.

1153 {
1154  if( aDefined )
1155  {
1156  aBox.Merge( aP );
1157  }
1158  else
1159  {
1160  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1161  aDefined = true;
1162  }
1163 }
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363

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

1144 {
1145  int count = 0;
1146 
1147  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1148  {
1149  SEG s = aCoupled.CSegment( i );
1150  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1151 
1152  if( s.ApproxParallel( aOrigSeg ) )
1153  {
1154  int64_t dist =
1155  int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1156 
1157  if( aPair->GapConstraint().Matches( dist ) )
1158  {
1159  *aIndices++ = i;
1160  count++;
1161  }
1162  }
1163  }
1164 
1165  return count;
1166 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.h:290
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:268
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.

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

1606 {
1607  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1608 
1609  if( !jt )
1610  return nullptr;
1611 
1612  for( ITEM* item : jt->LinkList() )
1613  {
1614  if( item->OfKind( ITEM::VIA_T ) )
1615  {
1616  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1617  return static_cast<VIA*>( item );
1618  }
1619  }
1620 
1621  return nullptr;
1622 }

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 }
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38

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

277 {
279 
280  if( line.PointCount() < 2 )
281  return;
282 
283  hull.Intersect( line, ips_raw );
284 
285  for( auto& p : ips_raw )
286  {
288 
289  SEG d1[2];
290  VECTOR2I d2[2];
291  int d1_idx = 0, d2_idx = 0;
292 
293  ipp = p;
294  ipp.valid = false;
295 
296  if( !p.is_corner_our && !p.is_corner_their )
297  {
298  ipp.valid = true;
299  ips.push_back( ipp );
300  continue;
301  }
302 
303  if( p.index_our >= hull.SegmentCount() )
304  p.index_our -= hull.SegmentCount();
305 
306  if( p.is_corner_our )
307  {
308  d1[0] = hull.CSegment( p.index_our );
309  d1[1] = hull.CSegment( p.index_our - 1 );
310  d1_idx = 2;
311  }
312  else
313  {
314  d1[0] = hull.CSegment( p.index_our );
315  d1_idx = 1;
316  }
317 
318  if( p.is_corner_their )
319  {
320  if( p.index_their > 0 )
321  {
322  d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
323  }
324  if( p.index_their < line.PointCount() - 1 )
325  {
326  d2[d2_idx++] = line.CSegment( p.index_their ).B;
327  }
328  }
329  else
330  {
331  d2[d2_idx++] = line.CSegment( p.index_their ).A;
332  d2[d2_idx++] = line.CSegment( p.index_their ).B;
333  }
334 
335  for( int i = 0; i < d1_idx; i++ )
336  {
337  for( int j = 0; j < d2_idx; j++ )
338  {
339  if( d1[i].Side( d2[j] ) > 0 )
340  {
341  ipp.valid = true;
342  }
343  }
344  }
345 
346 #ifdef TOM_EXTRA_DEBUG
347  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);
348  printf("d1 %d d2 %d\n", d1_idx, d2_idx );
349 #endif
350  if( ipp.valid )
351  {
352  ips.push_back( ipp );
353  }
354  }
355 }
Represent an intersection between two line segments.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
int PointCount() const
Return the number of points (vertices) in this line chain.
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

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().

◆ ItemCast()

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

Definition at line 263 of file pns_item.h.

264 {
265  static_assert( std::is_base_of<ITEM, S>::value, "Need to be handed a ITEM!" );
266  static_assert( std::is_base_of<ITEM, T>::value, "Need to cast to an ITEM!" );
267  return std::unique_ptr<T>( static_cast<T*>( aPtr.release() ) );
268 }

◆ 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 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
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 168 of file pns_utils.cpp.

169 {
170  int dist;
171 
172  aVertices.NearestPoint( aDiagonal, dist );
173  dist -= HULL_MARGIN;
174  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
175  aDiagonal.A += moveBy;
176  aDiagonal.B += moveBy;
177 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

References SEG::A, SEG::B, HULL_MARGIN, 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 35 of file pns_utils.cpp.

37 {
39 
40  s.SetClosed( true );
41 
42  s.Append( aP0.x - aClearance, aP0.y - aClearance + aChamfer );
43 
44  if( aChamfer )
45  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
46 
47  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
48 
49  if( aChamfer )
50  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
51 
52  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
53 
54  if( aChamfer )
55  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
56 
57  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
58 
59  if( aChamfer )
60  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
61 
62  return s;
63 }
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

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

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

◆ operator==()

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

Definition at line 288 of file pns_joint.h.

289 {
290  return aP1.pos == aP2.pos && aP1.net == aP2.net;
291 }

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 }
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
bool IsClosed() const override
int SegmentCount() const
Return the number of segments in this line chain.

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

125 {
126  int cl = aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
127  int d = aSeg.GetWidth() / 2 + cl;
128  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );
129 
130  const VECTOR2I a = aSeg.GetSeg().A;
131  const VECTOR2I b = aSeg.GetSeg().B;
132 
133  if( a == b )
134  {
135  return OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
136  VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
137  cl + 1,
138  2.0 * ( 1.0 - M_SQRT1_2 ) * d );
139  }
140 
141  VECTOR2I dir = b - a;
142  VECTOR2I p0 = dir.Perpendicular().Resize( d );
143  VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
144  VECTOR2I pd = dir.Resize( x / 2 );
145  VECTOR2I dp = dir.Resize( d );
146 
148 
149  s.SetClosed( true );
150 
151  s.Append( b + p0 + pd );
152  s.Append( b + dp + ds );
153  s.Append( b + dp - ds );
154  s.Append( b - p0 + pd );
155  s.Append( a - p0 - pd );
156  s.Append( a - dp - ds );
157  s.Append( a - dp + ds );
158  s.Append( a + p0 - pd );
159 
160  // make sure the hull outline is always clockwise
161  if( s.CSegment( 0 ).Side( a ) < 0 )
162  return s.Reverse();
163  else
164  return s;
165 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
const SEG & GetSeg() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:35
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
VECTOR2I A
Definition: seg.h:48
int GetWidth() const
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
VECTOR2I B
Definition: seg.h:49

References SEG::A, SHAPE_LINE_CHAIN::Append(), SEG::B, SHAPE_LINE_CHAIN::CSegment(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), HULL_MARGIN, OctagonalHull(), VECTOR2< T >::Perpendicular(), VECTOR2< T >::Resize(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SetClosed(), and SEG::Side().

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

◆ shovedArea()

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

Definition at line 1363 of file pns_optimizer.cpp.

1364 {
1365  int64_t area = 0;
1366  const int oc = aOld.PointCount();
1367  const int nc = aNew.PointCount();
1368  const int total = oc + nc;
1369 
1370  for(int i = 0; i < total; i++)
1371  {
1372  int i_next = (i + 1 == total ? 0 : i + 1);
1373 
1374  const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1375  : aNew.CPoint( nc - 1 - (i - oc) );
1376  const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1377  : aNew.CPoint( nc - 1 - (i_next - oc) );
1378  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1379  }
1380 
1381  return std::abs( area / 2 );
1382 }
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

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

1488 {
1489  LINE tmp;
1490 
1491  if( aNewLine.SegmentCount() < 3 )
1492  return;
1493 
1494  SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1495 
1496  for( int step = 0; step < 3; step++ )
1497  {
1498  current.Simplify();
1499 
1500  for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1501  {
1502  SHAPE_LINE_CHAIN l_in, l_out;
1503 
1504  l_in = current.Slice( i, i + 3 );
1505 
1506  for( int dir = 0; dir <= 1; dir++ )
1507  {
1508  if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1509  {
1510  SHAPE_LINE_CHAIN opt = current;
1511  opt.Replace( i, i + 3, l_out );
1512  auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1513  auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1514 
1515  if( optArea < prevArea )
1516  current = opt;
1517 
1518  break;
1519  }
1520  }
1521  }
1522  }
1523 
1524  aOptimized = LINE( aNewLine, current );
1525 
1526  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1527  //dbg->AddLine ( current, 4, 100000 );
1528 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
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)
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::Replace(), 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 1385 of file pns_optimizer.cpp.

1387 {
1388  SEG a = in.CSegment(0);
1389  SEG center = in.CSegment(1);
1390  SEG b = in.CSegment(2);
1391 
1392  DIRECTION_45 dirA ( a );
1393  DIRECTION_45 dirCenter ( center );
1394  DIRECTION_45 dirB ( b );
1395 
1396  if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1397  return false;
1398 
1399  //VECTOR2I perp = (center.B - center.A).Perpendicular();
1400  VECTOR2I guideA, guideB ;
1401 
1402  SEG guide;
1403  int initial;
1404 
1405  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1406  if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1407  return false;
1408 
1409  {
1410  /*
1411  auto rC = *a.IntersectLines( b );
1412  dbg->AddSegment ( SEG( center.A, rC ), 1 );
1413  dbg->AddSegment ( SEG( center.B, rC ), 2 );
1414  auto perp = dirCenter.Left().Left();
1415 
1416  SEG sperp ( center.A, center.A + perp.ToVector() );
1417 
1418  auto vpc = sperp.LineProject( rC );
1419  auto vpa = sperp.LineProject( a.A );
1420  auto vpb = sperp.LineProject( b.B );
1421 
1422  auto da = (vpc - vpa).EuclideanNorm();
1423  auto db = (vpc - vpb).EuclideanNorm();
1424 
1425  auto vp = (da < db) ? vpa : vpb;
1426  dbg->AddSegment ( SEG( vpc, vp ), 5 );
1427 
1428 
1429  guide = SEG ( vpc, vp );
1430  */
1431  }
1432 
1433  int da = a.Length();
1434  int db = b.Length();
1435 
1436  if( da < db )
1437  guide = a;
1438  else
1439  guide = b;
1440 
1441  initial = guide.Length();
1442 
1443  int step = initial;
1444  int current = step;
1445  SHAPE_LINE_CHAIN snew;
1446 
1447  while( step > 1 )
1448  {
1449  LINE l( cur );
1450 
1451  snew.Clear();
1452  snew.Append( a.A );
1453  snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1454  snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1455  snew.Append( b.B );
1456 
1457  step /= 2;
1458 
1459  l.SetShape(snew);
1460 
1461  if( aNode->CheckColliding(&l) )
1462  current -= step;
1463  else if ( current + step >= initial )
1464  current = initial;
1465  else
1466  current += step;
1467 
1468  //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1469  //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1470  //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1471 
1472  if ( current == initial )
1473  break;
1474 
1475 
1476  }
1477 
1478  out = snew;
1479 
1480  //dbg->AddLine ( snew, 3, 100000 );
1481 
1482  return true;
1483 }
int Length() const
Return the length (this).
Definition: seg.h:350
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
Definition: seg.h:40
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
VECTOR2I A
Definition: seg.h:48
void Clear()
Remove all points from the line chain.
VECTOR2I B
Definition: seg.h:49

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

1171 {
1172  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1173  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1174 
1175  if( refLine.Collide( &coupledLine, aNode ) )
1176  return false;
1177 
1178  if( aNode->CheckColliding ( &refLine ) )
1179  return false;
1180 
1181  if( aNode->CheckColliding ( &coupledLine ) )
1182  return false;
1183 
1184  return true;
1185 }

References PNS::NODE::CheckColliding(), 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

Definition at line 34 of file pns_utils.h.

Referenced by ArcHull(), ConvexHull(), MoveDiagonal(), and SegmentHull().

◆ pnsSchemaVersion

const int PNS::pnsSchemaVersion = 0

Definition at line 29 of file pns_routing_settings.cpp.

◆ theRouter