KiCad PCB EDA Suite
convert_shape_list_to_polygon.cpp File Reference
#include <trigo.h>
#include <macros.h>
#include <math/vector2d.h>
#include <pcb_shape.h>
#include <footprint.h>
#include <pad.h>
#include <base_units.h>
#include <convert_basic_shapes_to_polygon.h>
#include <geometry/shape_poly_set.h>
#include <geometry/geometry_utils.h>
#include <convert_shape_list_to_polygon.h>
#include <wx/log.h>
#include <board.h>
#include <collectors.h>

Go to the source code of this file.

Functions

bool close_enough (VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
 Function close_enough is a local and tunable method of qualifying the proximity of two points. More...
 
bool closer_to_first (VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
 Function closer_to_first Local method which qualifies whether the start or end point of a segment is closest to a point. More...
 
static PCB_SHAPEfindNext (PCB_SHAPE *aShape, const VECTOR2I &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
 Searches for a PCB_SHAPE matching a given end point or start point in a list. More...
 
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)
 Function ConvertOutlineToPolygon Build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a closed main outline with perhaps closed inner outlines. More...
 
bool BuildBoardPolygonOutlines (BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
 Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer. More...
 
void buildBoardBoundingBoxPoly (const BOARD *aBoard, SHAPE_POLY_SET &aOutline)
 Get the complete bounding box of the board (including all items). More...
 
VECTOR2I projectPointOnSegment (const VECTOR2I &aEndPoint, const SHAPE_POLY_SET &aOutline, int aOutlineNum=0)
 
int findEndSegments (SHAPE_LINE_CHAIN &aChain, SEG &aStartSeg, SEG &aEndSeg)
 
bool BuildFootprintPolygonOutlines (BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
 This function is used to extract a board outline for a footprint view. More...
 

Variables

const wxChar * traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" )
 Flag to enable debug tracing for the board outline creation. More...
 

Function Documentation

◆ buildBoardBoundingBoxPoly()

void buildBoardBoundingBoxPoly ( const BOARD aBoard,
SHAPE_POLY_SET aOutline 
)

Get the complete bounding box of the board (including all items).

The vertex numbers and segment numbers of the rectangle returned. 1 ------------— |1 2| 0| |2 |0 3| ------------— 3

Definition at line 740 of file convert_shape_list_to_polygon.cpp.

741{
742 BOX2I bbbox = aBoard->GetBoundingBox();
743 SHAPE_LINE_CHAIN chain;
744
745 // If null area, uses the global bounding box.
746 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
747 bbbox = aBoard->ComputeBoundingBox();
748
749 // Ensure non null area. If happen, gives a minimal size.
750 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
751 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
752
753 // Inflate slightly (by 1/10th the size of the box)
754 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
755
756 chain.Append( bbbox.GetOrigin() );
757 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
758 chain.Append( bbbox.GetEnd() );
759 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
760 chain.SetClosed( true );
761
762 aOutline.RemoveAllContours();
763 aOutline.AddOutline( chain );
764}
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:809
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1235
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
const Vec GetEnd() const
Definition: box2.h:185
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
constexpr int mmToIU(double mm) const
Definition: base_units.h:89

References SHAPE_POLY_SET::AddOutline(), SHAPE_LINE_CHAIN::Append(), BOARD::ComputeBoundingBox(), BOARD::GetBoundingBox(), BOX2< Vec >::GetEnd(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetOrigin(), BOX2< Vec >::GetWidth(), BOX2< Vec >::Inflate(), EDA_IU_SCALE::mmToIU(), pcbIUScale, SHAPE_POLY_SET::RemoveAllContours(), SHAPE_LINE_CHAIN::SetClosed(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildFootprintPolygonOutlines(), and RENDER_3D_RAYTRACE::Reload().

◆ BuildBoardPolygonOutlines()

bool BuildBoardPolygonOutlines ( BOARD aBoard,
SHAPE_POLY_SET aOutlines,
int  aErrorMax,
int  aChainingEpsilon,
OUTLINE_ERROR_HANDLER aErrorHandler = nullptr 
)

Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer.

Any closed outline inside the main outline is a hole. All contours should be closed, i.e. are valid vertices for a closed polygon.

Returns
true if success, false if a contour is not valid

Definition at line 604 of file convert_shape_list_to_polygon.cpp.

606{
607 PCB_TYPE_COLLECTOR items;
608 bool success = false;
609
610 SHAPE_POLY_SET fpHoles;
611
612 // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
613 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
614
615 for( int ii = 0; ii < items.GetCount(); ++ii )
616 items[ii]->ClearFlags( SKIP_STRUCT );
617
618 for( FOOTPRINT* fp : aBoard->Footprints() )
619 {
620 PCB_TYPE_COLLECTOR fpItems;
621 fpItems.Collect( fp, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
622
623 std::vector<PCB_SHAPE*> fpSegList;
624
625 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
626 {
627 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
628
629 if( fpSeg->GetLayer() == Edge_Cuts )
630 fpSegList.push_back( fpSeg );
631 }
632
633 if( !fpSegList.empty() )
634 {
635 SHAPE_POLY_SET fpOutlines;
636 success = ConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
637 false,
638 // don't report errors here; the second pass also
639 // gets an opportunity to use these segments
640 nullptr );
641
642 if( success && isCopperOutside( fp, fpOutlines ) )
643 {
644 fpHoles.Append( fpOutlines );
645 }
646 else
647 {
648 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
649 // in contention for the board outline builds.
650 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
651 fpItems[ii]->ClearFlags( SKIP_STRUCT );
652 }
653 }
654 }
655
656 // Make a working copy of aSegList, because the list is modified during calculations
657 std::vector<PCB_SHAPE*> segList;
658
659 for( int ii = 0; ii < items.GetCount(); ii++ )
660 {
661 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
662
663 // Skip anything already used to generate footprint holes (above)
664 if( seg->GetFlags() & SKIP_STRUCT )
665 continue;
666
667 if( seg->GetLayer() == Edge_Cuts )
668 segList.push_back( seg );
669 }
670
671 if( segList.size() )
672 {
673 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
674 true, aErrorHandler );
675 }
676
677 if( !success || !aOutlines.OutlineCount() )
678 {
679 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
680 // create a rectangular outline, or, failing that, the bounding box of the items on
681 // the board.
682
683 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
684
685 // If null area, uses the global bounding box.
686 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
687 bbbox = aBoard->ComputeBoundingBox();
688
689 // Ensure non null area. If happen, gives a minimal size.
690 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
691 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
692
693 aOutlines.RemoveAllContours();
694 aOutlines.NewOutline();
695
696 wxPoint corner;
697 aOutlines.Append( bbbox.GetOrigin() );
698
699 corner.x = bbbox.GetOrigin().x;
700 corner.y = bbbox.GetEnd().y;
701 aOutlines.Append( corner );
702
703 aOutlines.Append( bbbox.GetEnd() );
704
705 corner.x = bbbox.GetEnd().x;
706 corner.y = bbbox.GetOrigin().y;
707 aOutlines.Append( corner );
708 }
709
710 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
711 {
712 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
713
714 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
715 {
716 if( aOutlines.Outline( jj ).PointInside( holePt ) )
717 {
718 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
719 break;
720 }
721 }
722 }
723
724 return success;
725}
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:192
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:823
FOOTPRINTS & Footprints()
Definition: board.h:307
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:81
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:142
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:522
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.
Definition: collectors.cpp:631
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Represent a set of closed polygons.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
SHAPE_LINE_CHAIN & Outline(int aIndex)
int NewOutline()
Creates a new hole in a given outline.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool ConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler)
Function ConvertOutlineToPolygon Build a polygon (with holes) from a PCB_SHAPE list,...
bool isCopperOutside(const FOOTPRINT *aFootprint, SHAPE_POLY_SET &aShape)
#define SKIP_STRUCT
flag indicating that the structure should be ignored
@ Edge_Cuts
Definition: layer_ids.h:113
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:88
@ PCB_FP_SHAPE_T
class FP_SHAPE, a footprint edge
Definition: typeinfo.h:94

References SHAPE_POLY_SET::AddHole(), SHAPE_POLY_SET::Append(), PCB_TYPE_COLLECTOR::Collect(), BOARD::ComputeBoundingBox(), ConvertOutlineToPolygon(), SHAPE_LINE_CHAIN::CPoint(), Edge_Cuts, BOARD::Footprints(), BOARD::GetBoardEdgesBoundingBox(), COLLECTOR::GetCount(), BOX2< Vec >::GetEnd(), EDA_ITEM::GetFlags(), BOX2< Vec >::GetHeight(), BOARD_ITEM::GetLayer(), BOX2< Vec >::GetOrigin(), BOX2< Vec >::GetWidth(), BOX2< Vec >::Inflate(), isCopperOutside(), EDA_IU_SCALE::mmToIU(), SHAPE_POLY_SET::NewOutline(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), PCB_FP_SHAPE_T, PCB_SHAPE_T, pcbIUScale, SHAPE_LINE_CHAIN_BASE::PointInside(), SHAPE_POLY_SET::RemoveAllContours(), SKIP_STRUCT, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BOARD::GetBoardPolygonOutlines(), DIALOG_EXPORT_STEP::onExportButton(), and DRC_TEST_PROVIDER_MISC::testOutline().

◆ BuildFootprintPolygonOutlines()

bool BuildFootprintPolygonOutlines ( BOARD aBoard,
SHAPE_POLY_SET aOutlines,
int  aErrorMax,
int  aChainingEpsilon,
OUTLINE_ERROR_HANDLER aErrorHandler 
)

This function is used to extract a board outline for a footprint view.

Notes:

  • Incomplete outlines will be closed by joining the end of the outline onto the bounding box (by simply projecting the end points) and then take the area that contains the copper.
  • If all copper lies inside a closed outline, than that outline will be treated as an external board outline.
  • If copper is located outside a closed outline, then that outline will be treated as a hole, and the outer edge will be formed using the bounding box.

Definition at line 853 of file convert_shape_list_to_polygon.cpp.

856{
857 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
858
859 // No footprint loaded
860 if( !footprint )
861 {
862 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
863 return false;
864 }
865
866 PCB_TYPE_COLLECTOR items;
867 SHAPE_POLY_SET outlines;
868 bool success = false;
869
870 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
871 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
872
873 // Make a working copy of aSegList, because the list is modified during calculations
874 std::vector<PCB_SHAPE*> segList;
875
876 for( int ii = 0; ii < items.GetCount(); ii++ )
877 {
878 if( items[ii]->GetLayer() == Edge_Cuts )
879 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
880 }
881
882 if( !segList.empty() )
883 {
884 success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
885 true, aErrorHandler );
886 }
887
888 // A closed outline was found on Edge_Cuts
889 if( success )
890 {
891 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
892
893 // If copper is outside a closed polygon, treat it as a hole
894 if( isCopperOutside( footprint, outlines ) )
895 {
896 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
897
898 buildBoardBoundingBoxPoly( aBoard, aOutlines );
899
900 // Copy all outlines from the conversion as holes into the new outline
901 for( int i = 0; i < outlines.OutlineCount(); i++ )
902 {
903 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
904
905 if( out.IsClosed() )
906 aOutlines.AddHole( out, -1 );
907
908 for( int j = 0; j < outlines.HoleCount( i ); j++ )
909 {
910 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
911
912 if( hole.IsClosed() )
913 aOutlines.AddHole( hole, -1 );
914 }
915 }
916 }
917 // If all copper is inside, then the computed outline is the board outline
918 else
919 {
920 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
921 aOutlines = outlines;
922 }
923
924 return true;
925 }
926 // No board outlines were found, so use the bounding box
927 else if( outlines.OutlineCount() == 0 )
928 {
929 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
930 buildBoardBoundingBoxPoly( aBoard, aOutlines );
931
932 return true;
933 }
934 // There is an outline present, but it is not closed
935 else
936 {
937 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
938
939 std::vector<SHAPE_LINE_CHAIN> closedChains;
940 std::vector<SHAPE_LINE_CHAIN> openChains;
941
942 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
943 // holes, so we promote the holes and process them
944 openChains.push_back( outlines.Outline( 0 ) );
945
946 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
947 {
948 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
949
950 if( hole.IsClosed() )
951 {
952 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
953 closedChains.push_back( hole );
954 }
955 else
956 {
957 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
958 openChains.push_back( hole );
959 }
960 }
961
962 SHAPE_POLY_SET bbox;
963 buildBoardBoundingBoxPoly( aBoard, bbox );
964
965 // Treat the open polys as the board edge
966 SHAPE_LINE_CHAIN chain = openChains[0];
967 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
968
969 // We know the outline chain is open, so set to non-closed to get better segment count
970 chain.SetClosed( false );
971
972 SEG startSeg;
973 SEG endSeg;
974
975 // The two possible board outlines
976 SHAPE_LINE_CHAIN upper;
977 SHAPE_LINE_CHAIN lower;
978
979 findEndSegments( chain, startSeg, endSeg );
980
981 if( chain.SegmentCount() == 0 )
982 {
983 // Something is wrong, bail out with the overall footprint bounding box
984 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
985 aOutlines = bbox;
986 return true;
987 }
988 else if( chain.SegmentCount() == 1 )
989 {
990 // This case means there is only 1 line segment making up the edge cuts of the
991 // footprint, so we just need to use it to cut the bounding box in half.
992 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
993
994 startSeg = chain.Segment( 0 );
995
996 // Intersect with all the sides of the rectangle
997 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
998 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
999 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1000 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1001
1002 if( inter0 && inter2 && !inter1 && !inter3 )
1003 {
1004 // Intersects the vertical rectangle sides only
1005 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1006 "sides" ) );
1007
1008 // The upper half
1009 upper.Append( *inter0 );
1010 upper.Append( rect.GetPoint( 1 ) );
1011 upper.Append( rect.GetPoint( 2 ) );
1012 upper.Append( *inter2 );
1013 upper.SetClosed( true );
1014
1015 // The lower half
1016 lower.Append( *inter0 );
1017 lower.Append( rect.GetPoint( 0 ) );
1018 lower.Append( rect.GetPoint( 3 ) );
1019 lower.Append( *inter2 );
1020 lower.SetClosed( true );
1021 }
1022 else if( inter1 && inter3 && !inter0 && !inter2 )
1023 {
1024 // Intersects the horizontal rectangle sides only
1025 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1026 "sides" ) );
1027
1028 // The left half
1029 upper.Append( *inter1 );
1030 upper.Append( rect.GetPoint( 1 ) );
1031 upper.Append( rect.GetPoint( 0 ) );
1032 upper.Append( *inter3 );
1033 upper.SetClosed( true );
1034
1035 // The right half
1036 lower.Append( *inter1 );
1037 lower.Append( rect.GetPoint( 2 ) );
1038 lower.Append( rect.GetPoint( 3 ) );
1039 lower.Append( *inter3 );
1040 lower.SetClosed( true );
1041 }
1042 else
1043 {
1044 // Angled line segment that cuts across a corner
1045 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1046 "sides" ) );
1047
1048 // Figure out which actual lines are intersected, since IntersectLines assumes
1049 // an infinite line
1050 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1051 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1052 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1053 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1054
1055 if( hit0 && hit1 )
1056 {
1057 // Cut across the upper left corner
1058 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1059
1060 // The upper half
1061 upper.Append( *inter0 );
1062 upper.Append( rect.GetPoint( 1 ) );
1063 upper.Append( *inter1 );
1064 upper.SetClosed( true );
1065
1066 // The lower half
1067 lower.Append( *inter0 );
1068 lower.Append( rect.GetPoint( 0 ) );
1069 lower.Append( rect.GetPoint( 3 ) );
1070 lower.Append( rect.GetPoint( 2 ) );
1071 lower.Append( *inter1 );
1072 lower.SetClosed( true );
1073 }
1074 else if( hit1 && hit2 )
1075 {
1076 // Cut across the upper right corner
1077 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1078
1079 // The upper half
1080 upper.Append( *inter1 );
1081 upper.Append( rect.GetPoint( 2 ) );
1082 upper.Append( *inter2 );
1083 upper.SetClosed( true );
1084
1085 // The lower half
1086 lower.Append( *inter1 );
1087 lower.Append( rect.GetPoint( 1 ) );
1088 lower.Append( rect.GetPoint( 0 ) );
1089 lower.Append( rect.GetPoint( 3 ) );
1090 lower.Append( *inter2 );
1091 lower.SetClosed( true );
1092 }
1093 else if( hit2 && hit3 )
1094 {
1095 // Cut across the lower right corner
1096 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1097
1098 // The upper half
1099 upper.Append( *inter2 );
1100 upper.Append( rect.GetPoint( 2 ) );
1101 upper.Append( rect.GetPoint( 1 ) );
1102 upper.Append( rect.GetPoint( 0 ) );
1103 upper.Append( *inter3 );
1104 upper.SetClosed( true );
1105
1106 // The bottom half
1107 lower.Append( *inter2 );
1108 lower.Append( rect.GetPoint( 3 ) );
1109 lower.Append( *inter3 );
1110 lower.SetClosed( true );
1111 }
1112 else
1113 {
1114 // Cut across the lower left corner
1115 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1116
1117 // The upper half
1118 upper.Append( *inter0 );
1119 upper.Append( rect.GetPoint( 1 ) );
1120 upper.Append( rect.GetPoint( 2 ) );
1121 upper.Append( rect.GetPoint( 3 ) );
1122 upper.Append( *inter3 );
1123 upper.SetClosed( true );
1124
1125 // The bottom half
1126 lower.Append( *inter0 );
1127 lower.Append( rect.GetPoint( 0 ) );
1128 lower.Append( *inter3 );
1129 lower.SetClosed( true );
1130 }
1131 }
1132 }
1133 else
1134 {
1135 // More than 1 segment
1136 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1137
1138 // Just a temporary thing
1139 aOutlines = bbox;
1140 return true;
1141 }
1142
1143 // Figure out which is the correct outline
1144 SHAPE_POLY_SET poly1;
1145 SHAPE_POLY_SET poly2;
1146
1147 poly1.NewOutline();
1148 poly1.Append( upper );
1149
1150 poly2.NewOutline();
1151 poly2.Append( lower );
1152
1153 if( isCopperOutside( footprint, poly1 ) )
1154 {
1155 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1156 aOutlines = poly2;
1157 }
1158 else
1159 {
1160 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1161 aOutlines = poly1;
1162 }
1163
1164 // Add all closed polys as holes to the main outline
1165 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1166 {
1167 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1168 aOutlines.AddHole( closedChain, -1 );
1169 }
1170
1171 return true;
1172 }
1173
1174 // We really shouldn't reach this point
1175 return false;
1176}
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:397
Definition: seg.h:42
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
bool Contains(const SEG &aSeg) const
Definition: seg.h:307
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
int SegmentCount() const
Return the number of segments in this line chain.
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
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)
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39

References SHAPE_POLY_SET::AddHole(), SHAPE_LINE_CHAIN::Append(), SHAPE_POLY_SET::Append(), buildBoardBoundingBoxPoly(), PCB_TYPE_COLLECTOR::Collect(), SEG::Contains(), ConvertOutlineToPolygon(), Edge_Cuts, findEndSegments(), COLLECTOR::GetCount(), BOARD::GetFirstFootprint(), SHAPE_LINE_CHAIN::GetPoint(), SHAPE_POLY_SET::Hole(), SHAPE_POLY_SET::HoleCount(), SEG::IntersectLines(), SHAPE_LINE_CHAIN::IsClosed(), isCopperOutside(), SHAPE_POLY_SET::NewOutline(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), PCB_FP_SHAPE_T, PCB_SHAPE_T, SHAPE_LINE_CHAIN::Segment(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_LINE_CHAIN::SetClosed(), and traceBoardOutline.

Referenced by BOARD_ADAPTER::createBoardPolygon().

◆ close_enough()

bool close_enough ( VECTOR2I  aLeft,
VECTOR2I  aRight,
unsigned  aLimit 
)

Function close_enough is a local and tunable method of qualifying the proximity of two points.

Parameters
aLeftis the first point
aRightis the second point
aLimitis a measure of proximity that the caller knows about.
Returns
bool - true if the two points are close enough, else false.

Definition at line 60 of file convert_shape_list_to_polygon.cpp.

61{
62 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63}
static SEG::ecoord Square(int a)
Definition: seg.h:123

References SEG::Square().

Referenced by ConvertOutlineToPolygon().

◆ closer_to_first()

bool closer_to_first ( VECTOR2I  aRef,
VECTOR2I  aFirst,
VECTOR2I  aSecond 
)

Function closer_to_first Local method which qualifies whether the start or end point of a segment is closest to a point.

Parameters
aRefis the reference point
aFirstis the first point
aSecondis the second point
Returns
bool - true if the first point is closest to the reference, otherwise false.

Definition at line 74 of file convert_shape_list_to_polygon.cpp.

75{
76 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
77}

Referenced by ConvertOutlineToPolygon().

◆ ConvertOutlineToPolygon()

bool ConvertOutlineToPolygon ( std::vector< PCB_SHAPE * > &  aShapeList,
SHAPE_POLY_SET aPolygons,
int  aErrorMax,
int  aChainingEpsilon,
bool  aAllowDisjoint,
OUTLINE_ERROR_HANDLER aErrorHandler 
)

Function ConvertOutlineToPolygon Build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a closed main outline with perhaps closed inner outlines.

Function ConvertOutlineToPolygon build a polygon set (with holes) from a PCB_SHAPE list, which is expected to be one or more top-level closed outlines, with zero or more holes in each.

These closed inner outlines are considered as holes in the main outline.

Parameters
aShapeListthe initial list of SHAPEs (only lines, circles and arcs).
aPolygonswill contain the complex polygon.
aErrorMaxis the max error distance when polygonizing a curve (internal units)
aChainingEpsilonis the max error distance when polygonizing a curve (internal units)
aAllowDisjointindicates multiple top-level outlines are allowed
aErrorHandler= an optional error handler

Definition at line 175 of file convert_shape_list_to_polygon.cpp.

178{
179 if( aShapeList.size() == 0 )
180 return true;
181
182 bool selfIntersecting = false;
183
184 wxString msg;
185 PCB_SHAPE* graphic = nullptr;
186
187 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
188
189 // Keep a list of where the various shapes came from so after doing our combined-polygon
190 // tests we can still report errors against the individual graphic items.
191 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> shapeOwners;
192
193 auto fetchOwner =
194 [&]( const SEG& seg ) -> PCB_SHAPE*
195 {
196 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
197 return it == shapeOwners.end() ? nullptr : it->second;
198 };
199
200 PCB_SHAPE* prevGraphic = nullptr;
201 VECTOR2I prevPt;
202
203 std::vector<SHAPE_LINE_CHAIN> contours;
204
205 for( PCB_SHAPE* shape : startCandidates )
206 shape->ClearFlags( SKIP_STRUCT );
207
208 while( startCandidates.size() )
209 {
210 graphic = (PCB_SHAPE*) *startCandidates.begin();
211 graphic->SetFlags( SKIP_STRUCT );
212 startCandidates.erase( startCandidates.begin() );
213
214 contours.emplace_back();
215
216 SHAPE_LINE_CHAIN& currContour = contours.back();
217 bool firstPt = true;
218
219 // Circles, rects and polygons are closed shapes unto themselves (and do not combine
220 // with other shapes), so process them separately.
221 if( graphic->GetShape() == SHAPE_T::POLY )
222 {
223 EDA_ANGLE orientation = ANGLE_0;
224 VECTOR2I offset = VECTOR2I( 0, 0 );
225
226 if( graphic->GetParentFootprint() )
227 {
228 orientation = graphic->GetParentFootprint()->GetOrientation();
229 offset = graphic->GetParentFootprint()->GetPosition();
230 }
231
232 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
233 {
234 VECTOR2I pt = *it;
235 RotatePoint( pt, orientation );
236 pt += offset;
237
238 currContour.Append( pt );
239
240 if( firstPt )
241 firstPt = false;
242 else
243 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
244
245 prevPt = pt;
246 }
247
248 currContour.SetClosed( true );
249 }
250 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
251 {
252 // make a circle by segments;
253 VECTOR2I center = graphic->GetCenter();
254 VECTOR2I start = center;
255 int radius = graphic->GetRadius();
256 int steps = GetArcToSegmentCount( radius, aErrorMax, FULL_CIRCLE );
257 VECTOR2I nextPt;
258
259 start.x += radius;
260
261 for( int step = 0; step < steps; ++step )
262 {
263 nextPt = start;
264 RotatePoint( nextPt, center, ANGLE_360 * step / steps );
265 currContour.Append( nextPt );
266
267 if( firstPt )
268 firstPt = false;
269 else
270 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
271
272 prevPt = nextPt;
273 }
274
275 currContour.SetClosed( true );
276 }
277 else if( graphic->GetShape() == SHAPE_T::RECT )
278 {
279 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
280
281 for( const VECTOR2I& pt : pts )
282 {
283 currContour.Append( pt );
284
285 if( firstPt )
286 firstPt = false;
287 else
288 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
289
290 prevPt = pt;
291 }
292
293 currContour.SetClosed( true );
294 }
295 else
296 {
297 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
298 // from here.
299
300 VECTOR2I startPt = graphic->GetEnd();
301 prevPt = startPt;
302 currContour.Append( prevPt );
303
304 // do not append the other end point yet, this first 'graphic' might be an arc
305 for(;;)
306 {
307 switch( graphic->GetShape() )
308 {
309 case SHAPE_T::RECT:
310 case SHAPE_T::CIRCLE:
311 {
312 // As a non-first item, closed shapes can't be anything but self-intersecting
313
314 if( aErrorHandler )
315 {
316 wxASSERT( prevGraphic );
317 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
318 }
319
320 selfIntersecting = true;
321
322 // A closed shape will finish where it started, so no point in updating prevPt
323 break;
324 }
325
326 case SHAPE_T::SEGMENT:
327 {
328 VECTOR2I nextPt;
329
330 // Use the line segment end point furthest away from prevPt as we assume
331 // the other end to be ON prevPt or very close to it.
332
333 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
334 nextPt = graphic->GetEnd();
335 else
336 nextPt = graphic->GetStart();
337
338 currContour.Append( nextPt );
339 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
340 prevPt = nextPt;
341 }
342 break;
343
344 case SHAPE_T::ARC:
345 // We do not support arcs in polygons, so approximate an arc with a series of
346 // short lines and put those line segments into the !same! PATH.
347 {
348 VECTOR2I pstart = graphic->GetStart();
349 VECTOR2I pend = graphic->GetEnd();
350 VECTOR2I pcenter = graphic->GetCenter();
351 EDA_ANGLE angle = -graphic->GetArcAngle();
352 int radius = graphic->GetRadius();
353 int steps = GetArcToSegmentCount( radius, aErrorMax, angle );
354
355 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
356 {
357 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
358
359 angle = -angle;
360 std::swap( pstart, pend );
361 }
362
363 // Create intermediate points between start and end:
364 for( int step = 1; step < steps; ++step )
365 {
366 EDA_ANGLE rotation = ( angle * step ) / steps;
367 VECTOR2I pt = pstart;
368
369 RotatePoint( pt, pcenter, rotation );
370
371 currContour.Append( pt );
372 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
373 prevPt = pt;
374 }
375
376 // Append the last arc end point
377 currContour.Append( pend );
378 shapeOwners[ std::make_pair( prevPt, pend ) ] = graphic;
379 prevPt = pend;
380 }
381 break;
382
383 case SHAPE_T::BEZIER:
384 // We do not support Bezier curves in polygons, so approximate with a series
385 // of short lines and put those line segments into the !same! PATH.
386 {
387 VECTOR2I nextPt;
388 bool reverse = false;
389
390 // Use the end point furthest away from prevPt as we assume the other
391 // end to be ON prevPt or very close to it.
392
393 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
394 {
395 nextPt = graphic->GetEnd();
396 }
397 else
398 {
399 nextPt = graphic->GetStart();
400 reverse = true;
401 }
402
403 if( reverse )
404 {
405 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
406 {
407 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
408 currContour.Append( pt );
409 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
410 prevPt = pt;
411 }
412 }
413 else
414 {
415 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
416 {
417 currContour.Append( pt );
418 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
419 prevPt = pt;
420 }
421 }
422
423 prevPt = nextPt;
424 }
425 break;
426
427 default:
429 return false;
430 }
431
432 // Get next closest segment.
433
434 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
435
436 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
437 {
438 prevGraphic = graphic;
439 graphic = nextGraphic;
440 graphic->SetFlags( SKIP_STRUCT );
441 startCandidates.erase( graphic );
442 continue;
443 }
444
445 // Finished, or ran into trouble...
446
447 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
448 {
449 currContour.SetClosed( true );
450 break;
451 }
452 else if( nextGraphic ) // encountered already-used segment, but not at the start
453 {
454 if( aErrorHandler )
455 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
456
457 break;
458 }
459 else // encountered discontinuity
460 {
461 if( aErrorHandler )
462 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
463
464 break;
465 }
466 }
467 }
468 }
469
470 for( const SHAPE_LINE_CHAIN& contour : contours )
471 {
472 if( !contour.IsClosed() )
473 return false;
474 }
475
476 // First, collect the parents of each contour
477 //
478 std::map<int, std::vector<int>> contourToParentIndexesMap;
479
480 for( size_t ii = 0; ii < contours.size(); ++ii )
481 {
482 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
483 std::vector<int> parents;
484
485 for( size_t jj = 0; jj < contours.size(); ++jj )
486 {
487 if( jj == ii )
488 continue;
489
490 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
491
492 if( parentCandidate.PointInside( firstPt ) )
493 parents.push_back( jj );
494 }
495
496 contourToParentIndexesMap[ii] = parents;
497 }
498
499 // Next add those that are top-level outlines to the SHAPE_POLY_SET
500 //
501 std::map<int, int> contourToOutlineIdxMap;
502
503 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
504 {
505 if( parentIndexes.size() %2 == 0 )
506 {
507 // Even number of parents; top-level outline
508 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
509 {
510 if( aErrorHandler )
511 {
512 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
513 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
514
515 if( a && b )
516 {
517 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
518 contours[ contourIndex ].GetPoint( 0 ) );
519 }
520 }
521
522 return false;
523 }
524
525 aPolygons.AddOutline( contours[ contourIndex ] );
526 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
527 }
528 }
529
530 // And finally add the holes
531 //
532 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
533 {
534 if( parentIndexes.size() %2 == 1 )
535 {
536 // Odd number of parents; we're a hole in the parent which has one fewer parents
537 // than we have.
538 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
539
540 for( int parentContourIdx : parentIndexes )
541 {
542 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
543 {
544 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
545 aPolygons.AddHole( hole, outlineIdx );
546 break;
547 }
548 }
549 }
550 }
551
552 // All of the silliness that follows is to work around the segment iterator while checking
553 // for collisions.
554 // TODO: Implement proper segment and point iterators that follow std
555
556 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
557 {
558 auto seg2 = seg1;
559
560 for( ++seg2; seg2; seg2++ )
561 {
562 // Check for exact overlapping segments.
563 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
564 {
565 if( aErrorHandler )
566 {
567 BOARD_ITEM* a = fetchOwner( *seg1 );
568 BOARD_ITEM* b = fetchOwner( *seg2 );
569
570 if( a && b )
571 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
572 }
573
574 selfIntersecting = true;
575 }
576
577 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
578 {
579 if( aErrorHandler )
580 {
581 BOARD_ITEM* a = fetchOwner( *seg1 );
582 BOARD_ITEM* b = fetchOwner( *seg2 );
583
584 if( a && b )
585 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
586 }
587
588 selfIntersecting = true;
589 }
590 }
591 }
592
593 return !selfIntersecting;
594}
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:70
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:139
EDA_ANGLE GetArcAngle() const
Definition: eda_shape.cpp:585
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:247
int GetRadius() const
Definition: eda_shape.cpp:523
SHAPE_T GetShape() const
Definition: eda_shape.h:113
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:145
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:120
std::vector< VECTOR2I > GetRectCorners() const
Definition: eda_shape.cpp:1035
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition: eda_shape.h:230
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:75
EDA_ANGLE GetOrientation() const
Definition: footprint.h:191
VECTOR2I GetPosition() const override
Definition: footprint.h:188
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:67
FOOTPRINT * GetParentFootprint() const
Return the parent footprint or NULL if PCB_SHAPE does not belong to a footprint.
Definition: pcb_shape.cpp:252
virtual const SEG GetSegment(int aIndex) const override
bool IsEmpty() const
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const VECTOR2I &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
Searches for a PCB_SHAPE matching a given end point or start point in a list.
bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Function close_enough is a local and tunable method of qualifying the proximity of two points.
bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Function closer_to_first Local method which qualifies whether the start or end point of a segment is ...
#define _(s)
static constexpr EDA_ANGLE & ANGLE_360
Definition: eda_angle.h:429
static constexpr EDA_ANGLE & FULL_CIRCLE
Definition: eda_angle.h:421
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:423
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
#define UNIMPLEMENTED_FOR(type)
Definition: macros.h:120
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References _, SHAPE_POLY_SET::AddHole(), SHAPE_POLY_SET::AddOutline(), PNS::angle(), ANGLE_0, ANGLE_360, SHAPE_LINE_CHAIN::Append(), ARC, BEZIER, CIRCLE, SHAPE_POLY_SET::CIterate(), close_enough(), closer_to_first(), findNext(), FULL_CIRCLE, EDA_SHAPE::GetArcAngle(), GetArcToSegmentCount(), EDA_SHAPE::GetBezierPoints(), PCB_SHAPE::GetCenter(), EDA_SHAPE::GetEnd(), EDA_ITEM::GetFlags(), FOOTPRINT::GetOrientation(), PCB_SHAPE::GetParentFootprint(), EDA_SHAPE::GetPolyShape(), FOOTPRINT::GetPosition(), EDA_SHAPE::GetRadius(), EDA_SHAPE::GetRectCorners(), SHAPE_LINE_CHAIN::GetSegment(), EDA_SHAPE::GetShape(), EDA_SHAPE::GetStart(), SHAPE_POLY_SET::IsEmpty(), SHAPE_POLY_SET::IterateSegmentsWithHoles(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), SHAPE_LINE_CHAIN_BASE::PointInside(), POLY, RECT, RotatePoint(), SEGMENT, SHAPE_LINE_CHAIN::SetClosed(), EDA_ITEM::SetFlags(), EDA_SHAPE::SHAPE_T_asString(), SKIP_STRUCT, UNIMPLEMENTED_FOR, and VECTOR2< T >::x.

Referenced by BuildBoardPolygonOutlines(), FOOTPRINT::BuildCourtyardCaches(), and BuildFootprintPolygonOutlines().

◆ findEndSegments()

int findEndSegments ( SHAPE_LINE_CHAIN aChain,
SEG aStartSeg,
SEG aEndSeg 
)

Definition at line 789 of file convert_shape_list_to_polygon.cpp.

790{
791 int foundSegs = 0;
792
793 for( int i = 0; i < aChain.SegmentCount(); i++ )
794 {
795 SEG seg = aChain.Segment( i );
796
797 bool foundA = false;
798 bool foundB = false;
799
800 for( int j = 0; j < aChain.SegmentCount(); j++ )
801 {
802 // Don't test the segment against itself
803 if( i == j )
804 continue;
805
806 SEG testSeg = aChain.Segment( j );
807
808 if( testSeg.Contains( seg.A ) )
809 foundA = true;
810
811 if( testSeg.Contains( seg.B ) )
812 foundB = true;
813 }
814
815 // This segment isn't a start or end
816 if( foundA && foundB )
817 continue;
818
819 if( foundSegs == 0 )
820 {
821 // The first segment we encounter is the "start" segment
822 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
823 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
824 aStartSeg = seg;
825 foundSegs++;
826 }
827 else
828 {
829 // Once we find both start and end, we can stop
830 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
831 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
832 aEndSeg = seg;
833 foundSegs++;
834 break;
835 }
836 }
837
838 return foundSegs;
839}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50

References SEG::A, SEG::B, SEG::Contains(), SHAPE_LINE_CHAIN::Segment(), SHAPE_LINE_CHAIN::SegmentCount(), traceBoardOutline, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildFootprintPolygonOutlines().

◆ findNext()

static PCB_SHAPE * findNext ( PCB_SHAPE aShape,
const VECTOR2I aPoint,
const std::vector< PCB_SHAPE * > &  aList,
unsigned  aLimit 
)
static

Searches for a PCB_SHAPE matching a given end point or start point in a list.

Parameters
aShapeThe starting shape.
aPointThe starting or ending point to search for.
aListThe list to remove from.
aLimitis the distance from aPoint that still constitutes a valid find.
Returns
PCB_SHAPE* - The first PCB_SHAPE that has a start or end point matching aPoint, otherwise NULL if none.

Definition at line 89 of file convert_shape_list_to_polygon.cpp.

91{
92 // Look for an unused, exact hit
93 for( PCB_SHAPE* graphic : aList )
94 {
95 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
96 continue;
97
98 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
99 return graphic;
100 }
101
102 // Search again for anything that's close, even something already used. (The latter is
103 // important for error reporting.)
104 VECTOR2I pt( aPoint );
105 SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
106 PCB_SHAPE* closest_graphic = nullptr;
107 SEG::ecoord d_sq;
108
109 for( PCB_SHAPE* graphic : aList )
110 {
111 if( graphic == aShape )
112 continue;
113
114 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
115
116 if( d_sq < closest_dist_sq )
117 {
118 closest_dist_sq = d_sq;
119 closest_graphic = graphic;
120 }
121
122 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
123
124 if( d_sq < closest_dist_sq )
125 {
126 closest_dist_sq = d_sq;
127 closest_graphic = graphic;
128 }
129 }
130
131 return closest_graphic; // Note: will be nullptr if nothing within aLimit
132}
VECTOR2I::extended_type ecoord
Definition: seg.h:44

References SKIP_STRUCT, and SEG::Square().

Referenced by ConvertOutlineToPolygon(), and PAD_TOOL::RecombinePad().

◆ isCopperOutside()

bool isCopperOutside ( const FOOTPRINT aFootprint,
SHAPE_POLY_SET aShape 
)

Definition at line 135 of file convert_shape_list_to_polygon.cpp.

136{
137 bool padOutside = false;
138
139 for( PAD* pad : aFootprint->Pads() )
140 {
142
143 poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
144
145 if( poly.OutlineCount() == 0 )
146 {
147 VECTOR2I padPos = pad->GetPosition();
148 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ),
149 padPos.x, padPos.y );
150 padOutside = true;
151 break;
152 }
153
154 VECTOR2I padPos = pad->GetPosition();
155 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
156 padPos.x, padPos.y );
157 }
158
159 return padOutside;
160}
PADS & Pads()
Definition: footprint.h:170
Definition: pad.h:59
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
SHAPE_POLY_SET CloneDropTriangulation() const
Creates a new empty polygon in the set and returns its index.

References SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::CloneDropTriangulation(), SHAPE_POLY_SET::OutlineCount(), pad, FOOTPRINT::Pads(), SHAPE_POLY_SET::PM_FAST, traceBoardOutline, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildBoardPolygonOutlines(), and BuildFootprintPolygonOutlines().

◆ projectPointOnSegment()

VECTOR2I projectPointOnSegment ( const VECTOR2I aEndPoint,
const SHAPE_POLY_SET aOutline,
int  aOutlineNum = 0 
)

Definition at line 767 of file convert_shape_list_to_polygon.cpp.

769{
770 int minDistance = -1;
771 VECTOR2I projPoint;
772
773 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
774 {
775 auto seg = it.Get();
776 int dis = seg.Distance( aEndPoint );
777
778 if( minDistance < 0 || ( dis < minDistance ) )
779 {
780 minDistance = dis;
781 projPoint = seg.NearestPoint( aEndPoint );
782 }
783 }
784
785 return projPoint;
786}
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.

References SHAPE_POLY_SET::CIterateSegments().