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;
160 pad->Padstack().ForEachUniqueLayer(
171 VECTOR2I padPos = pad->GetPosition();
172 wxLogTrace( traceBoardOutline, wxT(
"Tested pad (%d, %d): outside" ),
173 padPos.x, padPos.y );
183 padPos.
x, padPos.
y );
191 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
195 if( aShapeList.size() == 0 )
198 bool selfIntersecting =
false;
203 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
207 std::map<std::pair<VECTOR2I, VECTOR2I>,
PCB_SHAPE*> shapeOwners;
212 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
213 return it == shapeOwners.end() ? nullptr : it->second;
219 std::vector<SHAPE_LINE_CHAIN> contours;
221 for(
PCB_SHAPE* shape : startCandidates )
224 while( startCandidates.size() )
226 graphic = (
PCB_SHAPE*) *startCandidates.begin();
228 aCleaner.insert( graphic );
229 startCandidates.erase( startCandidates.begin() );
231 contours.emplace_back();
250 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
266 currContour.
Append( arc360, aErrorMax );
270 for(
int ii = 1; ii < currContour.
PointCount(); ++ii )
272 shapeOwners[ std::make_pair( currContour.
CPoint( ii-1 ),
273 currContour.
CPoint( ii ) ) ] = graphic;
276 if( !aAllowUseArcsInPolygons )
290 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
303 currContour.
Append( prevPt );
316 wxASSERT( prevGraphic );
317 (*aErrorHandler)(
_(
"(self-intersecting)" ), prevGraphic, graphic,
321 selfIntersecting =
true;
334 nextPt = graphic->
GetEnd();
338 currContour.
Append( nextPt );
339 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
354 std::swap( pstart, pend );
360 arcChain.
Append( sarc, aErrorMax );
364 if( prevGraphic !=
nullptr )
367 if( !aAllowUseArcsInPolygons )
371 for(
int ii = 1; ii < arcChain.
PointCount(); ++ii )
373 shapeOwners[std::make_pair( arcChain.
CPoint( ii - 1 ),
374 arcChain.
CPoint( ii ) )] = graphic;
377 currContour.
Append( arcChain );
388 bool reverse =
false;
394 nextPt = graphic->
GetEnd();
415 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
427 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
442 PCB_SHAPE* nextGraphic =
findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
446 prevGraphic = graphic;
447 graphic = nextGraphic;
449 aCleaner.insert( graphic );
450 startCandidates.erase( graphic );
460 else if( nextGraphic )
463 (*aErrorHandler)(
_(
"(self-intersecting)" ), graphic, nextGraphic,
471 (*aErrorHandler)(
_(
"(not a closed shape)" ), graphic,
nullptr, prevPt );
481 if( !contour.IsClosed() )
486 std::map<int, std::vector<int>> contourToParentIndexesMap;
488 for(
size_t ii = 0; ii < contours.size(); ++ii )
490 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
491 std::vector<int> parents;
493 for(
size_t jj = 0; jj < contours.size(); ++jj )
501 parents.push_back( jj );
504 contourToParentIndexesMap[ii] = std::move( parents );
508 std::map<int, int> contourToOutlineIdxMap;
510 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
512 if( parentIndexes.size() %2 == 0 )
515 if( !aAllowDisjoint && !aPolygons.
IsEmpty() )
520 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
524 (*aErrorHandler)(
_(
"(multiple board outlines not supported)" ), a, b,
525 contours[ contourIndex ].GetPoint( 0 ) );
532 aPolygons.
AddOutline( contours[ contourIndex ] );
533 contourToOutlineIdxMap[ contourIndex ] = aPolygons.
OutlineCount() - 1;
538 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
540 if( parentIndexes.size() %2 == 1 )
546 for(
int parentContourIdx : parentIndexes )
548 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
550 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
551 aPolygons.
AddHole( hole, outlineIdx );
565 for( ++seg2; seg2; seg2++ )
568 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
574 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, ( *seg1 ).A );
577 selfIntersecting =
true;
580 if(
OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(),
true ) )
586 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, *pt );
589 selfIntersecting =
true;
594 return !selfIntersecting;
599 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
605 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
615 int min_dist = std::max( 0, aMinDist );
620 std::vector<PCB_SHAPE*> shapeList;
622 for(
int ii = 0; ii < items.
GetCount(); ii++ )
627 shapeList.push_back( seg );
633 switch( shape->GetShape() )
637 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
640 if( dim <= min_dist )
646 (*aErrorHandler)( wxString::Format(
_(
"(rectangle has null or very small "
647 "size: %d nm)" ), dim ),
648 shape,
nullptr, shape->GetStart() );
656 int r = shape->GetRadius();
664 (*aErrorHandler)( wxString::Format(
_(
"(circle has null or very small "
665 "radius: %d nm)" ), r ),
666 shape,
nullptr, shape->GetStart() );
674 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
677 if( dim <= min_dist )
683 (*aErrorHandler)( wxString::Format(
_(
"(segment has null or very small "
684 "length: %d nm)" ), dim ),
685 shape,
nullptr, shape->GetStart() );
695 VECTOR2I arcMiddle = shape->GetArcMid();
696 VECTOR2I seg1 = arcMiddle - shape->GetStart();
697 VECTOR2I seg2 = shape->GetEnd() - arcMiddle;
700 if( dim <= min_dist )
706 (*aErrorHandler)( wxString::Format(
_(
"(arc has null or very small size: "
708 shape,
nullptr, shape->GetStart() );
732 bool aAllowUseArcsInPolygons )
736 bool success =
false;
743 for(
int ii = 0; ii < items.
GetCount(); ++ii )
751 std::vector<PCB_SHAPE*> fpSegList;
753 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
758 fpSegList.push_back( fpSeg );
761 if( !fpSegList.empty() )
768 nullptr, aAllowUseArcsInPolygons, cleaner );
777 fpHoles.
Append( fpOutlines );
783 for(
int ii = 0; ii < fpItems.
GetCount(); ++ii )
790 std::vector<PCB_SHAPE*> segList;
792 for(
int ii = 0; ii < items.
GetCount(); ii++ )
801 segList.push_back( seg );
807 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
833 aOutlines.
Append( corner );
839 aOutlines.
Append( corner );
900 int aOutlineNum = 0 )
902 int minDistance = -1;
908 int dis = seg.
Distance( aEndPoint );
910 if( minDistance < 0 || ( dis < minDistance ) )
913 projPoint = seg.NearestPoint( aEndPoint );
948 if( foundA && foundB )
955 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
963 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
989 bool success =
false;
997 std::vector<PCB_SHAPE*> segList;
999 for(
int ii = 0; ii < items.
GetCount(); ii++ )
1001 if( items[ii]->GetLayer() ==
Edge_Cuts )
1002 segList.push_back(
static_cast<PCB_SHAPE*
>( items[ii] ) );
1005 if( !segList.empty() )
1008 aErrorHandler,
false, cleaner );
1032 for(
int j = 0; j < outlines.
HoleCount( i ); j++ )
1037 aOutlines.
AddHole( hole, -1 );
1045 aOutlines = outlines;
1063 std::vector<SHAPE_LINE_CHAIN> closedChains;
1064 std::vector<SHAPE_LINE_CHAIN> openChains;
1068 openChains.push_back( outlines.
Outline( 0 ) );
1070 for(
int j = 0; j < outlines.
HoleCount( 0 ); j++ )
1077 closedChains.push_back( hole );
1082 openChains.push_back( hole );
1116 wxLogTrace(
traceBoardOutline, wxT(
"Only 1 line segment in provided outline" ) );
1118 startSeg = chain.
Segment( 0 );
1126 if( inter0 && inter2 && !inter1 && !inter3 )
1146 else if( inter1 && inter3 && !inter0 && !inter2 )
1169 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects two perpendicular bbox "
1198 else if( hit1 && hit2 )
1217 else if( hit2 && hit3 )
1292 aOutlines.
AddHole( closedChain, -1 );
constexpr int ARC_HIGH_DEF
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
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr const Vec GetEnd() const
constexpr size_type GetWidth() const
constexpr size_type GetHeight() const
constexpr const Vec & GetOrigin() const
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
SHAPE_POLY_SET & GetPolyShape()
void RebuildBezierToSegmentsPointsList(int aMaxError)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
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 Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the 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.
void ClearArcs()
Removes all arc references from all the outlines and holes in the polyset.
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
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.
void BooleanIntersection(const SHAPE_POLY_SET &b)
Perform boolean polyset intersection.
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)
double Distance(const VECTOR2< extended_type > &aVector) const
Compute the distance between two vectors.
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
@ RECTANGLE
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.
PCB_LAYER_ID
A quick note on layer IDs:
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