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...
 
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  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  PRESERVE_VERTEX_CONSTRAINT
 
class  ROUTER
 
class  ROUTER_IFACE
 ROUTER. More...
 
class  ROUTING_SETTINGS
 ROUTING_SETTINGS. More...
 
class  RULE_RESOLVER
 RULE_RESOLVER. More...
 
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 ) }
 
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  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, LINE cur, SHAPE_LINE_CHAIN in, SHAPE_LINE_CHAIN &out)
 
void Tighten (NODE *aNode, SHAPE_LINE_CHAIN &aOldLine, LINE &aNewLine, LINE &aOptimized)
 
static VIAfindViaByHandle (NODE *aNode, const VIA_HANDLE &handle)
 
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

◆ DRAG_MODE

Enumerator
DM_CORNER 
DM_SEGMENT 
DM_VIA 
DM_FREE_ANGLE 
DM_ARC 
DM_ANY 
DM_COMPONENT 

Definition at line 75 of file pns_router.h.

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

◆ LineMarker

Enumerator
MK_HEAD 
MK_VIOLATION 
MK_LOCKED 
MK_DP_COUPLED 

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

◆ 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 67 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(), DIMENSION::AdjustDimensionDetails(), EC_45DEGREE::Apply(), EC_CIRCLE::Apply(), HPGL_PLOTTER::Arc(), GEOM_TEST::ArePerpendicular(), BuildCornersList_S_Shape(), PNS::DP_GATEWAYS::BuildGeneric(), D_PAD::BuildPadPolygon(), PNS::OPTIMIZER::circleBreakouts(), DRAWSEGMENT::computeArcBBox(), ConvertOutlineToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), D_CODE::ConvertShapeToPolygon(), PCB_EDIT_FRAME::Create_MuWaveComponent(), SCH_GLOBALLABEL::CreateGraphicShape(), PNS::OPTIMIZER::customBreakouts(), DRC::doTrackDrc(), KIGFX::PCB_PAINTER::draw(), DRAWING_TOOL::DrawDimension(), ROUTER_PREVIEW_ITEM::drawLineChain(), AR_MATRIX::drawSegmentQcq(), GBR_TO_PCB_EXPORTER::export_non_copper_item(), export_vrml_line(), DSN::SPECCTRA_DB::FromBOARD(), C3D_RENDER_OGL_LEGACY::generate_ring_contour(), TEXTE_MODULE::GetBoundingBox(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetStartAngle(), KIGFX::PREVIEW::ARC_GEOM_MANAGER::GetSubtended(), ARRAY_CIRCULAR_OPTIONS::GetTransform(), GRCSegm(), PNS::LINE_PLACER::handlePullback(), idf_export_module(), DIALOG_PAD_PROPERTIES::initValues(), DXF_IMPORT_PLUGIN::insertArc(), PNS::LINE::Is45Degree(), LEGACY_PLUGIN::loadMODULE_EDGE(), LEGACY_PLUGIN::loadPCB_LINE(), LEGACY_PLUGIN::loadPCB_TEXT(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), DSN::SPECCTRA_DB::makeIMAGE(), EAGLE_PLUGIN::packagePolygon(), SHAPE_LINE_CHAIN::Parse(), GPCB_FPL_CACHE::parseMODULE(), D_PAD::PrintShape(), processComp(), processSolid(), ZONE_CONTAINER::Rotate(), AR_AUTOPLACER::rotateModule(), RotatePoint(), SCH_SEXPR_PLUGIN::saveSymbol(), TEXTE_MODULE::SetDrawCoord(), D_PAD::SetDrawCoord(), EDGE_MODULE::SetLocalCoord(), TEXTE_MODULE::SetLocalCoord(), AR_MATRIX::traceArc(), AR_MATRIX::traceCircle(), AR_MATRIX::TraceFilledRectangle(), TransformCircleToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), TEXTE_MODULE::ViewBBox(), and ROUTER_PREVIEW_ITEM::ViewDraw().

◆ 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
Definition: shape_segment.h:72
VECTOR2I A
Definition: seg.h:47
int GetWidth() const
Definition: shape_segment.h:82
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()
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:89
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:274
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:133

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

◆ 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 }
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

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

1184 {
1185  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1186 
1187  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1188 }

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:202
static const int dist[10][10]
Definition: ar_matrix.cpp:326
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

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

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

◆ clipToLoopStart()

bool PNS::clipToLoopStart ( SHAPE_LINE_CHAIN l)

Definition at line 156 of file pns_walkaround.cpp.

157 {
158  auto ip = l.SelfIntersecting();
159 
160  if(!ip)
161  return false;
162  else {
163  int pidx = l.Split( ip->p );
164  auto lead = l.Slice(0, pidx);
165  auto tail = l.Slice(pidx + 1, -1);
166 
167  int pidx2 = tail.Split( ip->p );
168 
169  auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
170  dbg->AddPoint( ip->p, 5 );
171 
172  l = lead;
173  l.Append( tail.Slice( 0, pidx2 ) );
174  //l = l.Slice(0, pidx);
175  return true;
176  }
177 
178 
179 }
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 271 of file pns_item.h.

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

Referenced by PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::SHOVE::pushOrShoveVia(), 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:128
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:392
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:319
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:359
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:386
Definition: seg.h:39
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:84
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:189
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:186
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_simple.h:74
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:196
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:128
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:125
Definition: seg.h:39
coord_type GetY() const
Definition: box2.h:190
SHAPE_LINE_CHAIN.
coord_type GetHeight() const
Definition: box2.h:197
const Vec & GetSize() const
Definition: box2.h:188
const Vec & GetOrigin() const
Definition: box2.h:192

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

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

1131 {
1132  int vStartIdx[1024]; // fixme: possible overflow
1133 
1134  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ), aRefBypass.CSegment( 0 ), aCoupled, aPair, vStartIdx );
1135  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1136 
1137  int64_t bestLength = -1;
1138  bool found = false;
1139  SHAPE_LINE_CHAIN bestBypass;
1140  int si, ei;
1141 
1142  for( int i=0; i< nStarts; i++ )
1143  {
1144  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1145  {
1146  int delta = std::abs ( vStartIdx[i] - j );
1147 
1148  if( delta > 1 )
1149  {
1150  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1151  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j), dir.IsDiagonal() );
1152 
1153  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1154 
1155  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1156 
1157  si = vStartIdx[i];
1158  ei = j;
1159 
1160  if(si < ei)
1161  newCoupled.Replace( si, ei, bypass );
1162  else
1163  newCoupled.Replace( ei, si, bypass.Reverse() );
1164 
1165  if(coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef, newCoupled) )
1166  {
1167  bestBypass = newCoupled;
1168  bestLength = coupledLength;
1169  found = true;
1170  }
1171  }
1172  }
1173  }
1174 
1175 
1176  if( found )
1177  aNewCoupled = bestBypass;
1178 
1179  return found;
1180 }
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 478 of file pns_line.cpp.

479 {
480  OPT<SHAPE_LINE_CHAIN> picked;
481  int i;
482  int d = 2;
483 
484  if( aOrigin.SegmentCount() == 1)
485  {
486  DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
487 
488  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
489  }
490 
491  if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
492  d = 1;
493 
494  for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
495  {
496  DIRECTION_45 d_start( aOrigin.CSegment( i ) );
497  VECTOR2I p_start = aOrigin.CPoint( i );
498  SHAPE_LINE_CHAIN paths[2];
499  DIRECTION_45 dirs[2];
500  DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) ) : DIRECTION_45() );
501  int dirCount = 0;
502 
503  for( int j = 0; j < 2; j++ )
504  {
505  paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
506 
507  if( paths[j].SegmentCount() < 1 )
508  continue;
509 
510  assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
511 
512  dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
513  ++dirCount;
514  }
515 
516  for( int j = 0; j < dirCount; j++ )
517  {
518  if( dirs[j] == d_start )
519  {
520  picked = paths[j];
521  break;
522  }
523  }
524 
525  if( picked )
526  break;
527 
528  for( int j = 0; j < dirCount; j++ )
529  {
530  if( dirs[j].IsObtuse( d_prev ) )
531  {
532  picked = paths[j];
533  break;
534  }
535  }
536 
537  if( picked )
538  break;
539  }
540 
541  if( picked )
542  {
543  SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
544  path.Append( *picked );
545 
546  return path;
547  }
548 
549  DIRECTION_45 dir( aOrigin.CPoint( -1 ) - aOrigin.CPoint( -2 ) );
550 
551  return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
552 }
int Length() const
Function Length()
Definition: seg.h:314
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 942 of file pns_line.cpp.

943 {
944  if( aDefined )
945  {
946  aBox.Merge( aP );
947  }
948  else
949  {
950  aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
951  aDefined = true;
952  }
953 }
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
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:385

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

1089 {
1090  int count = 0;
1091  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1092  {
1093  SEG s = aCoupled.CSegment( i );
1094  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1095 
1096  if( s.ApproxParallel ( aOrigSeg ) )
1097  {
1098  int64_t dist = ( projOverCoupled - aVertex ).EuclideanNorm() - aPair->Width();
1099 
1100  if( aPair->GapConstraint().Matches( dist ) )
1101  {
1102  *aIndices++ = i;
1103  count++;
1104  }
1105  }
1106  }
1107 
1108  return count;
1109 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
static const int dist[10][10]
Definition: ar_matrix.cpp:326
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:359
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:260
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:39
const SEG CSegment(int aIndex) const
Function CSegment()

References SEG::ApproxParallel(), SHAPE_LINE_CHAIN::CSegment(), dist, 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 1431 of file pns_shove.cpp.

1432 {
1433  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1434 
1435  if( !jt )
1436  return nullptr;
1437 
1438  for( ITEM* item : jt->LinkList() )
1439  {
1440  if ( item->OfKind( ITEM::VIA_T ))
1441  {
1442  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1443  return static_cast<VIA*>( item );
1444  }
1445  }
1446 
1447  return nullptr;
1448 }

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

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

◆ makeGapVector()

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

Definition at line 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:128
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
static const int dist[10][10]
Definition: ar_matrix.cpp:326
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, dist, 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 PNS::SOLID::Hull(), 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 326 of file pns_optimizer.cpp.

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

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
Definition: shape_segment.h:72
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
Definition: shape_segment.h:82
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:133
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 PNS::SOLID::Hull(), and PNS::SEGMENT::Hull().

◆ shovedArea()

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

Definition at line 1299 of file pns_optimizer.cpp.

1300 {
1301  int64_t area = 0;
1302  const int oc = aOld.PointCount();
1303  const int nc = aNew.PointCount();
1304  const int total = oc + nc;
1305 
1306  for(int i = 0; i < total; i++)
1307  {
1308  int i_next = (i + 1 == total ? 0 : i + 1);
1309 
1310  const VECTOR2I &v0 = ( i < oc ? aOld.CPoint(i) : aNew.CPoint( nc - 1 - (i - oc) ) );
1311  const VECTOR2I &v1 = ( i_next < oc ? aOld.CPoint ( i_next ) : aNew.CPoint( nc - 1 - (i_next - oc) ) );
1312  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1313  }
1314 
1315  return std::abs(area / 2);
1316 }
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,
SHAPE_LINE_CHAIN aOldLine,
LINE aNewLine,
LINE aOptimized 
)

Definition at line 1427 of file pns_optimizer.cpp.

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

Definition at line 1318 of file pns_optimizer.cpp.

1319 {
1320  SEG a = in.CSegment(0);
1321  SEG center = in.CSegment(1);
1322  SEG b = in.CSegment(2);
1323 
1324  DIRECTION_45 dirA ( a );
1325  DIRECTION_45 dirCenter ( center );
1326  DIRECTION_45 dirB ( b );
1327 
1328  if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1329  return false;
1330 
1331  //VECTOR2I perp = (center.B - center.A).Perpendicular();
1332  VECTOR2I guideA, guideB ;
1333 
1334  SEG guide;
1335  int initial;
1336 
1337  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1338  if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1339  return false;
1340 
1341  {
1342  //auto rC = *a.IntersectLines( b );
1343  // dbg->AddSegment ( SEG( center.A, rC ), 1 );
1344  // dbg->AddSegment ( SEG( center.B, rC ), 2 );
1345  /*
1346  auto perp = dirCenter.Left().Left();
1347 
1348  SEG sperp ( center.A, center.A + perp.ToVector() );
1349 
1350  auto vpc = sperp.LineProject( rC );
1351  auto vpa = sperp.LineProject( a.A );
1352  auto vpb = sperp.LineProject( b.B );
1353 
1354  auto da = (vpc - vpa).EuclideanNorm();
1355  auto db = (vpc - vpb).EuclideanNorm();
1356 
1357  auto vp = (da < db) ? vpa : vpb;
1358  dbg->AddSegment ( SEG( vpc, vp ), 5 );
1359 
1360 
1361  guide = SEG ( vpc, vp );*/
1362 
1363 
1364  }
1365 
1366  int da = a.Length();
1367  int db = b.Length();
1368 
1369  if ( da < db )
1370  guide = a;
1371  else
1372  guide = b;
1373 
1374 
1375  initial = guide.Length();
1376 
1377  int step = initial;
1378  int current = step;
1379  //printf("step %d\n", step);
1380  SHAPE_LINE_CHAIN snew;
1381 
1382  while (step > 1)
1383  {
1384  LINE l ( cur );
1385 
1386 
1387  //printf("current %d l %d\n", current, guide.Length() );
1388  snew.Clear();
1389  snew.Append( a.A );
1390  snew.Append( a.B + (a.A - a.B).Resize( current ) );
1391  snew.Append( b.A + (b.B - b.A).Resize( current ) );
1392  snew.Append( b.B );
1393 
1394  step /= 2;
1395 
1396  l.SetShape(snew);
1397  if( aNode->CheckColliding(&l) )
1398  {
1399  current -= step;
1400  } else if ( current + step >= initial ) {
1401  current = initial;
1402  } else {
1403  current += step;
1404  }
1405 
1406 
1407  //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1408  //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1409  //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1410 
1411 
1412  if ( current == initial )
1413  break;
1414 
1415 
1416  }
1417  out = snew;
1418 
1419  //dbg->AddLine ( snew, 3, 100000 );
1420 
1421 
1422  return true;
1423 
1424 
1425 }
int Length() const
Function Length()
Definition: seg.h:314
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 1112 of file pns_optimizer.cpp.

1113 {
1114  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1115  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1116 
1117  if( aNode->CheckColliding( &refLine, &coupledLine, ITEM::ANY_T, aPair->Gap() - 10 ) )
1118  return false;
1119 
1120  if( aNode->CheckColliding ( &refLine ) )
1121  return false;
1122 
1123  if( aNode->CheckColliding ( &coupledLine ) )
1124  return false;
1125 
1126  return true;
1127 }

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