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;
171 padPos.
x, padPos.
y );
178 padPos.
x, padPos.
y );
186 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
190 if( aShapeList.size() == 0 )
193 bool selfIntersecting =
false;
198 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
202 std::map<std::pair<VECTOR2I, VECTOR2I>,
PCB_SHAPE*> shapeOwners;
207 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
208 return it == shapeOwners.end() ? nullptr : it->second;
214 std::vector<SHAPE_LINE_CHAIN> contours;
216 for(
PCB_SHAPE* shape : startCandidates )
219 while( startCandidates.size() )
221 graphic = (
PCB_SHAPE*) *startCandidates.begin();
223 aCleaner.insert( graphic );
224 startCandidates.erase( startCandidates.begin() );
226 contours.emplace_back();
245 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
261 currContour.
Append( arc360, aErrorMax );
265 for(
int ii = 1; ii < currContour.
PointCount(); ++ii )
267 shapeOwners[ std::make_pair( currContour.
CPoint( ii-1 ),
268 currContour.
CPoint( ii ) ) ] = graphic;
271 if( !aAllowUseArcsInPolygons )
285 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
298 currContour.
Append( prevPt );
311 wxASSERT( prevGraphic );
312 (*aErrorHandler)(
_(
"(self-intersecting)" ), prevGraphic, graphic,
316 selfIntersecting =
true;
329 nextPt = graphic->
GetEnd();
333 currContour.
Append( nextPt );
334 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
349 std::swap( pstart, pend );
355 arcChain.
Append( sarc, aErrorMax );
359 if( prevGraphic !=
nullptr )
362 if( !aAllowUseArcsInPolygons )
366 for(
int ii = 1; ii < arcChain.
PointCount(); ++ii )
368 shapeOwners[std::make_pair( arcChain.
CPoint( ii - 1 ),
369 arcChain.
CPoint( ii ) )] = graphic;
372 currContour.
Append( arcChain );
383 bool reverse =
false;
389 nextPt = graphic->
GetEnd();
410 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
422 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
437 PCB_SHAPE* nextGraphic =
findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
441 prevGraphic = graphic;
442 graphic = nextGraphic;
444 aCleaner.insert( graphic );
445 startCandidates.erase( graphic );
455 else if( nextGraphic )
458 (*aErrorHandler)(
_(
"(self-intersecting)" ), graphic, nextGraphic,
466 (*aErrorHandler)(
_(
"(not a closed shape)" ), graphic,
nullptr, prevPt );
476 if( !contour.IsClosed() )
481 std::map<int, std::vector<int>> contourToParentIndexesMap;
483 for(
size_t ii = 0; ii < contours.size(); ++ii )
485 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
486 std::vector<int> parents;
488 for(
size_t jj = 0; jj < contours.size(); ++jj )
496 parents.push_back( jj );
499 contourToParentIndexesMap[ii] = std::move( parents );
503 std::map<int, int> contourToOutlineIdxMap;
505 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
507 if( parentIndexes.size() %2 == 0 )
510 if( !aAllowDisjoint && !aPolygons.
IsEmpty() )
515 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
519 (*aErrorHandler)(
_(
"(multiple board outlines not supported)" ), a, b,
520 contours[ contourIndex ].GetPoint( 0 ) );
527 aPolygons.
AddOutline( contours[ contourIndex ] );
528 contourToOutlineIdxMap[ contourIndex ] = aPolygons.
OutlineCount() - 1;
533 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
535 if( parentIndexes.size() %2 == 1 )
541 for(
int parentContourIdx : parentIndexes )
543 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
545 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
546 aPolygons.
AddHole( hole, outlineIdx );
560 for( ++seg2; seg2; seg2++ )
563 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
569 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, ( *seg1 ).A );
572 selfIntersecting =
true;
575 if(
OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(),
true ) )
581 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, *pt );
584 selfIntersecting =
true;
589 return !selfIntersecting;
594 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
600 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
610 int min_dist = std::max( 0, aMinDist );
615 std::vector<PCB_SHAPE*> segList;
617 for(
int ii = 0; ii < items.
GetCount(); ii++ )
622 segList.push_back( seg );
630 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
635 segList.push_back( fpSeg );
642 switch( graphic->GetShape() )
646 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
649 if( dim <= min_dist )
655 (*aErrorHandler)( wxString::Format(
_(
"(rectangle has null or very small "
656 "size: %d nm)" ), dim ),
657 graphic,
nullptr, graphic->GetStart() );
665 int r = graphic->GetRadius();
673 (*aErrorHandler)( wxString::Format(
_(
"(circle has null or very small "
674 "radius: %d nm)" ), r ),
675 graphic,
nullptr, graphic->GetStart() );
683 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
686 if( dim <= min_dist )
692 (*aErrorHandler)( wxString::Format(
_(
"(segment has null or very small "
693 "length: %d nm)" ), dim ),
694 graphic,
nullptr, graphic->GetStart() );
704 VECTOR2I arcMiddle = graphic->GetArcMid();
705 VECTOR2I seg1 = arcMiddle - graphic->GetStart();
706 VECTOR2I seg2 = graphic->GetEnd() - arcMiddle;
709 if( dim <= min_dist )
715 (*aErrorHandler)( wxString::Format(
_(
"(arc has null or very small size: "
717 graphic,
nullptr, graphic->GetStart() );
741 bool aAllowUseArcsInPolygons )
745 bool success =
false;
752 for(
int ii = 0; ii < items.
GetCount(); ++ii )
760 std::vector<PCB_SHAPE*> fpSegList;
762 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
767 fpSegList.push_back( fpSeg );
770 if( !fpSegList.empty() )
777 nullptr, aAllowUseArcsInPolygons, cleaner );
786 fpHoles.
Append( fpOutlines );
792 for(
int ii = 0; ii < fpItems.
GetCount(); ++ii )
799 std::vector<PCB_SHAPE*> segList;
801 for(
int ii = 0; ii < items.
GetCount(); ii++ )
810 segList.push_back( seg );
816 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
842 aOutlines.
Append( corner );
848 aOutlines.
Append( corner );
909 int aOutlineNum = 0 )
911 int minDistance = -1;
917 int dis = seg.
Distance( aEndPoint );
919 if( minDistance < 0 || ( dis < minDistance ) )
922 projPoint = seg.NearestPoint( aEndPoint );
957 if( foundA && foundB )
964 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
972 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
998 bool success =
false;
1006 std::vector<PCB_SHAPE*> segList;
1008 for(
int ii = 0; ii < items.
GetCount(); ii++ )
1010 if( items[ii]->GetLayer() ==
Edge_Cuts )
1011 segList.push_back(
static_cast<PCB_SHAPE*
>( items[ii] ) );
1014 if( !segList.empty() )
1017 aErrorHandler,
false, cleaner );
1041 for(
int j = 0; j < outlines.
HoleCount( i ); j++ )
1046 aOutlines.
AddHole( hole, -1 );
1054 aOutlines = outlines;
1072 std::vector<SHAPE_LINE_CHAIN> closedChains;
1073 std::vector<SHAPE_LINE_CHAIN> openChains;
1077 openChains.push_back( outlines.
Outline( 0 ) );
1079 for(
int j = 0; j < outlines.
HoleCount( 0 ); j++ )
1086 closedChains.push_back( hole );
1091 openChains.push_back( hole );
1125 wxLogTrace(
traceBoardOutline, wxT(
"Only 1 line segment in provided outline" ) );
1127 startSeg = chain.
Segment( 0 );
1135 if( inter0 && inter2 && !inter1 && !inter3 )
1155 else if( inter1 && inter3 && !inter0 && !inter2 )
1178 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects two perpendicular bbox "
1207 else if( hit1 && hit2 )
1226 else if( hit2 && hit3 )
1301 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.
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false, bool aIncludeHiddenText=false) const
Calculate the bounding box containing all board items (or board edge segments).
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
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
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
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)
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
@ 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