26#include <unordered_set>
81 return ( aLeft - aRight ).SquaredEuclideanNorm() <=
SEG::Square( aLimit );
95 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
109 const std::vector<PCB_SHAPE*>& aList,
unsigned aLimit )
114 if( graphic == aShape || ( graphic->GetFlags() &
SKIP_STRUCT ) != 0 )
117 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
130 if( graphic == aShape )
133 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
135 if( d_sq < closest_dist_sq )
137 closest_dist_sq = d_sq;
138 closest_graphic = graphic;
141 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
143 if( d_sq < closest_dist_sq )
145 closest_dist_sq = d_sq;
146 closest_graphic = graphic;
150 return closest_graphic;
156 bool padOutside =
false;
169 padPos.
x, padPos.
y );
176 padPos.
x, padPos.
y );
184 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
188 if( aShapeList.size() == 0 )
191 bool selfIntersecting =
false;
196 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
200 std::map<std::pair<VECTOR2I, VECTOR2I>,
PCB_SHAPE*> shapeOwners;
205 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
206 return it == shapeOwners.end() ? nullptr : it->second;
212 std::vector<SHAPE_LINE_CHAIN> contours;
214 for(
PCB_SHAPE* shape : startCandidates )
217 while( startCandidates.size() )
219 graphic = (
PCB_SHAPE*) *startCandidates.begin();
221 aCleaner.insert( graphic );
222 startCandidates.erase( startCandidates.begin() );
224 contours.emplace_back();
243 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
259 currContour.
Append( arc360, aErrorMax );
263 for(
int ii = 1; ii < currContour.
PointCount(); ++ii )
265 shapeOwners[ std::make_pair( currContour.
CPoint( ii-1 ),
266 currContour.
CPoint( ii ) ) ] = graphic;
269 if( !aAllowUseArcsInPolygons )
283 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
296 currContour.
Append( prevPt );
309 wxASSERT( prevGraphic );
310 (*aErrorHandler)(
_(
"(self-intersecting)" ), prevGraphic, graphic,
314 selfIntersecting =
true;
327 nextPt = graphic->
GetEnd();
331 currContour.
Append( nextPt );
332 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
347 std::swap( pstart, pend );
353 arcChain.
Append( sarc, aErrorMax );
355 if( !aAllowUseArcsInPolygons )
359 for(
int ii = 1; ii < arcChain.
PointCount(); ++ii )
361 shapeOwners[std::make_pair( arcChain.
CPoint( ii - 1 ),
362 arcChain.
CPoint( ii ) )] = graphic;
365 currContour.
Append( arcChain );
376 bool reverse =
false;
382 nextPt = graphic->
GetEnd();
407 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
419 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
434 PCB_SHAPE* nextGraphic =
findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
438 prevGraphic = graphic;
439 graphic = nextGraphic;
441 aCleaner.insert( graphic );
442 startCandidates.erase( graphic );
452 else if( nextGraphic )
455 (*aErrorHandler)(
_(
"(self-intersecting)" ), graphic, nextGraphic,
463 (*aErrorHandler)(
_(
"(not a closed shape)" ), graphic,
nullptr, prevPt );
473 if( !contour.IsClosed() )
478 std::map<int, std::vector<int>> contourToParentIndexesMap;
480 for(
size_t ii = 0; ii < contours.size(); ++ii )
482 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
483 std::vector<int> parents;
485 for(
size_t jj = 0; jj < contours.size(); ++jj )
493 parents.push_back( jj );
496 contourToParentIndexesMap[ii] = std::move( parents );
500 std::map<int, int> contourToOutlineIdxMap;
502 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
504 if( parentIndexes.size() %2 == 0 )
507 if( !aAllowDisjoint && !aPolygons.
IsEmpty() )
512 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
516 (*aErrorHandler)(
_(
"(multiple board outlines not supported)" ), a, b,
517 contours[ contourIndex ].GetPoint( 0 ) );
524 aPolygons.
AddOutline( contours[ contourIndex ] );
525 contourToOutlineIdxMap[ contourIndex ] = aPolygons.
OutlineCount() - 1;
530 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
532 if( parentIndexes.size() %2 == 1 )
538 for(
int parentContourIdx : parentIndexes )
540 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
542 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
543 aPolygons.
AddHole( hole, outlineIdx );
557 for( ++seg2; seg2; seg2++ )
560 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
566 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, ( *seg1 ).A );
569 selfIntersecting =
true;
572 if(
OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(),
true ) )
578 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, *pt );
581 selfIntersecting =
true;
586 return !selfIntersecting;
591 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
597 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
607 int min_dist = std::max( 0, aMinDist );
612 std::vector<PCB_SHAPE*> segList;
614 for(
int ii = 0; ii < items.
GetCount(); ii++ )
619 segList.push_back( seg );
627 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
632 segList.push_back( fpSeg );
639 switch( graphic->GetShape() )
643 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
646 if( dim <= min_dist )
652 (*aErrorHandler)( wxString::Format(
_(
"(Rectangle has null or very small "
655 graphic,
nullptr, graphic->GetStart() );
663 if( graphic->GetRadius() <= min_dist )
669 (*aErrorHandler)( wxString::Format(
_(
"(Circle has null or very small "
671 (
int)graphic->GetRadius() ),
672 graphic,
nullptr, graphic->GetStart() );
680 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
683 if( dim <= min_dist )
689 (*aErrorHandler)( wxString::Format(
_(
"(Segment has null or very small "
690 "length: %d nm)" ), dim ),
691 graphic,
nullptr, graphic->GetStart() );
701 VECTOR2I arcMiddle = graphic->GetArcMid();
702 VECTOR2I seg1 = arcMiddle - graphic->GetStart();
703 VECTOR2I seg2 = graphic->GetEnd() - arcMiddle;
706 if( dim <= min_dist )
712 (*aErrorHandler)( wxString::Format(
_(
"(Arc has null or very small size: %d nm)" ), dim ),
713 graphic,
nullptr, graphic->GetStart() );
737 bool aAllowUseArcsInPolygons )
741 bool success =
false;
748 for(
int ii = 0; ii < items.
GetCount(); ++ii )
756 std::vector<PCB_SHAPE*> fpSegList;
758 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
763 fpSegList.push_back( fpSeg );
766 if( !fpSegList.empty() )
773 nullptr, aAllowUseArcsInPolygons, cleaner );
782 fpHoles.
Append( fpOutlines );
788 for(
int ii = 0; ii < fpItems.
GetCount(); ++ii )
795 std::vector<PCB_SHAPE*> segList;
797 for(
int ii = 0; ii < items.
GetCount(); ii++ )
806 segList.push_back( seg );
812 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
838 aOutlines.
Append( corner );
844 aOutlines.
Append( corner );
905 int aOutlineNum = 0 )
907 int minDistance = -1;
913 int dis = seg.Distance( aEndPoint );
915 if( minDistance < 0 || ( dis < minDistance ) )
918 projPoint = seg.NearestPoint( aEndPoint );
953 if( foundA && foundB )
960 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
968 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
994 bool success =
false;
1002 std::vector<PCB_SHAPE*> segList;
1004 for(
int ii = 0; ii < items.
GetCount(); ii++ )
1006 if( items[ii]->GetLayer() ==
Edge_Cuts )
1007 segList.push_back(
static_cast<PCB_SHAPE*
>( items[ii] ) );
1010 if( !segList.empty() )
1013 aErrorHandler,
false, cleaner );
1037 for(
int j = 0; j < outlines.
HoleCount( i ); j++ )
1042 aOutlines.
AddHole( hole, -1 );
1050 aOutlines = outlines;
1068 std::vector<SHAPE_LINE_CHAIN> closedChains;
1069 std::vector<SHAPE_LINE_CHAIN> openChains;
1073 openChains.push_back( outlines.
Outline( 0 ) );
1075 for(
int j = 0; j < outlines.
HoleCount( 0 ); j++ )
1082 closedChains.push_back( hole );
1087 openChains.push_back( hole );
1121 wxLogTrace(
traceBoardOutline, wxT(
"Only 1 line segment in provided outline" ) );
1123 startSeg = chain.
Segment( 0 );
1131 if( inter0 && inter2 && !inter1 && !inter3 )
1151 else if( inter1 && inter3 && !inter0 && !inter2 )
1174 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects two perpendicular bbox "
1203 else if( hit1 && hit2 )
1222 else if( hit2 && hit3 )
1297 aOutlines.
AddHole( closedChain, -1 );
constexpr EDA_IU_SCALE pcbIUScale
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Information pertinent to a Pcbnew printed circuit board.
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
const FOOTPRINTS & Footprints() const
const Vec & GetOrigin() const
size_type GetHeight() const
size_type GetWidth() const
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
int GetCount() const
Return the number of objects in the list.
A base class for most all the KiCad significant classes used in schematics and boards.
void SetFlags(EDA_ITEM_FLAGS aMask)
void ClearFlags(EDA_ITEM_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
EDA_ITEM_FLAGS GetFlags() const
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
SHAPE_POLY_SET & GetPolyShape()
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
std::vector< VECTOR2I > GetRectCorners() const
const std::vector< VECTOR2I > & GetBezierPoints() const
wxString SHAPE_T_asString() const
VECTOR2I GetArcMid() const
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
int GetWidth() const override
PCB_LAYER_ID GetLayer() const override
Return the primary layer this item is on.
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
void Collect(BOARD_ITEM *aBoard, const std::vector< KICAD_T > &aTypes)
Collect BOARD_ITEM objects using this class's Inspector method, which does the collection.
EDA_ITEM_FLAGS m_flagsToClear
SCOPED_FLAGS_CLEANER(const EDA_ITEM_FLAGS &aFlagsToClear)
VECTOR2I::extended_type ecoord
static SEG::ecoord Square(int a)
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
bool Contains(const SEG &aSeg) const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
virtual const SEG GetSegment(int aIndex) const override
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
void SetWidth(int aWidth)
Set the width of all segments in the chain.
Represent a set of closed polygons.
void RemoveAllContours()
Remove all outlines & holes (clears) the polygon set.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the reference to aHole-th hole in the aIndex-th outline.
int NewOutline()
Creates a new empty polygon in the set and returns its index.
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
int OutlineCount() const
Return the number of outlines in the set.
SHAPE_POLY_SET CloneDropTriangulation() const
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
VECTOR2I projectPointOnSegment(const VECTOR2I &aEndPoint, const SHAPE_POLY_SET &aOutline, int aOutlineNum=0)
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const VECTOR2I &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
Search for a PCB_SHAPE matching a given end point or start point in a list.
static bool isCopperOutside(const FOOTPRINT *aFootprint, SHAPE_POLY_SET &aShape)
bool ConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler, bool aAllowUseArcsInPolygons)
Build a polygon set with holes from a PCB_SHAPE list.
bool TestBoardOutlinesGraphicItems(BOARD *aBoard, int aMinDist, OUTLINE_ERROR_HANDLER *aErrorHandler)
Test a board graphic items on edge cut layer for validity.
void buildBoardBoundingBoxPoly(const BOARD *aBoard, SHAPE_POLY_SET &aOutline)
Get the complete bounding box of the board (including all items).
int findEndSegments(SHAPE_LINE_CHAIN &aChain, SEG &aStartSeg, SEG &aEndSeg)
bool BuildBoardPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler, bool aAllowUseArcsInPolygons)
Extract the board outlines and build a closed polygon from lines, arcs and circle items on edge cut l...
static bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Local and tunable method of qualifying the proximity of two points.
static bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Local method which qualifies whether the start or end point of a segment is closest to a point.
bool BuildFootprintPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
Extract a board outline for a footprint view.
bool doConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler, bool aAllowUseArcsInPolygons, SCOPED_FLAGS_CLEANER &aCleaner)
const std::function< void(const wxString &msg, BOARD_ITEM *itemA, BOARD_ITEM *itemB, const VECTOR2I &pt)> OUTLINE_ERROR_HANDLER
static constexpr EDA_ANGLE ANGLE_360
#define SKIP_STRUCT
flag indicating that the structure should be ignored
std::uint32_t EDA_ITEM_FLAGS
@ ARC
use RECTANGLE instead of RECT to avoid collision in a Windows header
a few functions useful in geometry calculations.
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
This file contains miscellaneous commonly used macros and functions.
#define UNIMPLEMENTED_FOR(type)
std::optional< VECTOR2I > OPT_VECTOR2I
constexpr int mmToIU(double mm) const
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers