26#include <unordered_set>
43#include <nanoflann.hpp>
83 return ( aLeft - aRight ).SquaredEuclideanNorm() <=
SEG::Square( aLimit );
97 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
103 bool padOutside =
false;
107 pad->Padstack().ForEachUniqueLayer(
118 VECTOR2I padPos = pad->GetPosition();
119 wxLogTrace( traceBoardOutline, wxT(
"Tested pad (%d, %d): outside" ),
120 padPos.x, padPos.y );
130 padPos.
x, padPos.
y );
147 endpoints.emplace_back( shape->GetStart(), shape );
148 endpoints.emplace_back( shape->GetEnd(), shape );
159 return static_cast<double>(
endpoints[idx].first.x );
161 return static_cast<double>(
endpoints[idx].first.y );
164 template <
class BBOX>
171using KDTree = nanoflann::KDTreeSingleIndexAdaptor<nanoflann::L2_Simple_Adaptor<double, PCB_SHAPE_ENDPOINTS_ADAPTOR>,
179 const double query_pt[2] = {
static_cast<double>( aPoint.
x ),
static_cast<double>( aPoint.
y ) };
182 std::vector<nanoflann::ResultItem<size_t, double>> matches;
183 double search_radius_sq =
static_cast<double>( aLimit * aLimit );
184 nanoflann::RadiusResultSet<double, size_t> radiusResultSet( search_radius_sq, matches );
186 kdTree.findNeighbors( radiusResultSet, query_pt );
188 if( matches.empty() )
193 double closest_dist_sq = search_radius_sq;
195 for(
const auto& match : matches )
199 if( candidate == aShape )
204 closest_dist_sq = match.second;
205 closest_graphic = candidate;
209 return closest_graphic;
213 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
217 if( aShapeList.size() == 0 )
220 bool selfIntersecting =
false;
223 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
227 KDTree kdTree( 2, adaptor, nanoflann::KDTreeSingleIndexAdaptorParams( 10 ) );
231 std::map<std::pair<VECTOR2I, VECTOR2I>,
PCB_SHAPE*> shapeOwners;
236 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
237 return it == shapeOwners.end() ? nullptr : it->second;
243 std::vector<SHAPE_LINE_CHAIN> contours;
244 contours.reserve( startCandidates.size() );
246 for(
PCB_SHAPE* shape : startCandidates )
249 while( startCandidates.size() )
251 graphic = (
PCB_SHAPE*) *startCandidates.begin();
253 aCleaner.insert( graphic );
254 startCandidates.erase( startCandidates.begin() );
256 contours.emplace_back();
275 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
291 currContour.
Append( arc360, aErrorMax );
295 for(
int ii = 1; ii < currContour.
PointCount(); ++ii )
297 shapeOwners[ std::make_pair( currContour.
CPoint( ii-1 ),
298 currContour.
CPoint( ii ) ) ] = graphic;
301 if( !aAllowUseArcsInPolygons )
315 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
328 currContour.
Append( prevPt );
341 wxASSERT( prevGraphic );
342 (*aErrorHandler)(
_(
"(self-intersecting)" ), prevGraphic, graphic,
346 selfIntersecting =
true;
359 nextPt = graphic->
GetEnd();
363 currContour.
Append( nextPt );
364 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
379 std::swap( pstart, pend );
388 arcChain.
Append( sarc, aErrorMax );
390 if( !aAllowUseArcsInPolygons )
394 for(
int ii = 1; ii < arcChain.
PointCount(); ++ii )
396 shapeOwners[std::make_pair( arcChain.
CPoint( ii - 1 ),
397 arcChain.
CPoint( ii ) )] = graphic;
400 currContour.
Append( arcChain );
411 bool reverse =
false;
417 nextPt = graphic->
GetEnd();
438 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
450 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
464 PCB_SHAPE* nextGraphic =
findNext( graphic, prevPt, kdTree, adaptor, aChainingEpsilon );
468 prevGraphic = graphic;
469 graphic = nextGraphic;
471 aCleaner.insert( graphic );
472 startCandidates.erase( graphic );
479 if( startPt != prevPt && currContour.
PointCount() > 2 )
493 arcChain.
Append( sarc, aErrorMax );
495 if( !aAllowUseArcsInPolygons )
499 for(
int ii = 1; ii < arcChain.
PointCount(); ++ii )
501 shapeOwners[std::make_pair( arcChain.
CPoint( ii - 1 ),
502 arcChain.
CPoint( ii ) )] = owner;
506 currContour.
Append( arcChain );
511 currContour.
SetPoint( -1, startPt );
513 shapeOwners[std::make_pair( currContour.
CPoints()[currContour.
PointCount() - 2 ],
523 else if( nextGraphic )
526 (*aErrorHandler)(
_(
"(self-intersecting)" ), graphic, nextGraphic,
534 (*aErrorHandler)(
_(
"(not a closed shape)" ), graphic,
nullptr, prevPt );
544 if( !contour.IsClosed() )
548 std::map<int, std::vector<int>> contourToParentIndexesMap;
550 for(
size_t ii = 0; ii < contours.size(); ++ii )
558 for(
size_t ii = 0; ii < contours.size(); ++ii )
560 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
561 std::vector<int> parents;
563 for(
size_t jj = 0; jj < contours.size(); ++jj )
570 if( parentCandidate.
PointInside( firstPt, 0,
true ) )
571 parents.push_back( jj );
574 contourToParentIndexesMap[ii] = std::move( parents );
578 std::map<int, int> contourToOutlineIdxMap;
580 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
582 if( parentIndexes.size() %2 == 0 )
585 if( !aAllowDisjoint && !aPolygons.
IsEmpty() )
590 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
594 (*aErrorHandler)(
_(
"(multiple board outlines not supported)" ), a, b,
595 contours[ contourIndex ].GetPoint( 0 ) );
602 aPolygons.
AddOutline( contours[ contourIndex ] );
603 contourToOutlineIdxMap[ contourIndex ] = aPolygons.
OutlineCount() - 1;
608 for(
const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
610 if( parentIndexes.size() %2 == 1 )
616 for(
int parentContourIdx : parentIndexes )
618 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
620 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
621 aPolygons.
AddHole( hole, outlineIdx );
631 std::vector<SEG> segments;
639 for(
int jj = 0; jj < aPolygons.
HoleCount( ii ); ++jj )
646 segments.reserve( total );
655 std::swap( segment.
A, segment.
B );
658 segments.push_back( segment );
661 std::sort( segments.begin(), segments.end(),
662 [](
const SEG& a,
const SEG& b )
665 return LexicographicalCompare( a.A, b.A ) < 0;
667 return LexicographicalCompare( a.B, b.B ) < 0;
670 for(
size_t i = 0; i < segments.size(); ++i )
672 const SEG& seg1 = segments[i];
674 for(
size_t j = i + 1; j < segments.size(); ++j )
676 const SEG& seg2 = segments[j];
678 if( seg2.
A > seg1.
B )
685 if( seg1 == seg2 || ( seg1.
A == seg2.
B && seg1.
B == seg2.
A ) )
691 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, seg1.
A );
694 selfIntersecting =
true;
702 (*aErrorHandler)(
_(
"(self-intersecting)" ), a, b, *pt );
705 selfIntersecting =
true;
710 return !selfIntersecting;
715 int aErrorMax,
int aChainingEpsilon,
bool aAllowDisjoint,
721 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
731 int min_dist = std::max( 0, aMinDist );
736 std::vector<PCB_SHAPE*> shapeList;
738 for(
int ii = 0; ii < items.
GetCount(); ii++ )
743 shapeList.push_back( seg );
749 switch( shape->GetShape() )
753 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
756 if( dim <= min_dist )
762 (*aErrorHandler)( wxString::Format(
_(
"(rectangle has null or very small "
763 "size: %d nm)" ), dim ),
764 shape,
nullptr, shape->GetStart() );
772 int r = shape->GetRadius();
780 (*aErrorHandler)( wxString::Format(
_(
"(circle has null or very small "
781 "radius: %d nm)" ), r ),
782 shape,
nullptr, shape->GetStart() );
790 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
793 if( dim <= min_dist )
799 (*aErrorHandler)( wxString::Format(
_(
"(segment has null or very small "
800 "length: %d nm)" ), dim ),
801 shape,
nullptr, shape->GetStart() );
811 VECTOR2I arcMiddle = shape->GetArcMid();
812 VECTOR2I seg1 = arcMiddle - shape->GetStart();
813 VECTOR2I seg2 = shape->GetEnd() - arcMiddle;
816 if( dim <= min_dist )
822 (*aErrorHandler)( wxString::Format(
_(
"(arc has null or very small size: "
824 shape,
nullptr, shape->GetStart() );
848 bool aAllowUseArcsInPolygons )
852 bool success =
false;
859 for(
int ii = 0; ii < items.
GetCount(); ++ii )
867 std::vector<PCB_SHAPE*> fpSegList;
869 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
874 fpSegList.push_back( fpSeg );
877 if( !fpSegList.empty() )
884 nullptr, aAllowUseArcsInPolygons, cleaner );
893 fpHoles.
Append( fpOutlines );
899 for(
int ii = 0; ii < fpItems.
GetCount(); ++ii )
906 std::vector<PCB_SHAPE*> segList;
908 for(
int ii = 0; ii < items.
GetCount(); ii++ )
917 segList.push_back( seg );
923 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
949 aOutlines.
Append( corner );
955 aOutlines.
Append( corner );
1016 int aOutlineNum = 0 )
1018 int minDistance = -1;
1023 auto seg = it.Get();
1024 int dis = seg.
Distance( aEndPoint );
1026 if( minDistance < 0 || ( dis < minDistance ) )
1029 projPoint = seg.NearestPoint( aEndPoint );
1045 bool foundA =
false;
1046 bool foundB =
false;
1064 if( foundA && foundB )
1067 if( foundSegs == 0 )
1071 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
1079 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
1105 bool success =
false;
1113 std::vector<PCB_SHAPE*> segList;
1115 for(
int ii = 0; ii < items.
GetCount(); ii++ )
1117 if( items[ii]->GetLayer() ==
Edge_Cuts )
1118 segList.push_back(
static_cast<PCB_SHAPE*
>( items[ii] ) );
1121 if( !segList.empty() )
1124 aErrorHandler,
false, cleaner );
1148 for(
int j = 0; j < outlines.
HoleCount( i ); j++ )
1153 aOutlines.
AddHole( hole, -1 );
1161 aOutlines = std::move( outlines );
1179 std::vector<SHAPE_LINE_CHAIN> closedChains;
1180 std::vector<SHAPE_LINE_CHAIN> openChains;
1184 openChains.push_back( outlines.
Outline( 0 ) );
1186 for(
int j = 0; j < outlines.
HoleCount( 0 ); j++ )
1193 closedChains.push_back( hole );
1198 openChains.push_back( hole );
1225 aOutlines = std::move( bbox );
1232 wxLogTrace(
traceBoardOutline, wxT(
"Only 1 line segment in provided outline" ) );
1242 if( inter0 && inter2 && !inter1 && !inter3 )
1245 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects only vertical bbox sides" ) );
1261 else if( inter1 && inter3 && !inter0 && !inter2 )
1264 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects only horizontal bbox sides" ) );
1283 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects two perpendicular bbox sides" ) );
1311 else if( hit1 && hit2 )
1330 else if( hit2 && hit3 )
1376 aOutlines = std::move( bbox );
1393 aOutlines = std::move( poly2 );
1398 aOutlines = std::move( poly1 );
1405 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
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
constexpr bool IsValid() 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)
bool HasFlag(EDA_ITEM_FLAGS aFlag) const
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)
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
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
const VECTOR2I & GetArcMid() const
const VECTOR2I & GetP0() 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...
const SHAPE_ARC & Arc(size_t aArc) const
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
void GenerateBBoxCache() const
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.
bool IsArcEnd(size_t aIndex) const
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
BOX2I * GetCachedBBox() const override
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.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
void SetWidth(int aWidth)
Set the width of all segments in the chain.
const std::vector< VECTOR2I > & CPoints() const
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 KDTree &kdTree, const PCB_SHAPE_ENDPOINTS_ADAPTOR &adaptor, unsigned aLimit)
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.
nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor< double, PCB_SHAPE_ENDPOINTS_ADAPTOR >, PCB_SHAPE_ENDPOINTS_ADAPTOR, 2 > KDTree
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
std::vector< std::pair< VECTOR2I, PCB_SHAPE * > > endpoints
bool kdtree_get_bbox(BBOX &) const
PCB_SHAPE_ENDPOINTS_ADAPTOR(const std::vector< PCB_SHAPE * > &shapes)
size_t kdtree_get_point_count() const
double kdtree_get_pt(const size_t idx, const size_t dim) const
const SHAPE_LINE_CHAIN chain
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
constexpr int LexicographicalCompare(const VECTOR2< T > &aA, const VECTOR2< T > &aB)