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*> shapeList;
617 for(
int ii = 0; ii < items.
GetCount(); ii++ )
622 shapeList.push_back( seg );
628 switch( shape->GetShape() )
632 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
635 if( dim <= min_dist )
641 (*aErrorHandler)( wxString::Format(
_(
"(rectangle has null or very small "
642 "size: %d nm)" ), dim ),
643 shape,
nullptr, shape->GetStart() );
651 int r = shape->GetRadius();
659 (*aErrorHandler)( wxString::Format(
_(
"(circle has null or very small "
660 "radius: %d nm)" ), r ),
661 shape,
nullptr, shape->GetStart() );
669 VECTOR2I seg = shape->GetEnd() - shape->GetStart();
672 if( dim <= min_dist )
678 (*aErrorHandler)( wxString::Format(
_(
"(segment has null or very small "
679 "length: %d nm)" ), dim ),
680 shape,
nullptr, shape->GetStart() );
690 VECTOR2I arcMiddle = shape->GetArcMid();
691 VECTOR2I seg1 = arcMiddle - shape->GetStart();
692 VECTOR2I seg2 = shape->GetEnd() - arcMiddle;
695 if( dim <= min_dist )
701 (*aErrorHandler)( wxString::Format(
_(
"(arc has null or very small size: "
703 shape,
nullptr, shape->GetStart() );
727 bool aAllowUseArcsInPolygons )
731 bool success =
false;
738 for(
int ii = 0; ii < items.
GetCount(); ++ii )
746 std::vector<PCB_SHAPE*> fpSegList;
748 for(
int ii = 0; ii < fpItems.
GetCount(); ii++ )
753 fpSegList.push_back( fpSeg );
756 if( !fpSegList.empty() )
763 nullptr, aAllowUseArcsInPolygons, cleaner );
772 fpHoles.
Append( fpOutlines );
778 for(
int ii = 0; ii < fpItems.
GetCount(); ++ii )
785 std::vector<PCB_SHAPE*> segList;
787 for(
int ii = 0; ii < items.
GetCount(); ii++ )
796 segList.push_back( seg );
802 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
828 aOutlines.
Append( corner );
834 aOutlines.
Append( corner );
895 int aOutlineNum = 0 )
897 int minDistance = -1;
903 int dis = seg.
Distance( aEndPoint );
905 if( minDistance < 0 || ( dis < minDistance ) )
908 projPoint = seg.NearestPoint( aEndPoint );
943 if( foundA && foundB )
950 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
958 seg.
A.
x, seg.
A.
y, seg.
B.
x, seg.
B.
y );
984 bool success =
false;
992 std::vector<PCB_SHAPE*> segList;
994 for(
int ii = 0; ii < items.
GetCount(); ii++ )
997 segList.push_back(
static_cast<PCB_SHAPE*
>( items[ii] ) );
1000 if( !segList.empty() )
1003 aErrorHandler,
false, cleaner );
1027 for(
int j = 0; j < outlines.
HoleCount( i ); j++ )
1032 aOutlines.
AddHole( hole, -1 );
1040 aOutlines = outlines;
1058 std::vector<SHAPE_LINE_CHAIN> closedChains;
1059 std::vector<SHAPE_LINE_CHAIN> openChains;
1063 openChains.push_back( outlines.
Outline( 0 ) );
1065 for(
int j = 0; j < outlines.
HoleCount( 0 ); j++ )
1072 closedChains.push_back( hole );
1077 openChains.push_back( hole );
1111 wxLogTrace(
traceBoardOutline, wxT(
"Only 1 line segment in provided outline" ) );
1113 startSeg = chain.
Segment( 0 );
1121 if( inter0 && inter2 && !inter1 && !inter3 )
1141 else if( inter1 && inter3 && !inter0 && !inter2 )
1164 wxLogTrace(
traceBoardOutline, wxT(
"Segment intersects two perpendicular bbox "
1193 else if( hit1 && hit2 )
1212 else if( hit2 && hit3 )
1287 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