shape_line_chain.cpp

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2013-2017 CERN
 * Copyright (C) 2013-2024 KiCad Developers, see AUTHORS.txt for contributors.
 *
 * @author Tomasz Wlostowski <[email protected]>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
#include <limits>
#include <math.h> // for hypot
#include <map>
#include <string> // for basic_string
 
#include <clipper.hpp>
#include <clipper2/clipper.h>
#include <core/kicad_algo.h> // for alg::run_on_pair
#include <geometry/circle.h>
#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
#include <geometry/shape_line_chain.h>
#include <geometry/shape_poly_set.h>
#include <math/box2.h> // for BOX2I
#include <math/util.h> // for rescale
#include <math/vector2d.h> // for VECTOR2, VECTOR2I
#include <math/box2_minmax.h>
#include <trigo.h> // for RotatePoint
 
class SHAPE;
 
const ssize_t SHAPE_LINE_CHAIN::SHAPE_IS_PT = -1;
const std::pair<ssize_t, ssize_t> SHAPE_LINE_CHAIN::SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT };
 
 
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<int>& aV)
 : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
{
 for(size_t i = 0; i < aV.size(); i+= 2 )
 {
 Append( aV[i], aV[i+1] );
 }
}
 
 
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed ) :
 SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
 m_closed( false ),
 m_width( 0 )
{
 m_points = aV;
 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
 SetClosed( aClosed );
}
 
 
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed ) :
 SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
 m_closed( false ),
 m_width( aArc.GetWidth() )
{
 Append( aArc );
 SetClosed( aClosed );
}
 
 
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath,
 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 const std::vector<SHAPE_ARC>& aArcBuffer ) :
 SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
 m_closed( true ), m_width( 0 )
{
 std::map<ssize_t, ssize_t> loadedArcs;
 m_points.reserve( aPath.size() );
 m_shapes.reserve( aPath.size() );
 
 auto loadArc =
 [&]( ssize_t aArcIndex ) -> ssize_t
 {
 if( aArcIndex == SHAPE_IS_PT )
 {
 return SHAPE_IS_PT;
 }
 else if( loadedArcs.count( aArcIndex ) == 0 )
 {
 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
 }
 
 return loadedArcs.at( aArcIndex );
 };
 
 for( size_t ii = 0; ii < aPath.size(); ++ii )
 {
 Append( aPath[ii].X, aPath[ii].Y );
 
 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
 }
 
 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
 // removed during Append() and we would have different number of shapes to points
 wxASSERT( m_shapes.size() == m_points.size() );
 
 // Clipper might mess up the rotation of the indices such that an arc can be split between
 // the end point and wrap around to the start point. Lets fix the indices up now
 fixIndicesRotation();
}
 
 
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const Clipper2Lib::Path64& aPath,
 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 const std::vector<SHAPE_ARC>& aArcBuffer ) :
 SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
 m_closed( true ), m_width( 0 )
{
 std::map<ssize_t, ssize_t> loadedArcs;
 m_points.reserve( aPath.size() );
 m_shapes.reserve( aPath.size() );
 
 auto loadArc =
 [&]( ssize_t aArcIndex ) -> ssize_t
 {
 if( aArcIndex == SHAPE_IS_PT )
 {
 return SHAPE_IS_PT;
 }
 else if( loadedArcs.count( aArcIndex ) == 0 )
 {
 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
 }
 
 return loadedArcs.at( aArcIndex );
 };
 
 for( size_t ii = 0; ii < aPath.size(); ++ii )
 {
 Append( aPath[ii].x, aPath[ii].y );
 
 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
 }
 
 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
 // removed during Append() and we would have different number of shapes to points
 wxASSERT( m_shapes.size() == m_points.size() );
 
 // Clipper might mess up the rotation of the indices such that an arc can be split between
 // the end point and wrap around to the start point. Lets fix the indices up now
 fixIndicesRotation();
}
 
 
ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation,
 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 std::vector<SHAPE_ARC>& aArcBuffer ) const
{
 ClipperLib::Path c_path;
 SHAPE_LINE_CHAIN input;
 bool orientation = Area( false ) >= 0;
 ssize_t shape_offset = aArcBuffer.size();
 
 if( orientation != aRequiredOrientation )
 input = Reverse();
 else
 input = *this;
 
 int pointCount = input.PointCount();
 c_path.reserve( pointCount );
 
 for( int i = 0; i < pointCount; i++ )
 {
 const VECTOR2I& vertex = input.CPoint( i );
 
 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
 size_t z_value_ptr = aZValueBuffer.size();
 aZValueBuffer.push_back( z_value );
 
 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
 }
 
 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
 
 return c_path;
}
 
 
Clipper2Lib::Path64 SHAPE_LINE_CHAIN::convertToClipper2( bool aRequiredOrientation,
 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 std::vector<SHAPE_ARC>& aArcBuffer ) const
{
 Clipper2Lib::Path64 c_path;
 SHAPE_LINE_CHAIN input;
 bool orientation = Area( false ) >= 0;
 ssize_t shape_offset = aArcBuffer.size();
 
 if( orientation != aRequiredOrientation )
 input = Reverse();
 else
 input = *this;
 
 int pointCount = input.PointCount();
 c_path.reserve( pointCount );
 
 for( int i = 0; i < pointCount; i++ )
 {
 const VECTOR2I& vertex = input.CPoint( i );
 
 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
 size_t z_value_ptr = aZValueBuffer.size();
 aZValueBuffer.push_back( z_value );
 
 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
 }
 
 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
 
 return c_path;
}
 
 
void SHAPE_LINE_CHAIN::fixIndicesRotation()
{
 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
 
 if( m_shapes.size() <= 1 )
 return;
 
 size_t rotations = 0;
 
 while( ArcIndex( 0 ) != SHAPE_IS_PT
 && !IsArcStart( 0 ) )
 {
 // Rotate right
 std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
 std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
 
 // Sanity check - avoid infinite loops (NB: wxCHECK is not thread-safe)
 if( rotations++ > m_shapes.size() )
 return;
 }
}
 
 
void SHAPE_LINE_CHAIN::mergeFirstLastPointIfNeeded()
{
 if( m_closed )
 {
 if( m_points.size() > 1 && m_points.front() == m_points.back() )
 {
 if( ArcIndex( m_shapes.size() - 1 ) != SHAPE_IS_PT )
 {
 m_shapes.front().second = m_shapes.front().first;
 m_shapes.front().first = ArcIndex( m_shapes.size() - 1 ) ;
 }
 
 m_points.pop_back();
 m_shapes.pop_back();
 
 fixIndicesRotation();
 }
 }
 else
 {
 if( m_points.size() > 1 && IsSharedPt( 0 ) )
 {
 // Create a duplicate point at the end
 m_points.push_back( m_points.front() );
 m_shapes.push_back( { m_shapes.front().first, SHAPE_IS_PT } );
 m_shapes.front().first = m_shapes.front().second;
 m_shapes.front().second = SHAPE_IS_PT;
 }
 }
}
 
 
void SHAPE_LINE_CHAIN::convertArc( ssize_t aArcIndex )
{
 if( aArcIndex < 0 )
 aArcIndex += m_arcs.size();
 
 if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
 return;
 
 // Clear the shapes references
 for( auto& sh : m_shapes )
 {
 alg::run_on_pair( sh,
 [&]( ssize_t& aShapeIndex )
 {
 if( aShapeIndex == aArcIndex )
 aShapeIndex = SHAPE_IS_PT;
 
 if( aShapeIndex > aArcIndex )
 --aShapeIndex;
 } );
 
 if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
 std::swap( sh.first, sh.second );
 }
 
 m_arcs.erase( m_arcs.begin() + aArcIndex );
}
 
 
void SHAPE_LINE_CHAIN::amendArc( size_t aArcIndex, const VECTOR2I& aNewStart,
 const VECTOR2I& aNewEnd )
{
 wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
 wxT( "Invalid arc index requested." ) );
 
 SHAPE_ARC& theArc = m_arcs[aArcIndex];
 
 // Try to preseve the centre of the original arc
 SHAPE_ARC newArc;
 newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
 theArc.IsClockwise() );
 
 m_arcs[aArcIndex] = newArc;
}
 
 
void SHAPE_LINE_CHAIN::splitArc( ssize_t aPtIndex, bool aCoincident )
{
 if( aPtIndex < 0 )
 aPtIndex += m_shapes.size();
 
 if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
 return; // Nothing to do
 
 if( !IsPtOnArc( aPtIndex ) )
 return; // Nothing to do
 
 wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
 wxT( "Invalid point index requested." ) );
 
 if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
 {
 if( aCoincident || aPtIndex == 0 )
 return; // nothing to do
 
 ssize_t firstArcIndex = m_shapes[aPtIndex].first;
 
 const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
 const VECTOR2I& newEnd = m_points[aPtIndex - 1];
 amendArc( firstArcIndex, newStart, newEnd );
 
 if( IsSharedPt( aPtIndex ) )
 {
 m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
 m_shapes[aPtIndex].second = SHAPE_IS_PT;
 }
 else
 {
 m_shapes[aPtIndex] = SHAPES_ARE_PT;
 }
 
 return;
 }
 
 ssize_t currArcIdx = ArcIndex( aPtIndex );
 SHAPE_ARC& currentArc = m_arcs[currArcIdx];
 
 SHAPE_ARC newArc1;
 SHAPE_ARC newArc2;
 
 VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
 VECTOR2I arc2Start = m_points[aPtIndex];
 
 newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
 currentArc.IsClockwise() );
 
 newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
 currentArc.IsClockwise() );
 
 if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
 {
 //Ignore newArc1 as it has zero points
 m_arcs[currArcIdx] = newArc2;
 }
 else
 {
 m_arcs[currArcIdx] = newArc1;
 m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
 
 if( aCoincident )
 {
 m_shapes[aPtIndex].second = currArcIdx + 1;
 aPtIndex++;
 }
 
 // Only change the arc indices for the second half of the point range
 for( int i = aPtIndex; i < PointCount(); i++ )
 {
 alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
 if( aIndex != SHAPE_IS_PT )
 aIndex++;
 } );
 }
 }
}
 
 
bool SHAPE_LINE_CHAIN_BASE::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
 VECTOR2I* aLocation ) const
{
 if( IsClosed() && PointInside( aP, aClearance ) )
 {
 if( aLocation )
 *aLocation = aP;
 
 if( aActual )
 *aActual = 0;
 
 return true;
 }
 
 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
 SEG::ecoord clearance_sq = SEG::Square( aClearance );
 VECTOR2I nearest;
 
 for( size_t i = 0; i < GetSegmentCount(); i++ )
 {
 const SEG& s = GetSegment( i );
 VECTOR2I pn = s.NearestPoint( aP );
 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
 
 if( dist_sq < closest_dist_sq )
 {
 nearest = pn;
 closest_dist_sq = dist_sq;
 
 if( closest_dist_sq == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( closest_dist_sq < clearance_sq && !aActual )
 break;
 }
 }
 
 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = sqrt( closest_dist_sq );
 
 return true;
 }
 
 return false;
}
 
 
bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
 VECTOR2I* aLocation ) const
{
 if( IsClosed() && PointInside( aP, aClearance ) )
 {
 if( aLocation )
 *aLocation = aP;
 
 if( aActual )
 *aActual = 0;
 
 return true;
 }
 
 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
 SEG::ecoord clearance_sq = SEG::Square( aClearance );
 VECTOR2I nearest;
 
 // Collide line segments
 for( size_t i = 0; i < GetSegmentCount(); i++ )
 {
 if( IsArcSegment( i ) )
 continue;
 
 const SEG& s = GetSegment( i );
 VECTOR2I pn = s.NearestPoint( aP );
 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
 
 if( dist_sq < closest_dist_sq )
 {
 nearest = pn;
 closest_dist_sq = dist_sq;
 
 if( closest_dist_sq == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( closest_dist_sq < clearance_sq && !aActual )
 break;
 }
 }
 
 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = sqrt( closest_dist_sq );
 
 return true;
 }
 
 // Collide arc segments
 for( size_t i = 0; i < ArcCount(); i++ )
 {
 const SHAPE_ARC& arc = Arc( i );
 
 // The arcs in the chain should have zero width
 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
 
 if( arc.Collide( aP, aClearance, aActual, aLocation ) )
 return true;
 }
 
 return false;
}
 
 
void SHAPE_LINE_CHAIN::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
{
 for( VECTOR2I& pt : m_points )
 RotatePoint( pt, aCenter, aAngle );
 
 for( SHAPE_ARC& arc : m_arcs )
 arc.Rotate( aAngle, aCenter );
}
 
 
bool SHAPE_LINE_CHAIN::ClosestSegmentsFast( const SHAPE_LINE_CHAIN& aOther, VECTOR2I& aPt0,
 VECTOR2I& aPt1 ) const
{
 const std::vector<VECTOR2I>& myPts = m_points;
 const std::vector<VECTOR2I>& otherPts = aOther.m_points;
 
 const int c_maxBoxes = 100;
 const int c_minPtsPerBox = 20;
 
 int myPointsPerBox = std::max( c_minPtsPerBox, int( myPts.size() / c_maxBoxes ) + 1 );
 int otherPointsPerBox = std::max( c_minPtsPerBox, int( otherPts.size() / c_maxBoxes ) + 1 );
 
 int myNumBoxes = ( myPts.size() + myPointsPerBox - 1 ) / myPointsPerBox;
 int otherNumBoxes = ( otherPts.size() + otherPointsPerBox - 1 ) / otherPointsPerBox;
 
 struct BOX
 {
 BOX2I_MINMAX bbox;
 VECTOR2I center;
 int radius;
 bool valid = false;
 };
 
 std::vector<BOX> myBoxes( myNumBoxes );
 std::vector<BOX> otherBoxes( otherNumBoxes );
 
 // Calculate bounding boxes
 for( size_t i = 0; i < myPts.size(); i++ )
 {
 const VECTOR2I pt = myPts[i];
 BOX& box = myBoxes[i / myPointsPerBox];
 
 if( box.valid )
 {
 box.bbox.Merge( pt );
 }
 else
 {
 box.bbox = BOX2I_MINMAX( pt );
 box.valid = true;
 }
 }
 
 for( size_t i = 0; i < otherPts.size(); i++ )
 {
 const VECTOR2I pt = otherPts[i];
 BOX& box = otherBoxes[i / otherPointsPerBox];
 
 if( box.valid )
 {
 box.bbox.Merge( pt );
 }
 else
 {
 box.bbox = BOX2I_MINMAX( pt );
 box.valid = true;
 }
 }
 
 // Store centers and radiuses
 for( BOX& box : myBoxes )
 {
 box.center = box.bbox.GetCenter();
 box.radius = int( box.bbox.GetDiameter() / 2 );
 }
 
 for( BOX& box : otherBoxes )
 {
 box.center = box.bbox.GetCenter();
 box.radius = int( box.bbox.GetDiameter() / 2 );
 }
 
 // Find closest pairs
 struct DIST_PAIR
 {
 DIST_PAIR( int64_t aDistSq, size_t aIdA, size_t aIdB ) :
 dist( aDistSq ), idA( aIdA ), idB( aIdB )
 {
 }
 
 int64_t dist;
 size_t idA;
 size_t idB;
 };
 
 std::vector<DIST_PAIR> pairsToTest;
 
 for( size_t ia = 0; ia < myBoxes.size(); ia++ )
 {
 for( size_t ib = 0; ib < otherBoxes.size(); ib++ )
 {
 const BOX& ca = myBoxes[ia];
 const BOX& cb = otherBoxes[ib];
 
 if( !ca.valid || !cb.valid )
 continue;
 
 VECTOR2L pA( ca.center );
 VECTOR2L pB( cb.center );
 
 int64_t dist = ( pB - pA ).EuclideanNorm();
 
 dist -= ca.radius;
 dist -= cb.radius;
 
 pairsToTest.emplace_back( dist, ia, ib );
 }
 }
 
 std::sort( pairsToTest.begin(), pairsToTest.end(),
 []( const DIST_PAIR& a, const DIST_PAIR& b )
 {
 return a.dist < b.dist;
 } );
 
 const int c_polyPairsLimit = 5;
 
 // Find closest segments in tested pairs
 int64_t total_closest_dist_sq = VECTOR2I::ECOORD_MAX;
 
 for( size_t pairId = 0; pairId < pairsToTest.size() && pairId < c_polyPairsLimit; pairId++ )
 {
 const DIST_PAIR& pair = pairsToTest[pairId];
 
 VECTOR2I ptA;
 VECTOR2I ptB;
 int64_t dist_sq;
 
 size_t myStartId = pair.idA * myPointsPerBox;
 size_t myEndId = myStartId + myPointsPerBox;
 
 if( myEndId > myPts.size() )
 myEndId = myPts.size();
 
 VECTOR2I myPrevPt = myPts[myStartId == 0 ? myPts.size() - 1 : myStartId - 1];
 
 size_t otherStartId = pair.idB * otherPointsPerBox;
 size_t otherEndId = otherStartId + otherPointsPerBox;
 
 if( otherEndId > otherPts.size() )
 otherEndId = otherPts.size();
 
 VECTOR2I otherPrevPt = otherPts[otherStartId == 0 ? otherPts.size() - 1 : otherStartId - 1];
 
 if( ClosestSegments( myPrevPt, myPts.begin() + myStartId, myPts.begin() + myEndId,
 otherPrevPt, otherPts.begin() + otherStartId,
 otherPts.begin() + otherEndId, ptA, ptB, dist_sq ) )
 {
 if( dist_sq < total_closest_dist_sq )
 {
 total_closest_dist_sq = dist_sq;
 aPt0 = ptA;
 aPt1 = ptB;
 }
 }
 }
 
 return total_closest_dist_sq != VECTOR2I::ECOORD_MAX;
}
 
 
bool SHAPE_LINE_CHAIN::ClosestSegments( const VECTOR2I& aMyPrevPt, const point_citer& aMyStart,
 const point_citer& aMyEnd, const VECTOR2I& aOtherPrevPt,
 const point_citer& aOtherStart,
 const point_citer& aOtherEnd, VECTOR2I& aPt0,
 VECTOR2I& aPt1, int64_t& aDistSq )
{
 if( aMyStart == aMyEnd )
 return false;
 
 if( aOtherStart == aOtherEnd )
 return false;
 
 int64_t closest_dist_sq = VECTOR2I::ECOORD_MAX;
 VECTOR2I lastPtA = aMyPrevPt;
 
 for( point_citer itA = aMyStart; itA != aMyEnd; itA++ )
 {
 const VECTOR2I& ptA = *itA;
 VECTOR2I lastPtB = aOtherPrevPt;
 
 for( point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
 {
 const VECTOR2I& ptB = *itB;
 
 SEG segA( lastPtA, ptA );
 SEG segB( lastPtB, ptB );
 
 VECTOR2I nearestA, nearestB;
 
 int64_t dist_sq;
 
 if( segA.NearestPoints( segB, nearestA, nearestB, dist_sq ) )
 {
 if( dist_sq < closest_dist_sq )
 {
 closest_dist_sq = dist_sq;
 aPt0 = nearestA;
 aPt1 = nearestB;
 }
 }
 
 lastPtB = ptB;
 }
 
 lastPtA = ptA;
 }
 
 aDistSq = closest_dist_sq;
 return closest_dist_sq != VECTOR2I::ECOORD_MAX;
}
 
 
bool SHAPE_LINE_CHAIN::ClosestPoints( const point_citer& aMyStart, const point_citer& aMyEnd,
 const point_citer& aOtherStart, const point_citer& aOtherEnd,
 VECTOR2I& aPt0, VECTOR2I& aPt1, int64_t& aDistSq )
{
 int64_t closest_dist_sq = VECTOR2I::ECOORD_MAX;
 
 for( point_citer itA = aMyStart; itA != aMyEnd; itA++ )
 {
 const VECTOR2I& ptA = *itA;
 
 for( point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
 {
 const VECTOR2I& ptB = *itB;
 
 ecoord dx = (ecoord) ptB.x - ptA.x;
 ecoord dy = (ecoord) ptB.y - ptA.y;
 
 SEG::ecoord dist_sq = dx * dx + dy * dy;
 
 if( dist_sq < closest_dist_sq )
 {
 closest_dist_sq = dist_sq;
 aPt0 = ptA;
 aPt1 = ptB;
 }
 }
 }
 
 aDistSq = closest_dist_sq;
 return closest_dist_sq != VECTOR2I::ECOORD_MAX;
}
 
 
bool SHAPE_LINE_CHAIN::ClosestPoints( const SHAPE_LINE_CHAIN& aOther, VECTOR2I& aPt0,
 VECTOR2I& aPt1 ) const
{
 ecoord dist_sq;
 
 return ClosestPoints( m_points.cbegin(), m_points.cend(), aOther.m_points.cbegin(),
 aOther.m_points.cend(), aPt0, aPt1, dist_sq );
}
 
 
bool SHAPE_LINE_CHAIN_BASE::Collide( const SEG& aSeg, int aClearance, int* aActual,
 VECTOR2I* aLocation ) const
{
 if( IsClosed() && PointInside( aSeg.A ) )
 {
 if( aLocation )
 *aLocation = aSeg.A;
 
 if( aActual )
 *aActual = 0;
 
 return true;
 }
 
 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
 SEG::ecoord clearance_sq = SEG::Square( aClearance );
 VECTOR2I nearest;
 
 for( size_t i = 0; i < GetSegmentCount(); i++ )
 {
 const SEG& s = GetSegment( i );
 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
 
 if( dist_sq < closest_dist_sq )
 {
 if( aLocation )
 nearest = s.NearestPoint( aSeg );
 
 closest_dist_sq = dist_sq;
 
 if( closest_dist_sq == 0)
 break;
 
 // If we're not looking for aActual then any collision will do
 if( closest_dist_sq < clearance_sq && !aActual )
 break;
 }
 }
 
 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = sqrt( closest_dist_sq );
 
 return true;
 }
 
 return false;
}
 
 
bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance, int* aActual,
 VECTOR2I* aLocation ) const
{
 if( IsClosed() && PointInside( aSeg.A ) )
 {
 if( aLocation )
 *aLocation = aSeg.A;
 
 if( aActual )
 *aActual = 0;
 
 return true;
 }
 
 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
 SEG::ecoord clearance_sq = SEG::Square( aClearance );
 VECTOR2I nearest;
 
 // Collide line segments
 for( size_t i = 0; i < GetSegmentCount(); i++ )
 {
 if( IsArcSegment( i ) )
 continue;
 
 const SEG& s = GetSegment( i );
 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
 
 if( dist_sq < closest_dist_sq )
 {
 if( aLocation )
 nearest = s.NearestPoint( aSeg );
 
 closest_dist_sq = dist_sq;
 
 if( closest_dist_sq == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( closest_dist_sq < clearance_sq && !aActual )
 break;
 }
 }
 
 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = sqrt( closest_dist_sq );
 
 return true;
 }
 
 int dist = std::numeric_limits<int>::max();
 SEG::ecoord closest_dist = sqrt( closest_dist_sq );
 
 // Collide arc segments
 for( size_t i = 0; i < ArcCount(); i++ )
 {
 const SHAPE_ARC& arc = Arc( i );
 VECTOR2I pos;
 
 // The arcs in the chain should have zero width
 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
 
 if( arc.Collide( aSeg, aClearance, aActual || aLocation ? &dist : nullptr,
 aLocation ? &pos : nullptr ) )
 {
 if( !aActual )
 return true;
 
 if( dist < closest_dist )
 {
 closest_dist = dist;
 nearest = pos;
 }
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 return true;
 }
 
 return false;
}
 
 
const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Reverse() const
{
 SHAPE_LINE_CHAIN a( *this );
 
 reverse( a.m_points.begin(), a.m_points.end() );
 reverse( a.m_shapes.begin(), a.m_shapes.end() );
 reverse( a.m_arcs.begin(), a.m_arcs.end() );
 
 for( auto& sh : a.m_shapes )
 {
 if( sh != SHAPES_ARE_PT )
 {
 alg::run_on_pair( sh,
 [&]( ssize_t& aShapeIndex )
 {
 if( aShapeIndex != SHAPE_IS_PT )
 aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
 } );
 
 if( sh.second != SHAPE_IS_PT )
 {
 // If the second element is populated, the first one should be too!
 assert( sh.first != SHAPE_IS_PT );
 
 // Switch round first and second in shared points, as part of reversing the chain
 std::swap( sh.first, sh.second );
 }
 }
 }
 
 for( SHAPE_ARC& arc : a.m_arcs )
 arc.Reverse();
 
 a.m_closed = m_closed;
 
 return a;
}
 
 
void SHAPE_LINE_CHAIN::ClearArcs()
{
 for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
 convertArc( arcIndex );
}
 
 
long long int SHAPE_LINE_CHAIN::Length() const
{
 long long int l = 0;
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 // Only include segments that aren't part of arc shapes
 if( !IsArcSegment(i) )
 l += CSegment( i ).Length();
 }
 
 for( size_t i = 0; i < ArcCount(); i++ )
 l += CArcs()[i].GetLength();
 
 return l;
}
 
 
void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
{
 for( auto& pt : m_points )
 {
 if( aX )
 pt.x = -pt.x + 2 * aRef.x;
 
 if( aY )
 pt.y = -pt.y + 2 * aRef.y;
 }
 
 for( auto& arc : m_arcs )
 arc.Mirror( aX, aY, aRef );
}
 
 
void SHAPE_LINE_CHAIN::Mirror( const SEG& axis )
{
 for( auto& pt : m_points )
 pt = axis.ReflectPoint( pt );
 
 for( auto& arc : m_arcs )
 arc.Mirror( axis );
}
 
 
void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
{
 Remove( aStartIndex, aEndIndex );
 Insert( aStartIndex, aP );
 assert( m_shapes.size() == m_points.size() );
}
 
 
void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
{
 if( aEndIndex < 0 )
 aEndIndex += PointCount();
 
 if( aStartIndex < 0 )
 aStartIndex += PointCount();
 
 // We only process lines in order in this house
 wxASSERT( aStartIndex <= aEndIndex );
 wxASSERT( aEndIndex < static_cast<int>( m_points.size() ) );
 
 SHAPE_LINE_CHAIN newLine = aLine;
 
 // Zero points to add?
 if( newLine.PointCount() == 0 )
 {
 Remove( aStartIndex, aEndIndex );
 return;
 }
 
 // Remove coincident points in the new line
 if( newLine.m_points.front() == m_points[aStartIndex] )
 {
 aStartIndex++;
 newLine.Remove( 0 );
 
 // Zero points to add?
 if( newLine.PointCount() == 0 )
 {
 Remove( aStartIndex, aEndIndex );
 return;
 }
 }
 
 if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
 {
 aEndIndex--;
 newLine.Remove( -1 );
 }
 
 Remove( aStartIndex, aEndIndex );
 
 // Zero points to add?
 if( newLine.PointCount() == 0 )
 return;
 
 // The total new arcs index is added to the new arc indices
 size_t prev_arc_count = m_arcs.size();
 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
 
 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
 {
 alg::run_on_pair( shape_pair,
 [&]( ssize_t& aShape )
 {
 if( aShape != SHAPE_IS_PT )
 aShape += prev_arc_count;
 } );
 }
 
 m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
 m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
 newLine.m_points.end() );
 m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
 
 assert( m_shapes.size() == m_points.size() );
}
 
 
void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
{
 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
 
 // Unwrap the chain first (correctly handling removing arc at
 // end of chain coincident with start)
 bool closedState = IsClosed();
 SetClosed( false );
 
 if( aEndIndex < 0 )
 aEndIndex += PointCount();
 
 if( aStartIndex < 0 )
 aStartIndex += PointCount();
 
 if( aStartIndex >= PointCount() || aEndIndex >= PointCount() || aStartIndex > aEndIndex)
 {
 SetClosed( closedState );
 return;
 }
 
 
 // Split arcs, making arcs coincident
 if( !IsArcStart( aStartIndex ) && IsPtOnArc( aStartIndex ) )
 splitArc( aStartIndex, false );
 
 if( IsSharedPt( aStartIndex ) ) // Don't delete the shared point
 aStartIndex += 1;
 
 if( !IsArcEnd( aEndIndex ) && IsPtOnArc( aEndIndex ) && aEndIndex < PointCount() - 1 )
 splitArc( aEndIndex + 1, true );
 
 if( IsSharedPt( aEndIndex ) ) // Don't delete the shared point
 aEndIndex -= 1;
 
 if( aStartIndex > aEndIndex )
 {
 SetClosed( closedState );
 return;
 }
 
 std::set<size_t> extra_arcs;
 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
 {
 if( aShapeIndex != SHAPE_IS_PT )
 extra_arcs.insert( aShapeIndex );
 };
 
 // Remove any overlapping arcs in the point range
 for( int i = aStartIndex; i <= aEndIndex; i++ )
 {
 if( IsSharedPt( i ) )
 {
 if( i == aStartIndex )
 {
 logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
 
 // Ensure that m_shapes has been built correctly.
 assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
 
 continue;
 }
 else if( i == aEndIndex )
 {
 logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
 
 // Ensure that m_shapes has been built correctly.
 assert( i > aStartIndex || ( IsSharedPt( i - 1 )
 ? m_shapes[i - 1].second == m_shapes[i].first
 : m_shapes[i - 1].first == m_shapes[i].first ) );
 continue;
 }
 }
 else
 {
 alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
 }
 }
 
 for( auto arc : extra_arcs )
 convertArc( arc );
 
 m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
 m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
 assert( m_shapes.size() == m_points.size() );
 
 SetClosed( closedState );
}
 
 
SEG::ecoord SHAPE_LINE_CHAIN_BASE::SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly ) const
{
 ecoord d = VECTOR2I::ECOORD_MAX;
 
 if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
 return 0;
 
 for( size_t s = 0; s < GetSegmentCount(); s++ )
 d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
 
 return d;
}
 
 
int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP, bool aExact )
{
 int ii = -1;
 int min_dist = 2;
 
 int found_index = Find( aP );
 
 if( found_index >= 0 && aExact )
 return found_index;
 
 for( int s = 0; s < SegmentCount(); s++ )
 {
 const SEG seg = CSegment( s );
 int dist = seg.Distance( aP );
 
 // make sure we are not producing a 'slightly concave' primitive. This might happen
 // if aP lies very close to one of already existing points.
 if( dist < min_dist && seg.A != aP && seg.B != aP )
 {
 min_dist = dist;
 if( found_index < 0 )
 ii = s;
 else if( s < found_index )
 ii = s;
 }
 }
 
 if( ii < 0 )
 ii = found_index;
 
 if( ii >= 0 )
 {
 // Don't create duplicate points
 if( GetPoint( ii ) == aP )
 return ii;
 
 size_t newIndex = static_cast<size_t>( ii ) + 1;
 
 if( IsArcSegment( ii ) )
 {
 m_points.insert( m_points.begin() + newIndex, aP );
 m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
 splitArc( newIndex, true ); // Make the inserted point a shared point
 }
 else
 {
 Insert( newIndex, aP );
 }
 
 return newIndex;
 }
 
 return -1;
}
 
 
int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP, int aThreshold ) const
{
 for( int s = 0; s < PointCount(); s++ )
 {
 if( aThreshold == 0 )
 {
 if( CPoint( s ) == aP )
 return s;
 }
 else
 {
 if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
 return s;
 }
 }
 
 return -1;
}
 
 
int SHAPE_LINE_CHAIN::FindSegment( const VECTOR2I& aP, int aThreshold ) const
{
 for( int s = 0; s < SegmentCount(); s++ )
 {
 if( CSegment( s ).Distance( aP ) <= aThreshold )
 return s;
 }
 
 return -1;
}
 
 
int SHAPE_LINE_CHAIN::ShapeCount() const
{
 wxCHECK2_MSG( m_points.size() == m_shapes.size(), return 0, "Invalid chain!" );
 
 if( m_points.size() < 2 )
 return 0;
 
 int numShapes = 1;
 
 for( int i = NextShape( 0 ); i != -1; i = NextShape( i ) )
 numShapes++;
 
 return numShapes;
}
 
 
SEG SHAPE_LINE_CHAIN::Segment( int aIndex ) const
{
 if( aIndex < 0 )
 aIndex += SegmentCount();
 
 wxCHECK( aIndex < SegmentCount() && aIndex >= 0,
 m_points.size() > 0 ? SEG( m_points.back(), m_points.back() ) : SEG( 0, 0, 0, 0 ) );
 
 if( aIndex == (int) ( m_points.size() - 1 ) && m_closed )
 return SEG( m_points[aIndex], m_points[0], aIndex );
 else
 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
}
 
 
int SHAPE_LINE_CHAIN::NextShape( int aPointIndex ) const
{
 if( aPointIndex < 0 )
 aPointIndex += PointCount();
 
 if( aPointIndex < 0 )
 return -1;
 
 int lastIndex = PointCount() - 1;
 
 // Last point?
 if( aPointIndex >= lastIndex )
 return -1; // we don't want to wrap around
 
 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
 {
 if( aPointIndex == lastIndex - 1 )
 {
 if( m_closed )
 return lastIndex;
 else
 return -1;
 }
 else
 {
 return aPointIndex + 1;
 }
 }
 
 int arcStart = aPointIndex;
 
 // The second element should only get populated when the point is shared between two shapes.
 // If not a shared point, then the index should always go on the first element.
 wxCHECK2_MSG( m_shapes[aPointIndex].first != SHAPE_IS_PT, return -1, "malformed chain!" );
 
 ssize_t currentArcIdx = ArcIndex( aPointIndex );
 
 // Now skip the rest of the arc
 while( aPointIndex < lastIndex && ArcIndex( aPointIndex ) == currentArcIdx )
 aPointIndex += 1;
 
 bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
 
 // We want the last vertex of the arc if the initial point was the start of one
 // Well-formed arcs should generate more than one point to travel above
 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
 aPointIndex -= 1;
 
 if( aPointIndex == lastIndex )
 {
 if( !m_closed || IsArcSegment( aPointIndex ) )
 return -1; //no shape
 else
 return lastIndex; // Segment between last point and the start of the chain
 }
 
 return aPointIndex;
}
 
 
void SHAPE_LINE_CHAIN::SetPoint( int aIndex, const VECTOR2I& aPos )
{
 if( aIndex < 0 )
 aIndex += PointCount();
 else if( aIndex >= PointCount() )
 aIndex -= PointCount();
 
 m_points[aIndex] = aPos;
 
 alg::run_on_pair( m_shapes[aIndex],
 [&]( ssize_t& aIdx )
 {
 if( aIdx != SHAPE_IS_PT )
 convertArc( aIdx );
 } );
}
 
 
void SHAPE_LINE_CHAIN::RemoveShape( int aPointIndex )
{
 if( aPointIndex < 0 )
 aPointIndex += PointCount();
 
 if( aPointIndex >= PointCount() || aPointIndex < 0 )
 return; // Invalid index, fail gracefully
 
 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
 {
 Remove( aPointIndex );
 return;
 }
 
 int start = aPointIndex;
 int end = aPointIndex;
 int arcIdx = ArcIndex( aPointIndex );
 
 if( !IsArcStart( start ) )
 {
 // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
 while( start > 0 && ArcIndex( static_cast<ssize_t>( start ) - 1 ) == arcIdx )
 start--;
 }
 
 if( !IsArcEnd( end ) || start == end )
 end = NextShape( end ); // can be -1 to indicate end of chain
 
 Remove( start, end );
}
 
 
const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
{
 SHAPE_LINE_CHAIN rv;
 
 if( aEndIndex < 0 )
 aEndIndex += PointCount();
 
 if( aStartIndex < 0 )
 aStartIndex += PointCount();
 
 // Bad programmer checks
 wxCHECK( aStartIndex >= 0, SHAPE_LINE_CHAIN() );
 wxCHECK( aEndIndex >= 0, SHAPE_LINE_CHAIN() );
 wxCHECK( aStartIndex < PointCount(), SHAPE_LINE_CHAIN() );
 wxCHECK( aEndIndex < PointCount(), SHAPE_LINE_CHAIN() );
 wxCHECK( aEndIndex >= aStartIndex, SHAPE_LINE_CHAIN() );
 
 int numPoints = static_cast<int>( m_points.size() );
 
 if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
 {
 // Cutting in middle of an arc, lets split it
 ssize_t arcToSplitIndex = ArcIndex( aStartIndex );
 const SHAPE_ARC& arcToSplit = Arc( arcToSplitIndex );
 
 // Copy the points as arc points
 for( size_t i = aStartIndex; arcToSplitIndex == ArcIndex( i ); i++ )
 {
 rv.m_points.push_back( m_points[i] );
 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
 rv.m_bbox.Merge( m_points[i] );
 }
 
 // Create a new arc from the existing one, with different start point.
 SHAPE_ARC newArc;
 
 VECTOR2I newArcStart = m_points[aStartIndex];
 
 newArc.ConstructFromStartEndCenter( newArcStart, arcToSplit.GetP1(),
 arcToSplit.GetCenter(),
 arcToSplit.IsClockwise() );
 
 
 rv.m_arcs.push_back( newArc );
 
 aStartIndex += rv.PointCount();
 }
 
 for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
 {
 if( i == -1 )
 return rv; // NextShape reached the end
 
 int nextShape = NextShape( i );
 bool isLastShape = nextShape < 0;
 
 if( IsArcStart( i ) )
 {
 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
 || ( nextShape > aEndIndex ) )
 {
 if( i == aEndIndex )
 {
 // Single point on an arc, just append the single point
 rv.Append( m_points[i] );
 return rv;
 }
 
 // Cutting in middle of an arc, lets split it
 ssize_t arcIndex = ArcIndex( i );
 const SHAPE_ARC& currentArc = Arc( arcIndex );
 
 // Copy the points as arc points
 for( ; i <= aEndIndex && i < numPoints; i++ )
 {
 if( arcIndex != ArcIndex( i ) )
 break;
 
 rv.m_points.push_back( m_points[i] );
 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
 rv.m_bbox.Merge( m_points[i] );
 }
 
 // Create a new arc from the existing one, with different end point.
 SHAPE_ARC newArc;
 
 VECTOR2I newArcEnd = m_points[aEndIndex];
 
 newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
 currentArc.GetCenter(),
 currentArc.IsClockwise() );
 
 
 rv.m_arcs.push_back( newArc );
 
 return rv;
 }
 else
 {
 // append the whole arc
 const SHAPE_ARC& currentArc = Arc( ArcIndex( i ) );
 rv.Append( currentArc );
 }
 
 if( isLastShape )
 return rv;
 }
 else
 {
 wxASSERT_MSG( !IsArcSegment( i ),
 wxT( "Still on an arc segment, we missed something..." ) );
 
 if( i == aStartIndex )
 rv.Append( m_points[i] );
 
 bool nextPointIsArc = isLastShape ? false : IsArcSegment( nextShape );
 
 if( !nextPointIsArc && i < SegmentCount() && i < aEndIndex )
 rv.Append( GetSegment( i ).B );
 }
 
 }
 
 return rv;
}
 
 
void SHAPE_LINE_CHAIN::Append( const SHAPE_LINE_CHAIN& aOtherLine )
{
 assert( m_shapes.size() == m_points.size() );
 
 if( aOtherLine.PointCount() == 0 )
 {
 return;
 }
 
 size_t num_arcs = m_arcs.size();
 m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
 
 auto fixShapeIndices =
 [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
 {
 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
 
 alg::run_on_pair( retval, [&]( ssize_t& aIndex )
 {
 if( aIndex != SHAPE_IS_PT )
 aIndex = aIndex + num_arcs;
 } );
 
 return retval;
 };
 
 if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
 {
 const VECTOR2I p = aOtherLine.CPoint( 0 );
 m_points.push_back( p );
 m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
 m_bbox.Merge( p );
 }
 else if( aOtherLine.IsArcSegment( 0 ) )
 {
 // Associate the new arc shape with the last point of this chain
 if( m_shapes.back() == SHAPES_ARE_PT )
 m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
 else
 m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
 }
 
 
 for( int i = 1; i < aOtherLine.PointCount(); i++ )
 {
 const VECTOR2I p = aOtherLine.CPoint( i );
 m_points.push_back( p );
 
 ssize_t arcIndex = aOtherLine.ArcIndex( i );
 
 if( arcIndex != ssize_t( SHAPE_IS_PT ) )
 {
 m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
 }
 else
 m_shapes.push_back( SHAPES_ARE_PT );
 
 m_bbox.Merge( p );
 }
 
 mergeFirstLastPointIfNeeded();
 
 assert( m_shapes.size() == m_points.size() );
}
 
 
void SHAPE_LINE_CHAIN::Append( const SHAPE_ARC& aArc )
{
 Append( aArc, SHAPE_ARC::DefaultAccuracyForPCB() );
}
 
 
void SHAPE_LINE_CHAIN::Append( const SHAPE_ARC& aArc, double aAccuracy )
{
 SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline( aAccuracy );
 
 if( chain.PointCount() > 2 )
 {
 chain.m_arcs.push_back( aArc );
 chain.m_arcs.back().SetWidth( 0 );
 
 for( auto& sh : chain.m_shapes )
 sh.first = 0;
 }
 
 Append( chain );
 
 assert( m_shapes.size() == m_points.size() );
}
 
 
void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
{
 if( aVertex == m_points.size() )
 {
 Append( aP );
 return;
 }
 
 wxCHECK( aVertex < m_points.size(), /* void */ );
 
 if( aVertex > 0 && IsPtOnArc( aVertex ) )
 splitArc( aVertex );
 
 //@todo need to check we aren't creating duplicate points
 m_points.insert( m_points.begin() + aVertex, aP );
 m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
 
 assert( m_shapes.size() == m_points.size() );
}
 
 
void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
{
 wxCHECK( aVertex < m_points.size(), /* void */ );
 
 if( aVertex > 0 && IsPtOnArc( aVertex ) )
 splitArc( aVertex );
 
 ssize_t arc_pos = m_arcs.size();
 
 for( auto arc_it = m_shapes.rbegin() ;
 arc_it != m_shapes.rend() + aVertex;
 arc_it++ )
 {
 if( *arc_it != SHAPES_ARE_PT )
 {
 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
 arc_pos++;
 }
 }
 
 //Increment all arc indices before inserting the new arc
 for( auto& sh : m_shapes )
 {
 alg::run_on_pair( sh,
 [&]( ssize_t& aIndex )
 {
 if( aIndex >= arc_pos )
 aIndex++;
 } );
 }
 
 SHAPE_ARC arcCopy( aArc );
 arcCopy.SetWidth( 0 );
 m_arcs.insert( m_arcs.begin() + arc_pos, arcCopy );
 
 //@todo need to check we aren't creating duplicate points at start or end
 auto& chain = aArc.ConvertToPolyline();
 m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
 
 //@todo need to check we aren't creating duplicate points at start or end
 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
 { arc_pos, SHAPE_IS_PT } );
 
 m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
 assert( m_shapes.size() == m_points.size() );
}
 
 
struct compareOriginDistance
{
 compareOriginDistance( const VECTOR2I& aOrigin ) :
 m_origin( aOrigin ) {};
 
 bool operator()( const SHAPE_LINE_CHAIN::INTERSECTION& aA,
 const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
 {
 return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
 }
 
 VECTOR2I m_origin;
};
 
 
int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
{
 for( int s = 0; s < SegmentCount(); s++ )
 {
 OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
 
 if( p )
 {
 INTERSECTION is;
 is.valid = true;
 is.index_our = s;
 is.index_their = -1;
 is.is_corner_our = is.is_corner_their = false;
 is.p = *p;
 aIp.push_back( is );
 }
 }
 
 compareOriginDistance comp( aSeg.A );
 sort( aIp.begin(), aIp.end(), comp );
 
 return aIp.size();
}
 
 
static inline void addIntersection( SHAPE_LINE_CHAIN::INTERSECTIONS& aIps, int aPc,
 const SHAPE_LINE_CHAIN::INTERSECTION& aP )
{
 if( aIps.size() == 0 )
 {
 aIps.push_back( aP );
 return;
 }
 
 aIps.push_back( aP );
}
 
 
int SHAPE_LINE_CHAIN::Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp,
 bool aExcludeColinearAndTouching, BOX2I* aChainBBox ) const
{
 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
 
 for( int s1 = 0; s1 < SegmentCount(); s1++ )
 {
 const SEG& a = CSegment( s1 );
 const BOX2I bb_cur( a.A, a.B - a.A );
 
 if( !bb_other.Intersects( bb_cur ) )
 continue;
 
 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
 {
 const SEG& b = aChain.CSegment( s2 );
 INTERSECTION is;
 
 is.index_our = s1;
 is.index_their = s2;
 is.is_corner_our = false;
 is.is_corner_their = false;
 is.valid = true;
 
 OPT_VECTOR2I p = a.Intersect( b );
 
 bool coll = a.Collinear( b );
 
 if( coll && ! aExcludeColinearAndTouching )
 {
 if( a.Contains( b.A ) )
 {
 is.p = b.A;
 is.is_corner_their = true;
 addIntersection(aIp, PointCount(), is);
 }
 
 if( a.Contains( b.B ) )
 {
 is.p = b.B;
 is.index_their++;
 is.is_corner_their = true;
 addIntersection( aIp, PointCount(), is );
 }
 
 if( b.Contains( a.A ) )
 {
 is.p = a.A;
 is.is_corner_our = true;
 addIntersection( aIp, PointCount(), is );
 }
 
 if( b.Contains( a.B ) )
 {
 is.p = a.B;
 is.index_our++;
 is.is_corner_our = true;
 addIntersection( aIp, PointCount(), is );
 }
 }
 else if( p )
 {
 is.p = *p;
 is.is_corner_our = false;
 is.is_corner_their = false;
 
 if( p == a.A )
 {
 is.is_corner_our = true;
 }
 
 if( p == a.B )
 {
 is.is_corner_our = true;
 is.index_our++;
 }
 
 if( p == b.A )
 {
 is.is_corner_their = true;
 }
 
 if( p == b.B )
 {
 is.is_corner_their = true;
 is.index_their++;
 }
 
 addIntersection( aIp, PointCount(), is );
 }
 }
 }
 
 return aIp.size();
}
 
 
int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
{
 int sum = 0;
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 const SEG seg = CSegment( i );
 bool indexMatch = true;
 
 if( aIndex >= 0 )
 {
 if( aIndex == SegmentCount() )
 {
 indexMatch = ( i == SegmentCount() - 1 );
 }
 else
 {
 indexMatch = ( i == aIndex );
 }
 }
 
 if( indexMatch )
 {
 sum += ( aP - seg.A ).EuclideanNorm();
 return sum;
 }
 else
 sum += seg.Length();
 }
 
 return -1;
}
 
 
bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
 bool aUseBBoxCache ) const
{
 /*
 * Don't check the bounding box unless it's cached. Building it is about the same speed as
 * the rigorous test below and so just slows things down by doing potentially two tests.
 */
 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
 return false;
 
 if( !IsClosed() || GetPointCount() < 3 )
 return false;
 
 bool inside = false;
 
 /*
 * To check for interior points, we draw a line in the positive x direction from
 * the point. If it intersects an even number of segments, the point is outside the
 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
 *
 * Note: slope might be denormal here in the case of a horizontal line but we require our
 * y to move from above to below the point (or vice versa)
 *
 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
 * vector number-of-points times. This has a non-trivial impact on zone fill times.
 */
 int pointCount = GetPointCount();
 
 for( int i = 0; i < pointCount; )
 {
 const auto p1 = GetPoint( i++ );
 const auto p2 = GetPoint( i == pointCount ? 0 : i );
 const auto diff = p2 - p1;
 
 if( diff.y != 0 )
 {
 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
 
 if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
 inside = !inside;
 }
 }
 
 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
 if( aAccuracy <= 1 )
 return inside;
 else
 return inside || PointOnEdge( aPt, aAccuracy );
}
 
 
bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
{
 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
}
 
 
int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
{
 if( !GetPointCount() )
 {
 return -1;
 }
 else if( GetPointCount() == 1 )
 {
 VECTOR2I dist = GetPoint(0) - aPt;
 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
 }
 
 for( size_t i = 0; i < GetSegmentCount(); i++ )
 {
 const SEG s = GetSegment( i );
 
 if( s.A == aPt || s.B == aPt )
 return i;
 
 if( s.Distance( aPt ) <= aAccuracy + 1 )
 return i;
 }
 
 return -1;
}
 
 
bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
{
 if( !PointCount() )
 return false;
 else if( PointCount() == 1 )
 return m_points[0] == aP;
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 const SEG s = CSegment( i );
 
 if( s.A == aP || s.B == aP )
 return true;
 
 if( s.Distance( aP ) <= aDist )
 return true;
 }
 
 return false;
}
 
 
const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
{
 for( int s1 = 0; s1 < SegmentCount(); s1++ )
 {
 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
 {
 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
 
 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
 {
 INTERSECTION is;
 is.index_our = s1;
 is.index_their = s2;
 is.p = s2a;
 return is;
 }
 else if( CSegment( s1 ).Contains( s2b ) &&
 // for closed polylines, the ending point of the
 // last segment == starting point of the first segment
 // this is a normal case, not self intersecting case
 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
 {
 INTERSECTION is;
 is.index_our = s1;
 is.index_their = s2;
 is.p = s2b;
 return is;
 }
 else
 {
 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
 
 if( p )
 {
 INTERSECTION is;
 is.index_our = s1;
 is.index_their = s2;
 is.p = *p;
 return is;
 }
 }
 }
 }
 
 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
}
 
 
struct SHAPE_KEY
{
 SHAPE_KEY( int aFirstIdx, int aArcIdx, const BOX2I_MINMAX& aBBox ) :
 m_FirstIdx( aFirstIdx ), m_ArcIdx( aArcIdx ), m_BBox( aBBox )
 {
 }
 
 int m_FirstIdx;
 int m_ArcIdx;
 BOX2I_MINMAX m_BBox;
};
 
 
const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
SHAPE_LINE_CHAIN::SelfIntersectingWithArcs() const
{
 auto pointsClose = []( const VECTOR2I& aPt1, const VECTOR2I& aPt2 ) -> bool
 {
 return ( VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
 };
 
 auto collideArcSeg = [&pointsClose]( const SHAPE_ARC& aArc, const SEG& aSeg, int aClearance = 0,
 VECTOR2I* aLocation = nullptr )
 {
 VECTOR2I center = aArc.GetCenter();
 CIRCLE circle( center, aArc.GetRadius() );
 
 std::vector<VECTOR2I> candidatePts = circle.Intersect( aSeg );
 
 for( const VECTOR2I& candidate : candidatePts )
 {
 // Skip shared points
 if( aArc.GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
 continue;
 
 if( aSeg.B == aArc.GetP0() && pointsClose( candidate, aSeg.B ) )
 continue;
 
 bool collides = aArc.Collide( candidate, aClearance, nullptr, aLocation );
 
 if( collides )
 return true;
 }
 
 return false;
 };
 
 auto collideArcArc = [&pointsClose]( const SHAPE_ARC& aArc1, const SHAPE_ARC& aArc2,
 VECTOR2I* aLocation = nullptr )
 {
 std::vector<VECTOR2I> candidatePts;
 
 aArc1.Intersect( aArc2, &candidatePts );
 
 for( const VECTOR2I& candidate : candidatePts )
 {
 // Skip shared points
 if( aArc1.GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.GetP1() ) )
 continue;
 
 if( aArc2.GetP1() == aArc1.GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
 continue;
 
 if( aLocation )
 *aLocation = candidate;
 
 return true;
 }
 
 return false;
 };
 
 auto collideSegSeg = [this]( int s1, int s2, INTERSECTION& is )
 {
 SEG seg1 = CSegment( s1 );
 SEG seg2 = CSegment( s2 );
 
 const VECTOR2I s2a = seg2.A, s2b = seg2.B;
 
 if( s1 + 1 != s2 && seg1.Contains( s2a ) )
 {
 is.index_our = s1;
 is.index_their = s2;
 is.p = s2a;
 return true;
 }
 else if( seg1.Contains( s2b ) &&
 // for closed polylines, the ending point of the
 // last segment == starting point of the first segment
 // this is a normal case, not self intersecting case
 !( IsClosed() && s1 == 0 && s2 == SegmentCount() - 1 ) )
 {
 is.index_our = s1;
 is.index_their = s2;
 is.p = s2b;
 return true;
 }
 else
 {
 OPT_VECTOR2I p = seg1.Intersect( seg2, true );
 
 if( p )
 {
 is.index_our = s1;
 is.index_their = s2;
 is.p = *p;
 return true;
 }
 }
 
 return false;
 };
 
 INTERSECTION is;
 
 std::vector<SHAPE_KEY> shapeCache;
 for( int si = 0; si != -1; si = NextShape( si ) )
 {
 int arci = ArcIndex( si );
 
 shapeCache.emplace_back( si, arci,
 arci == -1 ? BOX2I_MINMAX( CSegment( si ) )
 : BOX2I_MINMAX( Arc( arci ) ) );
 }
 
 for( size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
 {
 for( size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
 {
 VECTOR2I loc;
 const SHAPE_KEY& k1 = shapeCache[sk1];
 const SHAPE_KEY& k2 = shapeCache[sk2];
 
 if( !k1.m_BBox.Intersects( k2.m_BBox ) )
 continue;
 
 if( k1.m_ArcIdx == -1 && k2.m_ArcIdx == -1 )
 {
 if( collideSegSeg( k1.m_FirstIdx, k2.m_FirstIdx, is ) )
 {
 return is;
 }
 }
 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx == -1 )
 {
 if( collideArcSeg( Arc( k1.m_ArcIdx ), CSegment( k2.m_FirstIdx ), 0, &loc ) )
 {
 is.index_our = k1.m_FirstIdx;
 is.index_their = k2.m_FirstIdx;
 is.p = loc;
 return is;
 }
 }
 else if( k1.m_ArcIdx == -1 && k2.m_ArcIdx != -1 )
 {
 if( collideArcSeg( Arc( k2.m_ArcIdx ), CSegment( k1.m_FirstIdx ), 0, &loc ) )
 {
 is.index_our = k1.m_FirstIdx;
 is.index_their = k2.m_FirstIdx;
 is.p = loc;
 return is;
 }
 }
 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx != -1 )
 {
 if( collideArcArc( Arc( k1.m_ArcIdx ), Arc( k2.m_ArcIdx ), &loc ) )
 {
 is.index_our = k1.m_FirstIdx;
 is.index_their = k2.m_FirstIdx;
 is.p = loc;
 return is;
 }
 }
 }
 }
 
 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
}
 
 
const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const VECTOR2I& aP,
 bool aAllowInternalShapePoints ) const
{
 if( PointCount() == 0 )
 {
 // The only right answer here is "don't crash".
 return { 0, 0 };
 }
 
 int min_d = std::numeric_limits<int>::max();
 int nearest = 0;
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 int d = CSegment( i ).Distance( aP );
 
 if( d < min_d )
 {
 min_d = d;
 nearest = i;
 }
 }
 
 if( !aAllowInternalShapePoints )
 {
 //Snap to arc end points if the closest found segment is part of an arc segment
 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
 {
 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
 
 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
 nearest++;
 
 // Is this the start or end of an arc? If so, return it directly
 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
 {
 return m_points[nearest];
 }
 else
 {
 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
 
 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
 return nearestArc.GetP1();
 else
 return nearestArc.GetP0();
 }
 
 }
 }
 
 return CSegment( nearest ).NearestPoint( aP );
}
 
 
const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
{
 if( PointCount() == 0 )
 {
 // The only right answer here is "don't crash".
 return { 0, 0 };
 }
 
 int nearest = 0;
 
 dist = std::numeric_limits<int>::max();
 
 for( int i = 0; i < PointCount(); i++ )
 {
 int d = aSeg.LineDistance( CPoint( i ) );
 
 if( d < dist )
 {
 dist = d;
 nearest = i;
 }
 }
 
 return CPoint( nearest );
}
 
 
int SHAPE_LINE_CHAIN::NearestSegment( const VECTOR2I& aP ) const
{
 int min_d = std::numeric_limits<int>::max();
 int nearest = 0;
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 int d = CSegment( i ).Distance( aP );
 
 if( d < min_d )
 {
 min_d = d;
 nearest = i;
 }
 }
 
 return nearest;
}
 
 
const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
{
 std::stringstream ss;
 
 ss << "SHAPE_LINE_CHAIN( { ";
 
 for( int i = 0; i < PointCount(); i++ )
 {
 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
 
 if( i != PointCount() -1 )
 ss << ", ";
 }
 
 ss << "}, " << ( m_closed ? "true" : "false" );
 ss << " );";
 
 return ss.str();
 
 /* fixme: arcs
 for( size_t i = 0; i < m_arcs.size(); i++ )
 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
 << m_arcs[i].GetCentralAngle().AsDegrees();
 
 return ss.str();*/
}
 
 
bool SHAPE_LINE_CHAIN::CompareGeometry( const SHAPE_LINE_CHAIN & aOther ) const
{
 SHAPE_LINE_CHAIN a(*this), b( aOther );
 a.Simplify();
 b.Simplify();
 
 if( a.m_points.size() != b.m_points.size() )
 return false;
 
 for( int i = 0; i < a.PointCount(); i++ )
 {
 if( a.CPoint( i ) != b.CPoint( i ) )
 return false;
 }
 
 return true;
}
 
 
bool SHAPE_LINE_CHAIN::Intersects( const SHAPE_LINE_CHAIN& aChain ) const
{
 INTERSECTIONS dummy;
 return Intersect( aChain, dummy ) != 0;
}
 
 
SHAPE* SHAPE_LINE_CHAIN::Clone() const
{
 return new SHAPE_LINE_CHAIN( *this );
}
 
 
bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
{
 size_t n_pts;
 size_t n_arcs;
 
 m_points.clear();
 aStream >> n_pts;
 
 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
 if( n_pts > aStream.str().size() )
 return false;
 
 aStream >> m_closed;
 aStream >> n_arcs;
 
 if( n_arcs > aStream.str().size() )
 return false;
 
 for( size_t i = 0; i < n_pts; i++ )
 {
 int x, y;
 ssize_t ind;
 aStream >> x;
 aStream >> y;
 m_points.emplace_back( x, y );
 
 aStream >> ind;
 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
 }
 
 for( size_t i = 0; i < n_arcs; i++ )
 {
 VECTOR2I p0, pc;
 double angle;
 
 aStream >> pc.x;
 aStream >> pc.y;
 aStream >> p0.x;
 aStream >> p0.y;
 aStream >> angle;
 
 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
 }
 
 return true;
}
 
 
const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
{
 int total = 0;
 
 if( aPathLength == 0 )
 return CPoint( 0 );
 
 for( int i = 0; i < SegmentCount(); i++ )
 {
 const SEG& s = CSegment( i );
 int l = s.Length();
 
 if( total + l >= aPathLength )
 {
 VECTOR2I d( s.B - s.A );
 return s.A + d.Resize( aPathLength - total );
 }
 
 total += l;
 }
 
 return CPoint( -1 );
}
 
 
double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
{
 // see https://www.mathopenref.com/coordpolygonarea2.html
 
 if( !m_closed )
 return 0.0;
 
 double area = 0.0;
 int size = m_points.size();
 
 for( int i = 0, j = size - 1; i < size; ++i )
 {
 area += ( (double) m_points[j].x + m_points[i].x ) *
 ( (double) m_points[j].y - m_points[i].y );
 j = i;
 }
 
 if( aAbsolute )
 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
 else
 return -area * 0.5; // The result would be negative if points are anti-clockwise
}
 
 
void SHAPE_LINE_CHAIN::RemoveDuplicatePoints()
{
 std::vector<VECTOR2I> pts_unique;
 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
 
 // Always try to keep at least 2 points otherwise, we're not really a line
 if( PointCount() < 3 )
 {
 return;
 }
 else if( PointCount() == 3 )
 {
 if( m_points[0] == m_points[1] )
 Remove( 1 );
 
 return;
 }
 
 int i = 0;
 
 while( i < PointCount() )
 {
 int j = i + 1;
 
 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
 // one of them is part of a shape and one is not.
 while( j < PointCount() && m_points[i] == m_points[j] &&
 ( m_shapes[i] == m_shapes[j] ||
 m_shapes[i] == SHAPES_ARE_PT ||
 m_shapes[j] == SHAPES_ARE_PT ) )
 {
 j++;
 }
 
 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
 
 if( shapeToKeep == SHAPES_ARE_PT )
 shapeToKeep = m_shapes[j - 1];
 
 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
 
 pts_unique.push_back( CPoint( i ) );
 shapes_unique.push_back( shapeToKeep );
 
 i = j;
 }
 
 m_points.clear();
 m_shapes.clear();
 
 for( size_t ii = 0; ii < pts_unique.size(); ++ii )
 {
 const VECTOR2I p0 = pts_unique[ii];
 
 m_points.push_back( p0 );
 m_shapes.push_back( shapes_unique[ii] );
 }
}
 
 
 
void SHAPE_LINE_CHAIN::Simplify( int aMaxError )
{
 if( PointCount() < 3 )
 return;
 
 std::vector<VECTOR2I> new_points;
 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
 
 new_points.reserve( m_points.size() );
 new_shapes.reserve( m_shapes.size() );
 
 auto is_skip = [this]( size_t i, size_t j, size_t k )
 {
 return ( ( m_points[i].x == m_points[j].x // First two points on same vertical line
 && m_points[i].y != m_points[j].y // and not on same horizontal line
 && m_points[i].x != m_points[k].x ) // and not on same vertical line as third point
 || ( m_points[i].y == m_points[j].y
 && m_points[i].x != m_points[j].x
 && m_points[i].y != m_points[k].y ) );
 };
 
 for( size_t ii = 0; ii < m_points.size(); )
 {
 new_points.push_back( m_points[ii] );
 new_shapes.push_back( m_shapes[ii] );
 size_t jj = ( ii + 1 ) % m_points.size();
 size_t kk = ( ii + 2 ) % m_points.size();
 
 if( m_shapes[ii].first != SHAPE_IS_PT || m_shapes[jj].first != SHAPE_IS_PT
 || m_shapes[kk].first != SHAPE_IS_PT
 || is_skip( ii, jj, kk ) )
 {
 ++ii;
 continue;
 }
 
 while( ii != kk && jj > ii && !( kk < ii && !m_closed ) )
 {
 bool too_far = false;
 
 for( size_t ll = ( ii + 1 ) % m_points.size(); ll != kk;
 ll = ( ll + 1 ) % m_points.size() )
 {
 if( !TestSegmentHitFast( m_points[ll], m_points[ii], m_points[kk], aMaxError ) )
 {
 too_far = true;
 break;
 }
 }
 
 if( too_far || is_skip( ii, jj, kk ) )
 break;
 
 jj = ( jj + 1 ) % m_points.size();
 kk = ( kk + 1 ) % m_points.size();
 }
 
 if( ii == kk || jj <= ii )
 break;
 
 ii = jj;
 }
 
 // If we have only one point, we need to add a second point to make a line
 if( new_points.size() == 1 )
 {
 new_points.push_back( m_points.back() );
 new_shapes.push_back( m_shapes.back() );
 }
 
 m_points.clear();
 m_shapes.clear();
 m_points = new_points;
 m_shapes = new_shapes;
}
 
 
void SHAPE_LINE_CHAIN::Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
 SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const
{
 VECTOR2I cp( aEnd );
 
 VECTOR2I n = NearestPoint( cp, false );
 VECTOR2I m = NearestPoint( aStart, false );
 
 SHAPE_LINE_CHAIN l( *this );
 l.Split( n, true );
 l.Split( m, true );
 
 int i_start = l.Find( m );
 int i_end = l.Find( n );
 
 if( i_start > i_end )
 {
 l = l.Reverse();
 i_start = l.Find( m );
 i_end = l.Find( n );
 }
 
 aPre = l.Slice( 0, i_start );
 aPost = l.Slice( i_end, -1 );
 aMid = l.Slice( i_start, i_end );
}
 
 
bool SHAPE_LINE_CHAIN::OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
 SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
 bool aSimplify ) const
{
 if( PointCount() < 2 )
 return false;
 
 SHAPE_POLY_SET poly;
 poly.OffsetLineChain( *this, aAmount, aCornerStrategy, aMaxError, aSimplify );
 
 if( poly.OutlineCount() != 1 )
 return false;
 
 if( poly.COutline( 0 ).PointCount() < 3 )
 return false;
 
 if( poly.HasHoles() )
 return false;
 
 SHAPE_LINE_CHAIN outline = poly.COutline( 0 );
 
 wxASSERT( outline.IsClosed() );
 
 const VECTOR2I& start = CPoint( 0 );
 const VECTOR2I& end = CPoint( -1 );
 
 outline.Split( start, true );
 outline.Split( end, true );
 
 const int idA = outline.Find( start );
 const int idB = outline.Find( end );
 
 if( idA == -1 || idB == -1 )
 return false;
 
 aLeft.Clear();
 aRight.Clear();
 
 for( int i = idA;; )
 {
 aLeft.Append( outline.CPoint( i ) );
 
 i = ( i + 1 ) % outline.PointCount();
 
 if( i == idB )
 {
 aLeft.Append( outline.CPoint( i ) );
 break;
 }
 
 if( i == idA )
 return false;
 }
 
 if( aLeft.PointCount() < 2 )
 return false;
 
 for( int i = idB;; )
 {
 aRight.Append( outline.CPoint( i ) );
 
 i = ( i + 1 ) % outline.PointCount();
 
 if( i == idA )
 {
 aRight.Append( outline.CPoint( i ) );
 break;
 }
 
 if( i == idB )
 return false;
 }
 
 if( aRight.PointCount() < 2 )
 return false;
 
 if( aLeft.CPoint( 0 ) != start )
 {
 aLeft = aLeft.Reverse();
 wxASSERT( aLeft.CPoint( 0 ) == start );
 }
 
 if( aRight.CPoint( 0 ) != start )
 {
 aRight = aRight.Reverse();
 wxASSERT( aRight.CPoint( 0 ) == start );
 }
 
 SEG base( CPoint( 0 ), CPoint( 1 ) );
 int sideLeft = base.Side( aLeft.CPoint( 1 ) );
 int sideRight = base.Side( aRight.CPoint( 1 ) );
 
 if( sideLeft == 0 || sideRight == 0 )
 return false;
 
 if( sideLeft == sideRight )
 return false;
 
 if( sideLeft > 0 && sideRight < 0 )
 std::swap( aLeft, aRight );
 
 if( aLeft.PointCount() < 4 )
 return false;
 
 if( aRight.PointCount() < 4 )
 return false;
 
 aLeft.Remove( 0 );
 aLeft.Remove( aLeft.PointCount() - 1 );
 
 aRight.Remove( 0 );
 aRight.Remove( aRight.PointCount() - 1 );
 
 return true;
}
 
 
void SHAPE_LINE_CHAIN::TransformToPolygon( SHAPE_POLY_SET& aBuffer, int aError,
 ERROR_LOC aErrorLoc ) const
{
 aBuffer.AddOutline( *this );
}
 
 
SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::POINT_INSIDE_TRACKER( const VECTOR2I& aPoint ) :
 m_point( aPoint ),
 m_finished( false ),
 m_state( 0 ),
 m_count( 0 )
{
}
 
 
bool SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::processVertex(
 const VECTOR2I& ip, const VECTOR2I& ipNext )
{
 if( ipNext.y == m_point.y )
 {
 if( ( ipNext.x == m_point.x )
 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
 {
 m_finished = true;
 m_state = -1;
 return false;
 }
 }
 
 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
 {
 if( ip.x >= m_point.x )
 {
 if( ipNext.x > m_point.x )
 {
 m_state = 1 - m_state;
 }
 else
 {
 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
 
 if( !d )
 {
 m_finished = true;
 m_state = -1;
 return false;
 }
 
 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
 m_state = 1 - m_state;
 }
 }
 else
 {
 if( ipNext.x > m_point.x )
 {
 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
 
 if( !d )
 {
 m_finished = true;
 m_state = -1;
 return false;
 }
 
 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
 m_state = 1 - m_state;
 }
 }
 }
 
 return true;
}
 
 
void SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline( const SHAPE_LINE_CHAIN& aPolyline )
{
 if( !m_count )
 {
 m_lastPoint = aPolyline.CPoint( 0 );
 m_firstPoint = aPolyline.CPoint( 0 );
 }
 
 m_count += aPolyline.PointCount();
 
 for( int i = 1; i < aPolyline.PointCount(); i++ )
 {
 auto p = aPolyline.CPoint( i );
 
 if( !processVertex( m_lastPoint, p ) )
 return;
 
 m_lastPoint = p;
 }
 
}
 
 
bool SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::IsInside()
{
 processVertex( m_lastPoint, m_firstPoint );
 return m_state > 0;
}
 
 
bool SHAPE_LINE_CHAIN::IsSharedPt( size_t aIndex ) const
{
 return aIndex < m_shapes.size()
 && m_shapes[aIndex].first != SHAPE_IS_PT
 && m_shapes[aIndex].second != SHAPE_IS_PT;
}
 
 
bool SHAPE_LINE_CHAIN::IsPtOnArc( size_t aPtIndex ) const
{
 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
}
 
 
bool SHAPE_LINE_CHAIN::IsArcSegment( size_t aSegment ) const
{
 /*
 * A segment is part of an arc except in the special case of two arcs next to each other
 * but without a shared vertex. Here there is a segment between the end of the first arc
 * and the start of the second arc.
 */
 size_t nextIdx = aSegment + 1;
 
 if( nextIdx > m_shapes.size() - 1 )
 {
 if( nextIdx == m_shapes.size() && m_closed && IsSharedPt( 0 ) )
 nextIdx = 0; // segment between end point and first point
 else
 return false;
 }
 
 return ( IsPtOnArc( aSegment )
 && ( ArcIndex( aSegment ) == m_shapes[nextIdx].first ) );
}
 
 
bool SHAPE_LINE_CHAIN::IsArcStart( size_t aIndex ) const
{
 if( !IsArcSegment( aIndex ) ) // also does bound checking
 return false;
 
 if( IsSharedPt( aIndex ) )
 return true;
 
 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
 
 return arc.GetP0() == m_points[aIndex];
}
 
 
bool SHAPE_LINE_CHAIN::IsArcEnd( size_t aIndex ) const
{
 size_t prevIndex = aIndex - 1;
 
 if( aIndex == 0 )
 prevIndex = m_points.size() - 1;
 else if( aIndex > m_points.size() -1 )
 return false; // invalid index requested
 
 if( !IsArcSegment( prevIndex ) )
 return false;
 
 if( IsSharedPt( aIndex ) )
 return true;
 
 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
 
 return arc.GetP1() == m_points[aIndex];
}