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_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, RM_Smart }
 < Routing modes More...
 
enum  PNS_OPTIMIZATION_EFFORT { OE_LOW = 0, OE_MEDIUM = 1, OE_FULL = 2 }
 
enum  CORNER_MODE { CORNER_MODE::MITERED_90, CORNER_MODE::MITERED_45, CORNER_MODE::ROUNDED_90, CORNER_MODE::ROUNDED_45 }
 

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.

◆ CORNER_MODE

enum PNS::CORNER_MODE
strong
Enumerator
MITERED_90 

H/V only (90-degree corners) (not yet implemented)

MITERED_45 

H/V/45 with mitered corners (default)

ROUNDED_90 

H/V with filleted corners (not yet implemented)

ROUNDED_45 

H/V/45 with filleted corners.

Definition at line 55 of file pns_routing_settings.h.

56 {
57  MITERED_90,
58  MITERED_45,
59  ROUNDED_90,
60  ROUNDED_45
61 };
H/V/45 with filleted corners.
H/V with filleted corners (not yet implemented)
H/V only (90-degree corners) (not yet implemented)
H/V/45 with mitered corners (default)

◆ 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 49 of file pns_meander.h.

49  {
50  MEANDER_STYLE_ROUND = 1, // rounded (90 degree arc)
51  MEANDER_STYLE_CHAMFER // chamfered (45 degree segment)
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_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_EMPTY // no meander (straight line)
46 };

◆ PNS_MODE

< Routing modes

Enumerator
RM_MarkObstacles 

Ignore collisions, mark obstacles.

RM_Shove 

Only shove.

RM_Walkaround 

Only walk around.

RM_Smart 

Guess what's better, try to make least mess on the PCB.

Definition at line 38 of file pns_routing_settings.h.

39 {
40  RM_MarkObstacles = 0,
41  RM_Shove,
43  RM_Smart
44 };
Guess what's better, try to make least mess on the PCB.
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(), HPGL_PLOTTER::Arc(), GEOM_TEST::ArePerpendicular(), BuildCornersList_S_Shape(), PNS::DP_GATEWAYS::BuildGeneric(), PNS::OPTIMIZER::circleBreakouts(), PCB_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_LEGACY::generateRing(), GetArcAngle(), 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(), SCH_SEXPR_PARSER::parseSchSheetPin(), FABMASTER::processArc(), processComp(), processSolid(), AR_AUTOPLACER::rotateFootprint(), RotatePoint(), SCH_SEXPR_PLUGIN::saveSymbol(), SCH_SEXPR_PLUGIN::saveText(), PCB_SHAPE::SetArcGeometry(), 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
VECTOR2I A
Definition: seg.h:48
int GetWidth() const
VECTOR2I B
Definition: seg.h:49

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

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:130
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:459
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
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 39 of file pns_solid.cpp.

41 {
42  int cl = aClearance + ( aWalkaroundThickness + 1 )/ 2;
43 
44  switch( aShape->Type() )
45  {
46  case SH_RECT:
47  {
48  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>( aShape );
49  return OctagonalHull( rect->GetPosition(),
50  rect->GetSize(),
51  cl + 1,
52  0 );
53  }
54 
55  case SH_CIRCLE:
56  {
57  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
58  int r = circle->GetRadius();
59  return OctagonalHull( circle->GetCenter() - VECTOR2I( r, r ),
60  VECTOR2I( 2 * r, 2 * r ),
61  cl + 1,
62  2.0 * ( 1.0 - M_SQRT1_2 ) * ( r + cl ) );
63  }
64 
65  case SH_SEGMENT:
66  {
67  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*>( aShape );
68  return SegmentHull( *seg, aClearance, aWalkaroundThickness );
69  }
70 
71  case SH_ARC:
72  {
73  const SHAPE_ARC* arc = static_cast<const SHAPE_ARC*>( aShape );
74  return ArcHull( *arc, aClearance, aWalkaroundThickness );
75  }
76 
77  case SH_SIMPLE:
78  {
79  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aShape );
80 
81  return ConvexHull( *convex, cl );
82  }
83  default:
84  {
85  wxFAIL_MSG( wxString::Format( "Unsupported hull shape: %d (%s).",
86  aShape->Type(),
87  SHAPE_TYPE_asString( aShape->Type() ) ) );
88  break;
89  }
90  }
91 
92  return SHAPE_LINE_CHAIN();
93 }
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:623
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
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 (an zero-thickness chain of connected line segments).
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(), 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:70
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 1246 of file pns_optimizer.cpp.

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

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

266 {
267  static_assert( std::is_base_of<ITEM, T>::value, "Need to be handed an ITEM!" );
268  return std::unique_ptr<typename std::remove_const<T>::type>( aItem.Clone() );
269 }

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(), and PNS::LINE_PLACER::SplitAdjacentSegments().

◆ closestProjectedPoint()

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

Definition at line 402 of file pns_line_placer.cpp.

403 {
404  // Keep distances squared for performance
405  SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
406  VECTOR2I closest;
407 
408  for( int i = 0; i < line.SegmentCount(); i++ )
409  {
410  const SEG& s = line.CSegment( i );
411  VECTOR2I a = s.NearestPoint( p );
412  int d_sq = (a - p).SquaredEuclideanNorm();
413 
414  if( d_sq < min_dist_sq )
415  {
416  min_dist_sq = d_sq;
417  closest = a;
418  }
419  }
420 
421  return closest;
422 }
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 779 of file pns_diff_pair.cpp.

780 {
781  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
782 
783  int64_t t_a = 0;
784  int64_t t_b = p.TCoef( p.B );
785 
786  int64_t tproj_a = p.TCoef( n_proj_p.A );
787  int64_t tproj_b = p.TCoef( n_proj_p.B );
788 
789  if( t_b < t_a )
790  std::swap( t_b, t_a );
791 
792  if( tproj_b < tproj_a )
793  std::swap( tproj_b, tproj_a );
794 
795  if( t_b <= tproj_a )
796  return false;
797 
798  if( t_a >= tproj_b )
799  return false;
800 
801  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
802  std::vector<int64_t> tv( t, t + 4 );
803  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
804 
805  int64_t pLenSq = p.SquaredLength();
806 
807  VECTOR2I dp = p.B - p.A;
808  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
809  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
810 
811  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
812  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
813 
814  nClip.A = n.LineProject( pClip.A );
815  nClip.B = n.LineProject( pClip.B );
816 
817  return true;
818 }
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:623
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 (an zero-thickness chain of connected line segments).
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 1189 of file pns_optimizer.cpp.

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

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

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

1138 {
1139  if( aDefined )
1140  {
1141  aBox.Merge( aP );
1142  }
1143  else
1144  {
1145  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1146  aDefined = true;
1147  }
1148 }
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
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 1143 of file pns_optimizer.cpp.

1145 {
1146  int count = 0;
1147 
1148  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1149  {
1150  SEG s = aCoupled.CSegment( i );
1151  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1152 
1153  if( s.ApproxParallel( aOrigSeg ) )
1154  {
1155  int64_t dist =
1156  int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1157 
1158  if( aPair->GapConstraint().Matches( dist ) )
1159  {
1160  *aIndices++ = i;
1161  count++;
1162  }
1163  }
1164  }
1165 
1166  return count;
1167 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
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
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:290
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 1598 of file pns_shove.cpp.

1599 {
1600  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1601 
1602  if( !jt )
1603  return nullptr;
1604 
1605  for( ITEM* item : jt->LinkList() )
1606  {
1607  if( item->OfKind( ITEM::VIA_T ) )
1608  {
1609  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1610  return static_cast<VIA*>( item );
1611  }
1612  }
1613 
1614  return nullptr;
1615 }

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 437 of file pns_diff_pair_placer.cpp.

438 {
439  switch( aItem->Kind() )
440  {
441  case ITEM::VIA_T:
442  case ITEM::SOLID_T:
443  return aItem->Anchor( 0 );
444 
445  case ITEM::ARC_T:
446  case ITEM::SEGMENT_T:
447  {
448  SEGMENT* s = static_cast<SEGMENT*>( aItem );
449 
450  JOINT* jA = aNode->FindJoint( aItem->Anchor( 0 ), aItem );
451  JOINT* jB = aNode->FindJoint( aItem->Anchor( 1 ), aItem );
452 
453  if( jA && jA->LinkCount() == 1 )
454  return s->Seg().A;
455  else if( jB && jB->LinkCount() == 1 )
456  return s->Seg().B;
457  else
458  return OPT_VECTOR2I();
459  }
460 
461  default:
462  return OPT_VECTOR2I();
463  }
464 }
usual segment : line with rounded ends
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 257 of file pns_item.h.

258 {
259  static_assert( std::is_base_of<ITEM, S>::value, "Need to be handed a ITEM!" );
260  static_assert( std::is_base_of<ITEM, T>::value, "Need to cast to an ITEM!" );
261  return std::unique_ptr<T>( static_cast<T*>( aPtr.release() ) );
262 }

◆ 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 (an zero-thickness chain of connected line segments).

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 265 of file pns_joint.h.

266 {
267  return aP1.pos == aP2.pos && aP1.net == aP2.net;
268 }

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

295 {
296  if( !aL.IsClosed() || aL.SegmentCount() < 3 )
297  return false;
298 
299  int result = 0;
300  size_t cnt = aL.PointCount();
301 
302  VECTOR2I ip = aL.CPoint( 0 );
303 
304  for( size_t i = 1; i <= cnt; ++i )
305  {
306  VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
307 
308  if( ipNext.y == aP.y )
309  {
310  if( ( ipNext.x == aP.x )
311  || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
312  return true; // pt on polyground boundary
313  }
314 
315  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
316  {
317  if( ip.x >=aP.x )
318  {
319  if( ipNext.x >aP.x )
320  {
321  result = 1 - result;
322  }
323  else
324  {
325  double d = static_cast<double>( ip.x - aP.x ) *
326  static_cast<double>( ipNext.y - aP.y ) -
327  static_cast<double>( ipNext.x - aP.x ) *
328  static_cast<double>( ip.y - aP.y );
329 
330  if( !d )
331  return true; // pt on polyground boundary
332 
333  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
334  result = 1 - result;
335  }
336  }
337  else
338  {
339  if( ipNext.x >aP.x )
340  {
341  double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
342  - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
343 
344  if( !d )
345  return true; // pt on polyground boundary
346 
347  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
348  result = 1 - result;
349  }
350  }
351  }
352 
353  ip = ipNext;
354  }
355 
356  return result > 0;
357 }
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:623
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 (an zero-thickness chain of connected line segments).
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 1364 of file pns_optimizer.cpp.

1365 {
1366  int64_t area = 0;
1367  const int oc = aOld.PointCount();
1368  const int nc = aNew.PointCount();
1369  const int total = oc + nc;
1370 
1371  for(int i = 0; i < total; i++)
1372  {
1373  int i_next = (i + 1 == total ? 0 : i + 1);
1374 
1375  const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1376  : aNew.CPoint( nc - 1 - (i - oc) );
1377  const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1378  : aNew.CPoint( nc - 1 - (i_next - oc) );
1379  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1380  }
1381 
1382  return std::abs( area / 2 );
1383 }
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 1487 of file pns_optimizer.cpp.

1489 {
1490  LINE tmp;
1491 
1492  if( aNewLine.SegmentCount() < 3 )
1493  return;
1494 
1495  SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1496 
1497  for( int step = 0; step < 3; step++ )
1498  {
1499  current.Simplify();
1500 
1501  for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1502  {
1503  SHAPE_LINE_CHAIN l_in, l_out;
1504 
1505  l_in = current.Slice( i, i + 3 );
1506 
1507  for( int dir = 0; dir <= 1; dir++ )
1508  {
1509  if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1510  {
1511  SHAPE_LINE_CHAIN opt = current;
1512  opt.Replace( i, i + 3, l_out );
1513  auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1514  auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1515 
1516  if( optArea < prevArea )
1517  current = opt;
1518 
1519  break;
1520  }
1521  }
1522  }
1523  }
1524 
1525  aOptimized = LINE( aNewLine, current );
1526 
1527  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1528  //dbg->AddLine ( current, 4, 100000 );
1529 }
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 (an zero-thickness chain of connected line segments).
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 1386 of file pns_optimizer.cpp.

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

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

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 playground_main_func(), and PNS::LINE::Walkaround().

◆ g_pnew

SHAPE_LINE_CHAIN PNS::g_pnew

Definition at line 169 of file pns_line.cpp.

Referenced by playground_main_func(), and 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