convert_shape_list_to_polygon.h File Reference

Go to the source code of this file.

Typedefs
typedef const std::function< void(const wxString &msg, BOARD_ITEM *itemA, BOARD_ITEM *itemB, const VECTOR2I &pt)>	OUTLINE_ERROR_HANDLER

Functions
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 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. More...
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. More...

Typedef Documentation

OUTLINE_ERROR_HANDLER

typedef const std::function<void( const wxString& msg, BOARD_ITEM* itemA, BOARD_ITEM* itemB, const VECTOR2I& pt )> OUTLINE_ERROR_HANDLER

Definition at line 33 of file convert_shape_list_to_polygon.h.

Function Documentation

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.

{
 PCB_TYPE_COLLECTOR items;
 bool success = false;
 
 SHAPE_POLY_SET fpHoles;
 
 // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
 
 for( int ii = 0; ii < items.GetCount(); ++ii )
 items[ii]->ClearFlags( SKIP_STRUCT );
 
 for( FOOTPRINT* fp : aBoard->Footprints() )
 {
 PCB_TYPE_COLLECTOR fpItems;
 fpItems.Collect( fp, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
 
 std::vector<PCB_SHAPE*> fpSegList;
 
 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
 {
 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
 
 if( fpSeg->GetLayer() == Edge_Cuts )
 fpSegList.push_back( fpSeg );
 }
 
 if( !fpSegList.empty() )
 {
 SHAPE_POLY_SET fpOutlines;
 success = ConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
 false,
 // don't report errors here; the second pass also
 // gets an opportunity to use these segments
 nullptr );
 
 if( success && isCopperOutside( fp, fpOutlines ) )
 {
 fpHoles.Append( fpOutlines );
 }
 else
 {
 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
 // in contention for the board outline builds.
 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
 fpItems[ii]->ClearFlags( SKIP_STRUCT );
 }
 }
 }
 
 // Make a working copy of aSegList, because the list is modified during calculations
 std::vector<PCB_SHAPE*> segList;
 
 for( int ii = 0; ii < items.GetCount(); ii++ )
 {
 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
 
 // Skip anything already used to generate footprint holes (above)
 if( seg->GetFlags() & SKIP_STRUCT )
 continue;
 
 if( seg->GetLayer() == Edge_Cuts )
 segList.push_back( seg );
 }
 
 if( segList.size() )
 {
 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
 true, aErrorHandler );
 }
 
 if( !success || !aOutlines.OutlineCount() )
 {
 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
 // create a rectangular outline, or, failing that, the bounding box of the items on
 // the board.
 
 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
 
 // If null area, uses the global bounding box.
 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
 bbbox = aBoard->ComputeBoundingBox();
 
 // Ensure non null area. If happen, gives a minimal size.
 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
 
 aOutlines.RemoveAllContours();
 aOutlines.NewOutline();
 
 wxPoint corner;
 aOutlines.Append( bbbox.GetOrigin() );
 
 corner.x = bbbox.GetOrigin().x;
 corner.y = bbbox.GetEnd().y;
 aOutlines.Append( corner );
 
 aOutlines.Append( bbbox.GetEnd() );
 
 corner.x = bbbox.GetEnd().x;
 corner.y = bbbox.GetOrigin().y;
 aOutlines.Append( corner );
 }
 
 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
 {
 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
 
 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
 {
 if( aOutlines.Outline( jj ).PointInside( holePt ) )
 {
 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
 break;
 }
 }
 }
 
 return success;
}

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().

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 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.

Optionally, it can be limited to a single top-level closed outline.

Parameters

aShapeList	the initial list of drawsegments (only lines, circles and arcs).
aPolygons	will contain the complex polygon.
aErrorMax	is the max error distance when polygonizing a curve (internal units)
aChainingEpsilon	is the max distance from one endPt to the next startPt (internal units)
aAllowDisjoint	indicates multiple top-level outlines are allowed
aErrorHandler	= an optional error handler

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

aShapeList	the initial list of SHAPEs (only lines, circles and arcs).
aPolygons	will contain the complex polygon.
aErrorMax	is the max error distance when polygonizing a curve (internal units)
aChainingEpsilon	is the max error distance when polygonizing a curve (internal units)
aAllowDisjoint	indicates multiple top-level outlines are allowed
aErrorHandler	= an optional error handler

Definition at line 175 of file convert_shape_list_to_polygon.cpp.

{
 if( aShapeList.size() == 0 )
 return true;
 
 bool selfIntersecting = false;
 
 wxString msg;
 PCB_SHAPE* graphic = nullptr;
 
 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
 
 // Keep a list of where the various shapes came from so after doing our combined-polygon
 // tests we can still report errors against the individual graphic items.
 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> shapeOwners;
 
 auto fetchOwner =
 [&]( const SEG& seg ) -> PCB_SHAPE*
 {
 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
 return it == shapeOwners.end() ? nullptr : it->second;
 };
 
 PCB_SHAPE* prevGraphic = nullptr;
 VECTOR2I prevPt;
 
 std::vector<SHAPE_LINE_CHAIN> contours;
 
 for( PCB_SHAPE* shape : startCandidates )
 shape->ClearFlags( SKIP_STRUCT );
 
 while( startCandidates.size() )
 {
 graphic = (PCB_SHAPE*) *startCandidates.begin();
 graphic->SetFlags( SKIP_STRUCT );
 startCandidates.erase( startCandidates.begin() );
 
 contours.emplace_back();
 
 SHAPE_LINE_CHAIN& currContour = contours.back();
 bool firstPt = true;
 
 // Circles, rects and polygons are closed shapes unto themselves (and do not combine
 // with other shapes), so process them separately.
 if( graphic->GetShape() == SHAPE_T::POLY )
 {
 EDA_ANGLE orientation = ANGLE_0;
 VECTOR2I offset = VECTOR2I( 0, 0 );
 
 if( graphic->GetParentFootprint() )
 {
 orientation = graphic->GetParentFootprint()->GetOrientation();
 offset = graphic->GetParentFootprint()->GetPosition();
 }
 
 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
 {
 VECTOR2I pt = *it;
 RotatePoint( pt, orientation );
 pt += offset;
 
 currContour.Append( pt );
 
 if( firstPt )
 firstPt = false;
 else
 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
 
 prevPt = pt;
 }
 
 currContour.SetClosed( true );
 }
 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
 {
 // make a circle by segments;
 VECTOR2I center = graphic->GetCenter();
 VECTOR2I start = center;
 int radius = graphic->GetRadius();
 int steps = GetArcToSegmentCount( radius, aErrorMax, FULL_CIRCLE );
 VECTOR2I nextPt;
 
 start.x += radius;
 
 for( int step = 0; step < steps; ++step )
 {
 nextPt = start;
 RotatePoint( nextPt, center, ANGLE_360 * step / steps );
 currContour.Append( nextPt );
 
 if( firstPt )
 firstPt = false;
 else
 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
 
 prevPt = nextPt;
 }
 
 currContour.SetClosed( true );
 }
 else if( graphic->GetShape() == SHAPE_T::RECT )
 {
 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
 
 for( const VECTOR2I& pt : pts )
 {
 currContour.Append( pt );
 
 if( firstPt )
 firstPt = false;
 else
 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
 
 prevPt = pt;
 }
 
 currContour.SetClosed( true );
 }
 else
 {
 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
 // from here.
 
 VECTOR2I startPt = graphic->GetEnd();
 prevPt = startPt;
 currContour.Append( prevPt );
 
 // do not append the other end point yet, this first 'graphic' might be an arc
 for(;;)
 {
 switch( graphic->GetShape() )
 {
 case SHAPE_T::RECT:
 case SHAPE_T::CIRCLE:
 {
 // As a non-first item, closed shapes can't be anything but self-intersecting
 
 if( aErrorHandler )
 {
 wxASSERT( prevGraphic );
 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
 }
 
 selfIntersecting = true;
 
 // A closed shape will finish where it started, so no point in updating prevPt
 break;
 }
 
 case SHAPE_T::SEGMENT:
 {
 VECTOR2I nextPt;
 
 // Use the line segment end point furthest away from prevPt as we assume
 // the other end to be ON prevPt or very close to it.
 
 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
 nextPt = graphic->GetEnd();
 else
 nextPt = graphic->GetStart();
 
 currContour.Append( nextPt );
 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
 prevPt = nextPt;
 }
 break;
 
 case SHAPE_T::ARC:
 // We do not support arcs in polygons, so approximate an arc with a series of
 // short lines and put those line segments into the !same! PATH.
 {
 VECTOR2I pstart = graphic->GetStart();
 VECTOR2I pend = graphic->GetEnd();
 VECTOR2I pcenter = graphic->GetCenter();
 EDA_ANGLE angle = -graphic->GetArcAngle();
 int radius = graphic->GetRadius();
 int steps = GetArcToSegmentCount( radius, aErrorMax, angle );
 
 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
 {
 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
 
 angle = -angle;
 std::swap( pstart, pend );
 }
 
 // Create intermediate points between start and end:
 for( int step = 1; step < steps; ++step )
 {
 EDA_ANGLE rotation = ( angle * step ) / steps;
 VECTOR2I pt = pstart;
 
 RotatePoint( pt, pcenter, rotation );
 
 currContour.Append( pt );
 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
 prevPt = pt;
 }
 
 // Append the last arc end point
 currContour.Append( pend );
 shapeOwners[ std::make_pair( prevPt, pend ) ] = graphic;
 prevPt = pend;
 }
 break;
 
 case SHAPE_T::BEZIER:
 // We do not support Bezier curves in polygons, so approximate with a series
 // of short lines and put those line segments into the !same! PATH.
 {
 VECTOR2I nextPt;
 bool reverse = false;
 
 // Use the end point furthest away from prevPt as we assume the other
 // end to be ON prevPt or very close to it.
 
 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
 {
 nextPt = graphic->GetEnd();
 }
 else
 {
 nextPt = graphic->GetStart();
 reverse = true;
 }
 
 if( reverse )
 {
 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
 {
 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
 currContour.Append( pt );
 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
 prevPt = pt;
 }
 }
 else
 {
 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
 {
 currContour.Append( pt );
 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
 prevPt = pt;
 }
 }
 
 prevPt = nextPt;
  }
 break;
 
 default:
 UNIMPLEMENTED_FOR( graphic->SHAPE_T_asString() );
 return false;
 }
 
 // Get next closest segment.
 
 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
 
 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
 {
 prevGraphic = graphic;
 graphic = nextGraphic;
 graphic->SetFlags( SKIP_STRUCT );
 startCandidates.erase( graphic );
 continue;
 }
 
 // Finished, or ran into trouble...
 
 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
 {
 currContour.SetClosed( true );
 break;
 }
 else if( nextGraphic ) // encountered already-used segment, but not at the start
  {
 if( aErrorHandler )
 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
 
 break;
 }
 else // encountered discontinuity
 {
 if( aErrorHandler )
 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
 
 break;
 }
 }
 }
 }
 
 for( const SHAPE_LINE_CHAIN& contour : contours )
 {
 if( !contour.IsClosed() )
 return false;
 }
 
 // First, collect the parents of each contour
 //
 std::map<int, std::vector<int>> contourToParentIndexesMap;
 
 for( size_t ii = 0; ii < contours.size(); ++ii )
 {
 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
 std::vector<int> parents;
 
 for( size_t jj = 0; jj < contours.size(); ++jj )
 {
 if( jj == ii )
 continue;
 
 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
 
 if( parentCandidate.PointInside( firstPt ) )
 parents.push_back( jj );
 }
 
 contourToParentIndexesMap[ii] = parents;
 }
 
 // Next add those that are top-level outlines to the SHAPE_POLY_SET
 //
 std::map<int, int> contourToOutlineIdxMap;
 
 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
 {
 if( parentIndexes.size() %2 == 0 )
 {
 // Even number of parents; top-level outline
 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
 {
 if( aErrorHandler )
 {
 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
 
 if( a && b )
 {
 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
 contours[ contourIndex ].GetPoint( 0 ) );
 }
 }
 
 return false;
 }
 
 aPolygons.AddOutline( contours[ contourIndex ] );
 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
 }
 }
 
 // And finally add the holes
 //
 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
 {
 if( parentIndexes.size() %2 == 1 )
 {
 // Odd number of parents; we're a hole in the parent which has one fewer parents
 // than we have.
 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
 
 for( int parentContourIdx : parentIndexes )
 {
 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
 {
 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
 aPolygons.AddHole( hole, outlineIdx );
 break;
 }
 }
 }
 }
 
 // All of the silliness that follows is to work around the segment iterator while checking
 // for collisions.
 // TODO: Implement proper segment and point iterators that follow std
 
 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
 {
 auto seg2 = seg1;
 
 for( ++seg2; seg2; seg2++ )
 {
 // Check for exact overlapping segments.
 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
 {
 if( aErrorHandler )
 {
 BOARD_ITEM* a = fetchOwner( *seg1 );
 BOARD_ITEM* b = fetchOwner( *seg2 );
 
 if( a && b )
 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
 }
 
 selfIntersecting = true;
 }
 
 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
 {
 if( aErrorHandler )
 {
 BOARD_ITEM* a = fetchOwner( *seg1 );
 BOARD_ITEM* b = fetchOwner( *seg2 );
 
 if( a && b )
 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
 }
 
 selfIntersecting = true;
 }
 }
 }
 
 return !selfIntersecting;
}

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().