convert_drawsegment_list_to_polygon.h File Reference

functions to convert a shape built with DRAWSEGMENTS to a polygon. More...

Go to the source code of this file.

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

Functions
bool	ConvertOutlineToPolygon (std::vector< PCB_SHAPE * > &aSegList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
	Function ConvertOutlineToPolygon build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a outline, therefore 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=nullptr)
	Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer. More...

Detailed Description

functions to convert a shape built with DRAWSEGMENTS to a polygon.

expecting the shape describes shape similar to a polygon

Definition in file convert_drawsegment_list_to_polygon.h.

Typedef Documentation

OUTLINE_ERROR_HANDLER

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

Definition at line 35 of file convert_drawsegment_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 883 of file convert_drawsegment_list_to_polygon.cpp.

{
    PCB_TYPE_COLLECTOR  items;
    bool                success = false;

    // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
    static const KICAD_T  scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
    items.Collect( aBoard, scan_graphics );

    // 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++ )
    {
        if( items[ii]->GetLayer() == Edge_Cuts )
            segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
    }

    if( segList.size() )
    {
        success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
                                           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.

        EDA_RECT 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( Millimeter2iu( 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 );
    }

    return success;
}

References SHAPE_POLY_SET::Append(), PCB_TYPE_COLLECTOR::Collect(), BOARD::ComputeBoundingBox(), ConvertOutlineToPolygon(), Edge_Cuts, EOT, BOARD::GetBoardEdgesBoundingBox(), COLLECTOR::GetCount(), EDA_RECT::GetEnd(), EDA_RECT::GetHeight(), EDA_RECT::GetOrigin(), EDA_RECT::GetWidth(), EDA_RECT::Inflate(), Millimeter2iu(), SHAPE_POLY_SET::NewOutline(), SHAPE_POLY_SET::OutlineCount(), PCB_FP_SHAPE_T, PCB_SHAPE_T, and SHAPE_POLY_SET::RemoveAllContours().

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

ConvertOutlineToPolygon()

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

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

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

Parameters

aSegList	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)
aErrorHandler	= an optional error handler

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

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

Parameters

aSegList	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 error distance when polygonizing a curve (internal units)
aErrorHandler	= an optional error handler

Definition at line 178 of file convert_drawsegment_list_to_polygon.cpp.

{
    if( aSegList.size() == 0 )
        return true;

    bool polygonComplete = false;
    bool selfIntersecting = false;

    wxString   msg;
    PCB_SHAPE* graphic = nullptr;

    std::set<PCB_SHAPE*> startCandidates( aSegList.begin(), aSegList.end() );

    // Find edge point with minimum x, this should be in the outer polygon
    // which will define the perimeter polygon polygon.
    wxPoint xmin    = wxPoint( INT_MAX, 0 );
    int     xmini   = 0;

    for( size_t i = 0; i < aSegList.size(); i++ )
    {
        graphic = (PCB_SHAPE*) aSegList[i];
        graphic->ClearFlags( SKIP_STRUCT );

        switch( graphic->GetShape() )
        {
        case PCB_SHAPE_TYPE::RECT:
        case PCB_SHAPE_TYPE::SEGMENT:
            {
                if( graphic->GetStart().x < xmin.x )
                {
                    xmin    = graphic->GetStart();
                    xmini   = i;
                }

                if( graphic->GetEnd().x < xmin.x )
                {
                    xmin    = graphic->GetEnd();
                    xmini   = i;
                }
            }
            break;

        case PCB_SHAPE_TYPE::ARC:
            {
                wxPoint  pstart = graphic->GetArcStart();
                wxPoint  center = graphic->GetCenter();
                double   angle  = -graphic->GetAngle();
                double   radius = graphic->GetRadius();
                int      steps  = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
                wxPoint  pt;

                for( int step = 1; step<=steps; ++step )
                {
                    double rotation = ( angle * step ) / steps;

                    pt = pstart;

                    RotatePoint( &pt, center, rotation );

                    if( pt.x < xmin.x )
                    {
                        xmin  = pt;
                        xmini = i;
                    }
                }
            }
            break;

        case PCB_SHAPE_TYPE::CIRCLE:
            {
                wxPoint pt = graphic->GetCenter();

                // pt has minimum x point
                pt.x -= graphic->GetRadius();

                // when the radius <= 0, this is a mal-formed circle. Skip it
                if( graphic->GetRadius() > 0 && pt.x < xmin.x )
                {
                    xmin  = pt;
                    xmini = i;
                }
            }
            break;

        case PCB_SHAPE_TYPE::CURVE:
            {
                graphic->RebuildBezierToSegmentsPointsList( graphic->GetWidth() );

                for( const wxPoint& pt : graphic->GetBezierPoints() )
                {
                    if( pt.x < xmin.x )
                    {
                        xmin  = pt;
                        xmini = i;
                    }
                }
            }
            break;

        case PCB_SHAPE_TYPE::POLYGON:
            {
                const SHAPE_POLY_SET poly = graphic->GetPolyShape();
                double               orientation = 0.0;
                VECTOR2I             offset = VECTOR2I( 0, 0 );

                if( graphic->GetParentFootprint() )
                {
                    orientation = graphic->GetParentFootprint()->GetOrientation();
                    offset = graphic->GetParentFootprint()->GetPosition();
                }

                for( auto iter = poly.CIterate(); iter; iter++ )
                {
                    VECTOR2I pt = *iter;
                    RotatePoint( pt, orientation );
                    pt += offset;

                    if( pt.x < xmin.x )
                    {
                        xmin.x = pt.x;
                        xmin.y = pt.y;
                        xmini = i;
                    }
                }
            }
            break;

        default:
            break;
        }
    }

    // Keep a list of where the various segments 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*> segOwners;

    auto fetchOwner =
            [&]( const SEG& seg ) -> PCB_SHAPE*
            {
                auto it = segOwners.find( std::make_pair( seg.A, seg.B ) );
                return it == segOwners.end() ? nullptr : it->second;
            };

    // Grab the left most point, assume its on the board's perimeter, and see if we can put
    // enough graphics together by matching endpoints to formulate a cohesive polygon.

    PCB_SHAPE* prevGraphic = nullptr;
    wxPoint    prevPt;

    graphic = (PCB_SHAPE*) aSegList[xmini];
    graphic->SetFlags( SKIP_STRUCT );
    startCandidates.erase( graphic );

    // Output the outline perimeter as polygon.
    if( graphic->GetShape() == PCB_SHAPE_TYPE::CIRCLE )
    {
        TransformCircleToPolygon( aPolygons, graphic->GetCenter(), graphic->GetRadius(),
                                  ARC_LOW_DEF, ERROR_INSIDE );
        polygonComplete = true;
    }
    else if( graphic->GetShape() == PCB_SHAPE_TYPE::RECT )
    {
        std::vector<wxPoint> pts = graphic->GetRectCorners();

        aPolygons.NewOutline();

        for( const wxPoint& pt : pts )
            aPolygons.Append( pt );

        segOwners[ std::make_pair( pts[0], pts[1] ) ] = graphic;
        segOwners[ std::make_pair( pts[1], pts[2] ) ] = graphic;
        segOwners[ std::make_pair( pts[2], pts[3] ) ] = graphic;
        segOwners[ std::make_pair( pts[3], pts[0] ) ] = graphic;

        polygonComplete = true;
    }
    else if( graphic->GetShape() == PCB_SHAPE_TYPE::POLYGON )
    {
        double   orientation = 0.0;
        VECTOR2I offset = VECTOR2I( 0, 0 );

        if( graphic->GetParentFootprint() )
        {
            orientation = graphic->GetParentFootprint()->GetOrientation();
            offset = graphic->GetParentFootprint()->GetPosition();
        }

        aPolygons.NewOutline();
        bool first = true;

        for( auto it = graphic->GetPolyShape().CIterate( 0 ); it; it++ )
        {
            VECTOR2I pt = *it;
            RotatePoint( pt, orientation );
            pt += offset;
            aPolygons.Append( pt );

            if( first )
                first = false;
            else
                segOwners[ std::make_pair( prevPt, pt ) ] = graphic;

            prevPt = (wxPoint) pt;
        }

        polygonComplete = true;
    }
    else
    {
        // Polygon start point. Arbitrarily chosen end of the
        // segment and build the poly from here.

        wxPoint startPt = graphic->GetShape() == PCB_SHAPE_TYPE::ARC ? graphic->GetArcEnd()
                                                       : graphic->GetEnd();

        prevPt = startPt;
        aPolygons.NewOutline();
        aPolygons.Append( prevPt );

        // Do not append the other end point yet of this 'graphic', this first
        // 'graphic' might be an arc or a curve.

        for(;;)
        {
            switch( graphic->GetShape() )
            {
            case PCB_SHAPE_TYPE::RECT:
            case PCB_SHAPE_TYPE::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 PCB_SHAPE_TYPE::SEGMENT:
            {
                wxPoint  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();

                aPolygons.Append( nextPt );
                segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
                prevPt = nextPt;
            }
                break;

            case PCB_SHAPE_TYPE::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.

                wxPoint pstart  = graphic->GetArcStart();
                wxPoint pend    = graphic->GetArcEnd();
                wxPoint pcenter = graphic->GetCenter();
                double  angle   = -graphic->GetAngle();
                double  radius  = graphic->GetRadius();
                int     steps   = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );

                if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
                {
                    wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), aChainingEpsilon ) );

                    angle = -angle;
                    std::swap( pstart, pend );
                }

                // Create intermediate points between start and end:
                for( int step = 1; step < steps; ++step )
                {
                    double rotation = ( angle * step ) / steps;
                    wxPoint pt = pstart;
                    RotatePoint( &pt, pcenter, rotation );

                    aPolygons.Append( pt );
                    segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
                    prevPt = pt;
                }

                // Append the last arc end point
                aPolygons.Append( pend );
                segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
                prevPt = pend;
            }
                break;

            case PCB_SHAPE_TYPE::CURVE:
            {
                // 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.

                wxPoint nextPt;
                bool    first = true;
                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 wxPoint& pt = graphic->GetBezierPoints()[jj];
                        aPolygons.Append( pt );

                        if( first )
                            first = false;
                        else
                            segOwners[ std::make_pair( prevPt, pt ) ] = graphic;

                        prevPt = pt;
                    }
                }
                else
                {
                    for( const wxPoint& pt : graphic->GetBezierPoints() )
                    {
                        aPolygons.Append( pt );

                        if( first )
                            first = false;
                        else
                            segOwners[ std::make_pair( prevPt, pt ) ] = graphic;

                        prevPt = pt;
                    }
                }

                prevPt = nextPt;
            }
                break;

            default:
                wxFAIL_MSG( "Unsupported PCB_SHAPE type "
                                + BOARD_ITEM::ShowShape( graphic->GetShape() ) );
                return false;
            }

            // Get next closest segment.

            PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, 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 ) )
            {
                polygonComplete = true;
                break;
            }
            else if( nextGraphic )  // encountered already-used segment, but not at the start
            {
                if( aErrorHandler )
                    (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );

                polygonComplete = false;
                break;
            }
            else                    // encountered discontinuity
            {
                if( aErrorHandler )
                    (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );

                polygonComplete = false;
                break;
            }
        }
    }

    int holeNum = -1;

    while( startCandidates.size() )
    {
        int  hole = aPolygons.NewHole();
        bool firstPt = true;
        holeNum++;

        graphic = (PCB_SHAPE*) *startCandidates.begin();
        graphic->SetFlags( SKIP_STRUCT );
        startCandidates.erase( startCandidates.begin() );

        // Both circles and polygons on the edge cuts layer are closed items that
        // do not connect to other elements, so we process them independently
        if( graphic->GetShape() == PCB_SHAPE_TYPE::POLYGON )
        {
            double   orientation = 0.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;

                aPolygons.Append( pt, -1, hole );

                if( firstPt )
                    firstPt = false;
                else
                    segOwners[ std::make_pair( prevPt, pt ) ] = graphic;

                prevPt = (wxPoint) pt;
            }
        }
        else if( graphic->GetShape() == PCB_SHAPE_TYPE::CIRCLE )
        {
            // make a circle by segments;
            wxPoint  center  = graphic->GetCenter();
            double   angle   = 3600.0;
            wxPoint  start   = center;
            int      radius  = graphic->GetRadius();
            int      steps   = GetArcToSegmentCount( radius, aErrorMax, 360.0 );
            wxPoint  nextPt;

            start.x += radius;

            for( int step = 0; step < steps; ++step )
            {
                double rotation = ( angle * step ) / steps;
                nextPt = start;
                RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
                aPolygons.Append( nextPt, -1, hole );

                if( firstPt )
                    firstPt = false;
                else
                    segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;

                prevPt = nextPt;
            }
        }
        else if( graphic->GetShape() == PCB_SHAPE_TYPE::RECT )
        {
            std::vector<wxPoint> pts = graphic->GetRectCorners();

            for( const wxPoint& pt : pts )
            {
                aPolygons.Append( pt, -1, hole );

                if( firstPt )
                    firstPt = false;
                else
                    segOwners[ std::make_pair( prevPt, pt ) ] = graphic;

                prevPt = (wxPoint) pt;
            }
        }
        else
        {
            // Polygon start point. Arbitrarily chosen end of the segment and build the poly
            // from here.

            wxPoint startPt( graphic->GetEnd() );
            prevPt = graphic->GetEnd();
            aPolygons.Append( prevPt, -1, hole );

            // do not append the other end point yet, this first 'graphic' might be an arc
            for(;;)
            {
                switch( graphic->GetShape() )
                {
                case PCB_SHAPE_TYPE::SEGMENT:
                    {
                        wxPoint 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();

                        aPolygons.Append( nextPt, -1, hole );
                        segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
                        prevPt = nextPt;
                    }
                    break;

                case PCB_SHAPE_TYPE::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.
                    {
                        wxPoint pstart  = graphic->GetArcStart();
                        wxPoint pend    = graphic->GetArcEnd();
                        wxPoint pcenter = graphic->GetCenter();
                        double  angle   = -graphic->GetAngle();
                        int     radius  = graphic->GetRadius();
                        int     steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );

                        if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
                        {
                            wxASSERT( close_enough( prevPt, graphic->GetArcEnd(),
                                                    aChainingEpsilon ) );

                            angle = -angle;
                            std::swap( pstart, pend );
                        }

                        // Create intermediate points between start and end:
                         for( int step = 1; step < steps; ++step )
                        {
                            double rotation = ( angle * step ) / steps;
                            wxPoint pt = pstart;
                            RotatePoint( &pt, pcenter, rotation );

                            aPolygons.Append( pt, -1, hole );
                            segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
                            prevPt = pt;
                        }

                        // Append the last arc end point
                        aPolygons.Append( pend, -1, hole );
                        segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
                        prevPt = pend;
                    }
                    break;

                case PCB_SHAPE_TYPE::CURVE:
                    // 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.
                    {
                        wxPoint 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 wxPoint& pt = graphic->GetBezierPoints()[jj];
                                aPolygons.Append( pt, -1, hole );
                                segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
                                prevPt = pt;
                            }
                        }
                        else
                        {
                            for( const wxPoint& pt : graphic->GetBezierPoints() )
                            {
                                aPolygons.Append( pt, -1, hole );
                                segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
                                prevPt = pt;
                            }
                        }

                        prevPt = nextPt;
                    }
                    break;

                default:
                    wxFAIL_MSG( "Unsupported PCB_SHAPE type "
                                    + BOARD_ITEM::ShowShape( graphic->GetShape() ) );

                    return false;
                }

                // Get next closest segment.

                PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );

                if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
                {
                    graphic = nextGraphic;
                    graphic->SetFlags( SKIP_STRUCT );
                    startCandidates.erase( graphic );
                    continue;
                }

                // Finished, or ran into trouble...

                if( close_enough( startPt, prevPt, aChainingEpsilon ) )
                {
                    break;
                }
                else if( nextGraphic )  // encountered already-used segment, but not at the start
                {
                    if( aErrorHandler )
                        (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );

                    polygonComplete = false;
                    break;
                }
                else                    // encountered discontinuity
                {
                    if( aErrorHandler )
                        (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );

                    polygonComplete = false;
                    break;
                }
            }
        }
    }

    if( !polygonComplete )
        return false;

    // 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, (wxPoint) ( *seg1 ).A );
                }

                selfIntersecting = true;
            }

            if( boost::optional<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, (wxPoint) pt.get() );
                }

                selfIntersecting = true;
            }
        }
    }

    return !selfIntersecting;
}

References _, PNS::angle(), SHAPE_POLY_SET::Append(), ARC, CIRCLE, SHAPE_POLY_SET::CIterate(), EDA_ITEM::ClearFlags(), close_enough(), closer_to_first(), CURVE, ERROR_INSIDE, findNext(), PCB_SHAPE::GetAngle(), PCB_SHAPE::GetArcEnd(), PCB_SHAPE::GetArcStart(), GetArcToSegmentCount(), PCB_SHAPE::GetBezierPoints(), PCB_SHAPE::GetCenter(), PCB_SHAPE::GetEnd(), EDA_ITEM::GetFlags(), FOOTPRINT::GetOrientation(), PCB_SHAPE::GetParentFootprint(), PCB_SHAPE::GetPolyShape(), FOOTPRINT::GetPosition(), PCB_SHAPE::GetRadius(), PCB_SHAPE::GetRectCorners(), PCB_SHAPE::GetShape(), PCB_SHAPE::GetStart(), PCB_SHAPE::GetWidth(), SHAPE_POLY_SET::IterateSegmentsWithHoles(), SHAPE_POLY_SET::NewHole(), SHAPE_POLY_SET::NewOutline(), POLYGON, PCB_SHAPE::RebuildBezierToSegmentsPointsList(), RECT, RotatePoint(), SEGMENT, EDA_ITEM::SetFlags(), BOARD_ITEM::ShowShape(), SKIP_STRUCT, TransformCircleToPolygon(), VECTOR2< T >::x, and VECTOR2< T >::y.

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