KiCad PCB EDA Suite
PNS Namespace Reference

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

Classes

class  ALGO_BASE
 ALGO_BASE. More...
 
class  ANGLE_CONSTRAINT_45
 
class  ARC
 
class  AREA_CONSTRAINT
 
class  COMPONENT_DRAGGER
 COMPONENT_DRAGGER. More...
 
struct  CONSTRAINT
 
class  COST_ESTIMATOR
 COST_ESTIMATOR. More...
 
class  DEBUG_DECORATOR
 
class  DIFF_PAIR
 DIFF_PAIR. More...
 
class  DIFF_PAIR_PLACER
 LINE_PLACER. More...
 
class  DP_GATEWAY
 DP_GATEWAY. More...
 
class  DP_GATEWAYS
 DP_GATEWAYS. More...
 
class  DP_MEANDER_PLACER
 DP_MEANDER_PLACER. More...
 
class  DP_PRIMITIVE_PAIR
 DP_PRIMITIVE_PAIR. More...
 
class  DRAG_ALGO
 DRAG_ALGO. More...
 
class  DRAGGER
 DRAGGER. More...
 
class  FIXED_TAIL
 
struct  HIT_VISITOR
 
class  INDEX
 INDEX. More...
 
class  ITEM
 ITEM. More...
 
class  ITEM_SET
 
class  JOINT
 JOINT. More...
 
class  JOINT_CACHE
 
class  KEEP_TOPOLOGY_CONSTRAINT
 
class  LINE
 
class  LINE_PLACER
 LINE_PLACER. More...
 
class  LINK_HOLDER
 
class  LINKED_ITEM
 
class  LOGGER
 
class  MEANDER_PLACER
 MEANDER_PLACER. More...
 
class  MEANDER_PLACER_BASE
 MEANDER_PLACER_BASE. More...
 
class  MEANDER_SETTINGS
 MEANDER_SETTINGS. More...
 
class  MEANDER_SHAPE
 MEANDER_SETTINGS. More...
 
class  MEANDER_SKEW_PLACER
 MEANDER_SKEW_PLACER. More...
 
class  MEANDERED_LINE
 MEANDERED_LINE. More...
 
class  NODE
 NODE. More...
 
struct  OBSTACLE
 Struct OBSTACLE. More...
 
class  OBSTACLE_VISITOR
 Struct OBSTACLE_VISITOR. More...
 
class  OPT_CONSTRAINT
 
class  OPTIMIZER
 OPTIMIZER. More...
 
class  PLACEMENT_ALGO
 PLACEMENT_ALGO. More...
 
class  POSTURE_SOLVER
 
class  PRESERVE_VERTEX_CONSTRAINT
 
class  RESTRICT_VERTEX_RANGE_CONSTRAINT
 
class  ROUTER
 
class  ROUTER_IFACE
 ROUTER. More...
 
class  ROUTING_SETTINGS
 ROUTING_SETTINGS. More...
 
class  RULE_RESOLVER
 
class  SEGMENT
 
class  SHOVE
 SHOVE. More...
 
class  SIZES_SETTINGS
 
class  SOLID
 
class  TIME_LIMIT
 
class  TOOL_BASE
 
class  TOPOLOGY
 
class  VIA
 
struct  VIA_HANDLE
 
class  WALKAROUND
 

Enumerations

enum  LineMarker {
  MK_HEAD = ( 1 << 0 ), MK_VIOLATION = ( 1 << 3 ), MK_LOCKED = ( 1 << 4 ), MK_DP_COUPLED = ( 1 << 5 ),
  MK_ALT_SHAPE = ( 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 }
 

meander corner shape

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

Optimization effort

More...
 

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)
 
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)
 
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 pointInside2 (const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
 
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)
 
bool clipToLoopStart (SHAPE_LINE_CHAIN &l)
 

Variables

static DEBUG_DECORATORg_dbg
 
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

RULE_RESOLVER.

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 

Definition at line 58 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 76 of file pns_router.h.

77 {
78  DM_CORNER = 0x1,
79  DM_SEGMENT = 0x2,
80  DM_VIA = 0x4,
81  DM_FREE_ANGLE = 0x8,
82  DM_ARC = 0x10,
83  DM_ANY = 0x17,
84  DM_COMPONENT = 0x20
85 };

◆ LineMarker

Enumerator
MK_HEAD 
MK_VIOLATION 
MK_LOCKED 
MK_DP_COUPLED 
MK_ALT_SHAPE 

Definition at line 39 of file pns_item.h.

39  {
40  MK_HEAD = ( 1 << 0 ),
41  MK_VIOLATION = ( 1 << 3 ),
42  MK_LOCKED = ( 1 << 4 ),
43  MK_DP_COUPLED = ( 1 << 5 ),
44  MK_ALT_SHAPE = ( 1 << 6 )
45 };

◆ MEANDER_STYLE

meander corner shape

Enumerator
MEANDER_STYLE_ROUND 
MEANDER_STYLE_CHAMFER 

Definition at line 47 of file pns_meander.h.

47  {
48  MEANDER_STYLE_ROUND = 1, // rounded (90 degree arc)
49  MEANDER_STYLE_CHAMFER // chamfered (45 degree segment)
50 };

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

35  {
36  MT_SINGLE, // _|^|_, single-sided
37  MT_START, // _|^|
38  MT_FINISH, // |^|_
39  MT_TURN, // |^| or |_|
40  MT_CHECK_START, // try fitting a start type, but don't produce a line
41  MT_CHECK_FINISH, // try fitting a finish type, but don't produce a line
42  MT_CORNER, // line corner
43  MT_EMPTY // no meander (straight line)
44 };

◆ PNS_MODE

Routing modes

Enumerator
RM_MarkObstacles 
RM_Shove 

Ignore collisions, mark obstacles

RM_Walkaround 

Only shove

RM_Smart 

Only walkaround

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

Definition at line 37 of file pns_routing_settings.h.

38 {
39  RM_MarkObstacles = 0,
40  RM_Shove,
42  RM_Smart
43 };
Ignore collisions, mark obstacles
Only walkaround

◆ PNS_OPTIMIZATION_EFFORT

Optimization effort

Enumerator
OE_LOW 
OE_MEDIUM 
OE_FULL 

Definition at line 46 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 68 of file pns_router.h.

Function Documentation

◆ angle()

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

Definition at line 178 of file pns_diff_pair.cpp.

179 {
180  DIRECTION_45 dir_a( a );
181  DIRECTION_45 dir_b( b );
182 
183  return dir_a.Angle( dir_b );
184 }
DIRECTION_45.
Definition: direction45.h:37

References DIRECTION_45::Angle().

Referenced by DXF_IMPORT_PLUGIN::addArc(), EC_45DEGREE::Apply(), EC_CIRCLE::Apply(), HPGL_PLOTTER::Arc(), GEOM_TEST::ArePerpendicular(), BuildCornersList_S_Shape(), PNS::DP_GATEWAYS::BuildGeneric(), PNS::OPTIMIZER::circleBreakouts(), PCB_SHAPE::computeArcBBox(), ConvertOutlineToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), D_CODE::ConvertShapeToPolygon(), 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(), export_vrml_line(), PCB_TEXT::Flip(), DSN::SPECCTRA_DB::FromBOARD(), C3D_RENDER_OGL_LEGACY::generate_ring_contour(), 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(), 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(), processComp(), processSolid(), AR_AUTOPLACER::rotateFootprint(), RotatePoint(), SCH_SEXPR_PLUGIN::saveSymbol(), SCH_SEXPR_PLUGIN::saveText(), FP_TEXT::SetDrawCoord(), PAD::SetDrawCoord(), FP_SHAPE::SetLocalCoord(), FP_TEXT::SetLocalCoord(), AR_MATRIX::traceArc(), AR_MATRIX::traceCircle(), AR_MATRIX::TraceFilledRectangle(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundRectToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and FP_TEXT::ViewBBox().

◆ ApproximateSegmentAsRect()

SHAPE_RECT PNS::ApproximateSegmentAsRect ( const SHAPE_SEGMENT aSeg)

Definition at line 216 of file pns_utils.cpp.

217 {
218  SHAPE_RECT r;
219 
220  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
221  VECTOR2I p0( aSeg.GetSeg().A - delta );
222  VECTOR2I p1( aSeg.GetSeg().B + delta );
223 
224  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
225  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
226 }
const SEG & GetSeg() const
VECTOR2I A
Definition: seg.h:47
int GetWidth() const
VECTOR2I B
Definition: seg.h:48

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

57 {
58  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
59  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
60 
61  auto line = aSeg.ConvertToPolyline();
62 
64  s.SetClosed( true );
65  std::vector<VECTOR2I> reverse_line;
66 
67  auto seg = line.Segment( 0 );
68  VECTOR2I dir = seg.B - seg.A;
69  VECTOR2I p0 = dir.Perpendicular().Resize( d );
70  VECTOR2I ds = dir.Perpendicular().Resize( x );
71  VECTOR2I pd = dir.Resize( x );
72  VECTOR2I dp = dir.Resize( d );
73 
74  // Append the first curve
75  s.Append( seg.A + p0 - pd );
76  s.Append( seg.A - dp + ds );
77  s.Append( seg.A - dp - ds );
78  s.Append( seg.A - p0 - pd );
79 
80  for( int i = 1; i < line.SegmentCount(); i++ )
81  {
82  auto old_seg = seg;
83  auto endpt = ( old_seg.A - old_seg.B ).Resize( seg.Length() );
84  old_seg.A = old_seg.B + endpt;
85 
86  seg = line.Segment( i );
87  auto dir2 = old_seg.A - seg.B;
88 
89  p0 = dir2.Perpendicular().Resize( d );
90  s.Append( seg.A - p0 );
91  reverse_line.push_back( seg.A + p0 );
92  }
93 
94  pd = dir.Resize( x );
95  dp = dir.Resize( d );
96  s.Append( seg.B - p0 + pd );
97  s.Append( seg.B + dp - ds );
98  s.Append( seg.B + dp + ds );
99  s.Append( seg.B + p0 + pd );
100 
101  for( int i = reverse_line.size() - 1; i >= 0; i-- )
102  s.Append( reverse_line[i] );
103 
104  // make sure the hull outline is always clockwise
105  if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
106  return s.Reverse();
107  else
108  return s;
109 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
VECTOR2< T > Perpendicular() const
Function Perpendicular computes the perpendicular vector.
Definition: vector2d.h:320
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
int GetWidth() const
Definition: shape_arc.h:102
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:138

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 PNS::ARC::Hull().

◆ buildHullForPrimitiveShape()

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

Definition at line 37 of file pns_solid.cpp.

38 {
39  int cl = aClearance + ( aWalkaroundThickness + 1 )/ 2;
40 
41  switch( aShape->Type() )
42  {
43  case SH_RECT:
44  {
45  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>( aShape );
46  return OctagonalHull( rect->GetPosition(), rect->GetSize(), cl + 1, 0.2 * cl );
47  }
48 
49  case SH_CIRCLE:
50  {
51  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
52  int r = circle->GetRadius();
53  return OctagonalHull( circle->GetCenter() - VECTOR2I( r, r ), VECTOR2I( 2 * r, 2 * r ),
54  cl + 1, 0.52 * ( r + cl ) );
55  }
56 
57  case SH_SEGMENT:
58  {
59  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*>( aShape );
60  return SegmentHull( *seg, aClearance, aWalkaroundThickness );
61  }
62 
63  case SH_SIMPLE:
64  {
65  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aShape );
66 
67  return ConvexHull( *convex, cl );
68  }
69  default:
70  {
71  wxLogError("Unsupported hull shape: %d", aShape->Type() );
72  break;
73  }
74  }
75 
76  return SHAPE_LINE_CHAIN();
77 }
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:160
SHAPE_SIMPLE.
Definition: shape_simple.h:43
int GetRadius() const
Definition: shape_circle.h:99
const VECTOR2I GetCenter() const
Definition: shape_circle.h:104
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:112
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:123
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:113
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:35
line chain (polyline)
Definition: shape.h:46
SHAPE_LINE_CHAIN.
Definition: shape.h:43
circle
Definition: shape.h:47
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:98
axis-aligned rectangle
Definition: shape.h:44

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

Referenced by PNS::SOLID::Hull().

◆ ChangedArea() [1/2]

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

Definition at line 290 of file pns_utils.cpp.

291 {
292  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
293  {
294  const VIA* va = static_cast<const VIA*>( aItemA );
295  const VIA* vb = static_cast<const VIA*>( aItemB );
296 
297  return va->ChangedArea( vb );
298  }
299  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
300  {
301  const LINE* la = static_cast<const LINE*> ( aItemA );
302  const LINE* lb = static_cast<const LINE*> ( aItemB );
303 
304  return la->ChangedArea( lb );
305  }
306 
307  return OPT_BOX2I();
308 }
Definition: track.h:354
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525

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

311 {
312  return aLineA.ChangedArea( &aLineB );
313 }

References PNS::LINE::ChangedArea().

◆ checkDpColliding()

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

Definition at line 1192 of file pns_optimizer.cpp.

1193 {
1194  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1195 
1196  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1197 }

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 187 of file pns_diff_pair.cpp.

188 {
189  int i, j;
190 
191  for( i = 0; i < p.SegmentCount(); i++ )
192  {
193  for( j = 0; j < n.SegmentCount() ; j++ )
194  {
195  int dist = p.CSegment( i ).Distance( n.CSegment( j ) );
196 
197  if( dist < gap - 100 )
198  return false;
199  }
200  }
201 
202  return true;
203 }
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

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

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

◆ clipToLoopStart()

bool PNS::clipToLoopStart ( SHAPE_LINE_CHAIN l)

Definition at line 160 of file pns_walkaround.cpp.

161 {
162  auto ip = l.SelfIntersecting();
163 
164  if(!ip)
165  return false;
166  else {
167  int pidx = l.Split( ip->p );
168  auto lead = l.Slice(0, pidx);
169  auto tail = l.Slice(pidx + 1, -1);
170 
171  int pidx2 = tail.Split( ip->p );
172 
173  auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
174  dbg->AddPoint( ip->p, 5 );
175 
176  l = lead;
177  l.Append( tail.Slice( 0, pidx2 ) );
178  //l = l.Slice(0, pidx);
179  return true;
180  }
181 
182 
183 }
int Split(const VECTOR2I &aP)
Function Split()
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()

References PNS::DEBUG_DECORATOR::AddPoint(), SHAPE_LINE_CHAIN::Append(), PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInstance(), PNS::ROUTER::GetInterface(), SHAPE_LINE_CHAIN::SelfIntersecting(), SHAPE_LINE_CHAIN::Slice(), and SHAPE_LINE_CHAIN::Split().

Referenced by PNS::WALKAROUND::Route().

◆ Clone()

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

Definition at line 277 of file pns_item.h.

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

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

371 {
372  int min_dist = INT_MAX;
373  VECTOR2I closest;
374 
375  for(int i = 0; i < line.SegmentCount(); i++ )
376  {
377  const auto& s = line.CSegment(i);
378  auto a = s.NearestPoint( p );
379  auto d = (a - p).EuclideanNorm();
380 
381  if( d < min_dist )
382  {
383  min_dist = d;
384  closest = a;
385  }
386  }
387 
388  return closest;
389 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

References SHAPE_LINE_CHAIN::CSegment(), EuclideanNorm(), SEG::NearestPoint(), and SHAPE_LINE_CHAIN::SegmentCount().

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

◆ commonParallelProjection()

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

Definition at line 772 of file pns_diff_pair.cpp.

773 {
774  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
775 
776  int64_t t_a = 0;
777  int64_t t_b = p.TCoef( p.B );
778 
779  int64_t tproj_a = p.TCoef( n_proj_p.A );
780  int64_t tproj_b = p.TCoef( n_proj_p.B );
781 
782  if( t_b < t_a )
783  std::swap( t_b, t_a );
784 
785  if( tproj_b < tproj_a )
786  std::swap( tproj_b, tproj_a );
787 
788  if( t_b <= tproj_a )
789  return false;
790 
791  if( t_a >= tproj_b )
792  return false;
793 
794  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
795  std::vector<int64_t> tv( t, t + 4 );
796  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
797 
798  int64_t pLenSq = p.SquaredLength();
799 
800  VECTOR2I dp = p.B - p.A;
801  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
802  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
803 
804  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
805  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
806 
807  nClip.A = n.LineProject( pClip.A );
808  nClip.B = n.LineProject( pClip.B );
809 
810  return true;
811 }
ecoord SquaredLength() const
Definition: seg.h:324
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:362
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:389
Definition: seg.h:39
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
VECTOR2I B
Definition: seg.h:48

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

161 {
162  // this defines the horizontal and vertical lines in the hull octagon
163  BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
164  box.Normalize();
165 
166  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
167  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
168  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
169  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
170  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
171  box.GetOrigin() );
172  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
173 
174  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
175 
176  // top right diagonal
177  VECTOR2I corner = box.GetOrigin() + box.GetSize();
178  SEG toprightline = SEG( corner,
179  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
180  MoveDiagonal( toprightline, vertices, aClearance );
181 
182  // bottom right diagonal
183  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
184  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
185  corner );
186  MoveDiagonal( bottomrightline, vertices, aClearance );
187 
188  // bottom left diagonal
189  corner = box.GetOrigin();
190  SEG bottomleftline = SEG( corner,
191  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
192  MoveDiagonal( bottomleftline, vertices, aClearance );
193 
194  // top left diagonal
195  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
196  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
197  corner );
198  MoveDiagonal( topleftline, vertices, aClearance );
199 
200  SHAPE_LINE_CHAIN octagon;
201  octagon.SetClosed( true );
202 
203  octagon.Append( *leftline.IntersectLines( bottomleftline ) );
204  octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
205  octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
206  octagon.Append( *rightline.IntersectLines( bottomrightline ) );
207  octagon.Append( *rightline.IntersectLines( toprightline ) );
208  octagon.Append( *topline.IntersectLines( toprightline ) );
209  octagon.Append( *topline.IntersectLines( topleftline ) );
210  octagon.Append( *leftline.IntersectLines( topleftline ) );
211 
212  return octagon;
213 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
coord_type GetX() const
Definition: box2.h:190
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:191
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_simple.h:82
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:148
coord_type GetWidth() const
Definition: box2.h:197
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:129
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:133
Definition: seg.h:39
coord_type GetY() const
Definition: box2.h:191
SHAPE_LINE_CHAIN.
coord_type GetHeight() const
Definition: box2.h:198
const Vec & GetSize() const
Definition: box2.h:189
const Vec & GetOrigin() const
Definition: box2.h:193

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

1140 {
1141  int vStartIdx[1024]; // fixme: possible overflow
1142 
1143  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ), aRefBypass.CSegment( 0 ), aCoupled, aPair, vStartIdx );
1144  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1145 
1146  int64_t bestLength = -1;
1147  bool found = false;
1148  SHAPE_LINE_CHAIN bestBypass;
1149  int si, ei;
1150 
1151  for( int i=0; i< nStarts; i++ )
1152  {
1153  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1154  {
1155  int delta = std::abs ( vStartIdx[i] - j );
1156 
1157  if( delta > 1 )
1158  {
1159  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1160  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j), dir.IsDiagonal() );
1161 
1162  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1163 
1164  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1165 
1166  si = vStartIdx[i];
1167  ei = j;
1168 
1169  if(si < ei)
1170  newCoupled.Replace( si, ei, bypass );
1171  else
1172  newCoupled.Replace( ei, si, bypass.Reverse() );
1173 
1174  if(coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef, newCoupled) )
1175  {
1176  bestBypass = newCoupled;
1177  bestLength = coupledLength;
1178  found = true;
1179  }
1180  }
1181  }
1182  }
1183 
1184 
1185  if( found )
1186  aNewCoupled = bestBypass;
1187 
1188  return found;
1189 }
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DIRECTION_45.
Definition: direction45.h:37
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
Function CSegment()
SHAPE_LINE_CHAIN.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()

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

◆ dragCornerInternal()

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

Definition at line 444 of file pns_line.cpp.

445 {
446  OPT<SHAPE_LINE_CHAIN> picked;
447  int i;
448  int d = 2;
449 
450  if( aOrigin.SegmentCount() == 1)
451  {
452  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
453 
454  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
455  }
456 
457  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
458  d = 1;
459 
460  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
461  {
462  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
463  VECTOR2I p_start = aOrigin.CPoint( i );
464  SHAPE_LINE_CHAIN paths[2];
465  DIRECTION_45 dirs[2];
466  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
467  int dirCount = 0;
468 
469  for( int j = 0; j < 2; j++ )
470  {
471  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
472 
473  if( paths[j].SegmentCount() < 1 )
474  continue;
475 
476  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
477 
478  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
479  ++dirCount;
480  }
481 
482  for( int j = 0; j < dirCount; j++ )
483  {
484  if( dirs[j] == d_start )
485  {
486  picked = paths[j];
487  break;
488  }
489  }
490 
491  if( picked )
492  break;
493 
494  for( int j = 0; j < dirCount; j++ )
495  {
496  if( dirs[j].IsObtuse( d_prev ) )
497  {
498  picked = paths[j];
499  break;
500  }
501  }
502 
503  if( picked )
504  break;
505  }
506 
507  if( picked )
508  {
509  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
510  path.Append( *picked );
511 
512  return path;
513  }
514 
515  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
516 
517  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
518 }
int Length() const
Function Length()
Definition: seg.h:319
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DIRECTION_45.
Definition: direction45.h:37
int SegmentCount() const
Function SegmentCount()
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
boost::optional< T > OPT
Definition: optional.h:7

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

903 {
904  if( aDefined )
905  {
906  aBox.Merge( aP );
907  }
908  else
909  {
910  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
911  aDefined = true;
912  }
913 }
BOX2< VECTOR2I > BOX2I
Definition: box2.h:522
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: box2.h:386

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

1098 {
1099  int count = 0;
1100  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1101  {
1102  SEG s = aCoupled.CSegment( i );
1103  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1104 
1105  if( s.ApproxParallel ( aOrigSeg ) )
1106  {
1107  int64_t dist = int64_t{(( projOverCoupled - aVertex ).EuclideanNorm())} - aPair->Width();
1108 
1109  if( aPair->GapConstraint().Matches( dist ) )
1110  {
1111  *aIndices++ = i;
1112  count++;
1113  }
1114  }
1115  }
1116 
1117  return count;
1118 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:362
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:265
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:39
const SEG CSegment(int aIndex) const
Function CSegment()

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

1455 {
1456  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1457 
1458  if( !jt )
1459  return nullptr;
1460 
1461  for( ITEM* item : jt->LinkList() )
1462  {
1463  if( item->OfKind( ITEM::VIA_T ) )
1464  {
1465  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1466  return static_cast<VIA*>( item );
1467  }
1468  }
1469 
1470  return nullptr;
1471 }

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

◆ ItemCast()

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

Definition at line 269 of file pns_item.h.

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

◆ makeGapVector()

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

Definition at line 409 of file pns_diff_pair.cpp.

410 {
411  int l = length / 2;
412  VECTOR2I rv;
413 
414  if( dir.EuclideanNorm() == 0 )
415  return dir;
416 
417  do
418  {
419  rv = dir.Resize( l );
420  l++;
421  } while( ( rv * 2 ).EuclideanNorm() < length );
422 
423  return rv;
424 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299

References EuclideanNorm(), VECTOR2< T >::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 148 of file pns_utils.cpp.

149 {
150  int dist;
151 
152  aVertices.NearestPoint( aDiagonal, dist );
153  dist -= HULL_MARGIN;
154  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
155  aDiagonal.A += moveBy;
156  aDiagonal.B += moveBy;
157 }
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
VECTOR2I A
Definition: seg.h:47
VECTOR2I B
Definition: seg.h:48

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  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
44  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
45  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
46  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
47  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
48  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
49  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
50 
51  return s;
52 }
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
SHAPE_LINE_CHAIN.

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

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

◆ operator==()

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

Definition at line 266 of file pns_joint.h.

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

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

Definition at line 331 of file pns_optimizer.cpp.

332 {
333  if( !aL.IsClosed() || aL.SegmentCount() < 3 )
334  return false;
335 
336  // returns 0 if false, +1 if true, -1 if pt ON polygon boundary
337  int result = 0;
338  size_t cnt = aL.PointCount();
339 
340  auto ip = aL.CPoint( 0 );
341 
342  for( size_t i = 1; i <= cnt; ++i )
343  {
344  auto ipNext = (i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ));
345 
346  if( ipNext.y == aP.y )
347  {
348  if( (ipNext.x ==aP.x) || ( ip.y ==aP.y
349  && ( (ipNext.x >aP.x) == (ip.x <aP.x) ) ) )
350  return -1;
351  }
352 
353  if( (ip.y <aP.y) != (ipNext.y <aP.y) )
354  {
355  if( ip.x >=aP.x )
356  {
357  if( ipNext.x >aP.x )
358  result = 1 - result;
359  else
360  {
361  double d = static_cast<double>( ip.x - aP.x ) *
362  static_cast<double>( ipNext.y - aP.y ) -
363  static_cast<double>( ipNext.x - aP.x ) *
364  static_cast<double>( ip.y - aP.y );
365 
366  if( !d )
367  return -1;
368 
369  if( (d > 0) == (ipNext.y > ip.y) )
370  result = 1 - result;
371  }
372  }
373  else
374  {
375  if( ipNext.x >aP.x )
376  {
377  double d = ((double)ip.x -aP.x) * ((double)ipNext.y -aP.y) -
378  ((double)ipNext.x -aP.x) * ((double)ip.y -aP.y);
379 
380  if( !d )
381  return -1;
382 
383  if( (d > 0) == (ipNext.y > ip.y) )
384  result = 1 - result;
385  }
386  }
387  }
388 
389  ip = ipNext;
390  }
391 
392  return result > 0;
393 }
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
bool IsClosed() const override
Function IsClosed()
int SegmentCount() const
Function SegmentCount()

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

114 {
115  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
116  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );
117 
118  const VECTOR2I a = aSeg.GetSeg().A;
119  const VECTOR2I b = aSeg.GetSeg().B;
120 
121  VECTOR2I dir = b - a;
122  VECTOR2I p0 = dir.Perpendicular().Resize( d );
123  VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
124  VECTOR2I pd = dir.Resize( x / 2 );
125  VECTOR2I dp = dir.Resize( d );
126 
128 
129  s.SetClosed( true );
130 
131  s.Append( b + p0 + pd );
132  s.Append( b + dp + ds );
133  s.Append( b + dp - ds );
134  s.Append( b - p0 + pd );
135  s.Append( a - p0 - pd );
136  s.Append( a - dp - ds );
137  s.Append( a - dp + ds );
138  s.Append( a + p0 - pd );
139 
140  // make sure the hull outline is always clockwise
141  if( s.CSegment( 0 ).Side( a ) < 0 )
142  return s.Reverse();
143  else
144  return s;
145 }
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
VECTOR2< T > Perpendicular() const
Function Perpendicular computes the perpendicular vector.
Definition: vector2d.h:320
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
const SEG & GetSeg() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
int GetWidth() const
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:138
VECTOR2I B
Definition: seg.h:48

References SEG::A, SHAPE_LINE_CHAIN::Append(), SEG::B, SHAPE_LINE_CHAIN::CSegment(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::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::SEGMENT::Hull().

◆ shovedArea()

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

Definition at line 1308 of file pns_optimizer.cpp.

1309 {
1310  int64_t area = 0;
1311  const int oc = aOld.PointCount();
1312  const int nc = aNew.PointCount();
1313  const int total = oc + nc;
1314 
1315  for(int i = 0; i < total; i++)
1316  {
1317  int i_next = (i + 1 == total ? 0 : i + 1);
1318 
1319  const VECTOR2I &v0 = ( i < oc ? aOld.CPoint(i) : aNew.CPoint( nc - 1 - (i - oc) ) );
1320  const VECTOR2I &v1 = ( i_next < oc ? aOld.CPoint ( i_next ) : aNew.CPoint( nc - 1 - (i_next - oc) ) );
1321  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1322  }
1323 
1324  return std::abs(area / 2);
1325 }
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()

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

1432 {
1433  LINE tmp;
1434 
1435  if( aNewLine.SegmentCount() < 3 )
1436  return;
1437 
1438  SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1439 
1440  for( int step = 0; step < 3; step++)
1441  {
1442  current.Simplify();
1443 
1444  for( int i = 0; i <= current.SegmentCount() - 3; i++)
1445  {
1446  SHAPE_LINE_CHAIN l_in, l_out;
1447 
1448  l_in = current.Slice(i, i+3);
1449  for( int dir = 0; dir < 1; dir++)
1450  {
1451  if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1452  {
1453  SHAPE_LINE_CHAIN opt = current;
1454  opt.Replace(i, i + 3, l_out);
1455  auto optArea = std::abs(shovedArea( aOldLine, opt ));
1456  auto prevArea = std::abs(shovedArea( aOldLine, current ));
1457 
1458  if( optArea < prevArea )
1459  {
1460  current = opt;
1461  }
1462  break;
1463  }
1464 
1465  }
1466  }
1467 
1468  }
1469 
1470  aOptimized = LINE(aNewLine, current);
1471 
1472  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1473  //dbg->AddLine ( current, 4, 100000 );
1474 }
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
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)
SHAPE_LINE_CHAIN.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()

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

1329 {
1330  SEG a = in.CSegment(0);
1331  SEG center = in.CSegment(1);
1332  SEG b = in.CSegment(2);
1333 
1334  DIRECTION_45 dirA ( a );
1335  DIRECTION_45 dirCenter ( center );
1336  DIRECTION_45 dirB ( b );
1337 
1338  if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1339  return false;
1340 
1341  //VECTOR2I perp = (center.B - center.A).Perpendicular();
1342  VECTOR2I guideA, guideB ;
1343 
1344  SEG guide;
1345  int initial;
1346 
1347  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1348  if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1349  return false;
1350 
1351  {
1352  //auto rC = *a.IntersectLines( b );
1353  // dbg->AddSegment ( SEG( center.A, rC ), 1 );
1354  // dbg->AddSegment ( SEG( center.B, rC ), 2 );
1355  /*
1356  auto perp = dirCenter.Left().Left();
1357 
1358  SEG sperp ( center.A, center.A + perp.ToVector() );
1359 
1360  auto vpc = sperp.LineProject( rC );
1361  auto vpa = sperp.LineProject( a.A );
1362  auto vpb = sperp.LineProject( b.B );
1363 
1364  auto da = (vpc - vpa).EuclideanNorm();
1365  auto db = (vpc - vpb).EuclideanNorm();
1366 
1367  auto vp = (da < db) ? vpa : vpb;
1368  dbg->AddSegment ( SEG( vpc, vp ), 5 );
1369 
1370 
1371  guide = SEG ( vpc, vp );*/
1372 
1373 
1374  }
1375 
1376  int da = a.Length();
1377  int db = b.Length();
1378 
1379  if ( da < db )
1380  guide = a;
1381  else
1382  guide = b;
1383 
1384 
1385  initial = guide.Length();
1386 
1387  int step = initial;
1388  int current = step;
1389  SHAPE_LINE_CHAIN snew;
1390 
1391  while (step > 1)
1392  {
1393  LINE l ( cur );
1394 
1395  snew.Clear();
1396  snew.Append( a.A );
1397  snew.Append( a.B + (a.A - a.B).Resize( current ) );
1398  snew.Append( b.A + (b.B - b.A).Resize( current ) );
1399  snew.Append( b.B );
1400 
1401  step /= 2;
1402 
1403  l.SetShape(snew);
1404  if( aNode->CheckColliding(&l) )
1405  {
1406  current -= step;
1407  } else if ( current + step >= initial ) {
1408  current = initial;
1409  } else {
1410  current += step;
1411  }
1412 
1413 
1414  //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1415  //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1416  //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1417 
1418 
1419  if ( current == initial )
1420  break;
1421 
1422 
1423  }
1424  out = snew;
1425 
1426  //dbg->AddLine ( snew, 3, 100000 );
1427 
1428  return true;
1429 }
int Length() const
Function Length()
Definition: seg.h:319
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
DIRECTION_45.
Definition: direction45.h:37
Definition: seg.h:39
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I B
Definition: seg.h:48

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

1122 {
1123  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1124  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1125 
1126  if( aNode->CheckColliding( &refLine, &coupledLine, ITEM::ANY_T, aPair->Gap() - 10 ) )
1127  return false;
1128 
1129  if( aNode->CheckColliding ( &refLine ) )
1130  return false;
1131 
1132  if( aNode->CheckColliding ( &coupledLine ) )
1133  return false;
1134 
1135  return true;
1136 }

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

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

Variable Documentation

◆ g_dbg

DEBUG_DECORATOR* PNS::g_dbg
static

Definition at line 44 of file pns_optimizer.cpp.

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

◆ 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