46 ecoord min_dist_sq = min_dist * min_dist;
51 if( dist_sq == 0 || dist_sq < min_dist_sq )
60 *aMTV =
delta.Resize( min_dist - sqrt( dist_sq ) + 3 );
76 const int min_dist = aClearance + r;
91 bool inside = c.
x >= p0.
x && c.
x <= ( p0.
x + size.
x )
92 && c.
y >= p0.
y && c.
y <= ( p0.
y + size.
y );
95 if( inside && !aActual && !aLocation && !aMTV )
98 for(
int i = 0; i < 4; i++ )
100 const SEG side( vts[i], vts[ i + 1] );
103 ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
105 if( side_dist_sq < nearest_side_dist_sq )
108 nearest_side_dist_sq = side_dist_sq;
113 if( nearest_side_dist_sq == 0 )
117 if( nearest_side_dist_sq < min_dist_sq && !aActual )
122 if( inside || nearest_side_dist_sq == 0 || nearest_side_dist_sq < min_dist_sq )
125 *aLocation = nearest;
128 *aActual = std::max( 0, (
int) sqrt( nearest_side_dist_sq ) - r );
135 *aMTV = -
delta.Resize(
abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
137 *aMTV =
delta.Resize(
abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
157 int min_dist = aClearance + r;
159 if( dist < min_dist )
161 for(
int corr = 0; corr < 5; corr++ )
163 f = ( aA.
GetCenter() - nearest ).Resize( min_dist - dist + corr );
165 if( aB.
Distance( c + f ) >= min_dist )
177 int closest_dist = INT_MAX;
178 int closest_mtv_dist = INT_MAX;
180 int closest_mtv_seg = -1;
193 if( dist < closest_mtv_dist )
195 closest_mtv_dist = dist;
206 int collision_dist = 0;
210 aActual || aLocation ? &collision_dist :
nullptr,
211 aLocation ? &pn :
nullptr ) )
213 if( collision_dist < closest_dist )
216 closest_dist = collision_dist;
219 if( closest_dist == 0 )
229 if( closest_dist == 0 || closest_dist < aClearance )
232 *aLocation = nearest;
235 *aActual = closest_dist;
244 if (closest_mtv_seg >= 0)
280 *aActual = std::max( 0, *aActual - aSeg.
GetWidth() / 2 );
292 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
296 int closest_dist = INT_MAX;
308 int collision_dist = 0;
321 aActual || aLocation ? &collision_dist :
nullptr,
322 aLocation ? &pn :
nullptr ) )
324 if( collision_dist < closest_dist )
327 closest_dist = collision_dist;
330 if( closest_dist == 0 )
343 for(
size_t i = 0; i < aB_line_chain->
ArcCount(); i++ )
348 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
350 if( arc.
Collide( &aA, aClearance, aActual, aLocation ) )
356 if( closest_dist == 0 || closest_dist < aClearance )
359 *aLocation = nearest;
362 *aActual = closest_dist;
374 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
378 int closest_dist = INT_MAX;
390 int collision_dist = 0;
394 aActual || aLocation ? &collision_dist :
nullptr,
395 aLocation ? &pn :
nullptr ) )
397 if( collision_dist < closest_dist )
400 closest_dist = collision_dist;
403 if( closest_dist == 0 )
413 if( closest_dist == 0 || closest_dist < aClearance )
416 *aLocation = nearest;
419 *aActual = closest_dist;
431 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
438 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
447 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
454 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
463 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
470 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
479 if( aClearance || aActual || aLocation || aMTV )
496 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
505 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
516 bool rv =
Collide( aB, lc, aClearance + aA.
GetWidth() / 2, aActual, aLocation, aMTV );
519 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
528 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
532 int closest_dist = INT_MAX;
538 nearest = aA.
GetP0();
544 int collision_dist = 0;
552 aActual || aLocation ? &collision_dist :
nullptr,
553 aLocation ? &pn :
nullptr ) )
555 if( collision_dist < closest_dist )
558 closest_dist = collision_dist;
561 if( closest_dist == 0 )
570 for(
size_t i = 0; i < aB.
ArcCount(); i++ )
575 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
577 if( arc.
Collide( &aA, aClearance, aActual, aLocation ) )
582 if( closest_dist == 0 || closest_dist < aClearance )
585 *aLocation = nearest;
588 *aActual = closest_dist;
600 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
606 bool rv =
Collide( lc, aB, aClearance + aA.
GetWidth() / 2, aActual, aLocation, aMTV );
609 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
618 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
622 int closest_dist = INT_MAX;
628 nearest = aA.
GetP0();
634 int collision_dist = 0;
638 aActual || aLocation ? &collision_dist :
nullptr,
639 aLocation ? &pn :
nullptr ) )
641 if( collision_dist < closest_dist )
644 closest_dist = collision_dist;
647 if( closest_dist == 0 )
657 if( closest_dist == 0 || closest_dist < aClearance )
660 *aLocation = nearest;
663 *aActual = closest_dist;
675 wxASSERT_MSG( !aMTV,
wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
681 std::vector<VECTOR2I> ips;
696 std::vector<VECTOR2I> ptsA;
697 std::vector<VECTOR2I> ptsB;
699 bool cocentered = ( mediatrix.
A == mediatrix.
B );
709 ptsA.push_back( aA.
GetP0() );
710 ptsA.push_back( aA.
GetP1() );
711 ptsB.push_back( aB.
GetP0() );
712 ptsB.push_back( aB.
GetP1() );
722 double minDist = std::numeric_limits<double>::max();
734 SEG candidateMinDist( ptA, ptB );
735 int dist = candidateMinDist.
Length() - widths;
737 if( dist < aClearance )
739 if( !rv || dist < minDist )
742 minDistSeg = candidateMinDist;
751 *aActual = std::max( 0, minDistSeg.
Length() - widths );
753 if( rv && aLocation )
754 *aLocation = minDistSeg.
Center();
760template<
class T_a,
class T_b>
765 return Collide( *
static_cast<const T_a*
>( aA ), *
static_cast<const T_b*
>( aB ),
766 aClearance, aActual, aLocation, aMTV);
770template<
class T_a,
class T_b>
774 bool rv =
Collide( *
static_cast<const T_b*
>( aB ), *
static_cast<const T_a*
>( aA ),
775 aClearance, aActual, aLocation, aMTV);
796 return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
799 return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
802 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
805 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
809 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
812 return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
826 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
829 return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
832 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
835 return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
839 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
842 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
856 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
859 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
862 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
865 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
869 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
872 return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
886 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
889 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
892 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
895 return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
899 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
902 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
917 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
920 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
923 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
926 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
930 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
933 return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
947 return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
950 return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
953 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
956 return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
960 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
963 return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
987 int currentActual = std::numeric_limits<int>::max();
990 bool colliding =
false;
998 if( aActual && currentActual > 0 )
1007 auto collideCompoundSubshapes =
1008 [&](
const SHAPE* elemA,
const SHAPE* elemB,
int clearance ) ->
bool
1015 aActual || aLocation ? &actual :
nullptr,
1016 aLocation ? &location :
nullptr,
1017 aMTV ? &mtv :
nullptr ) )
1019 if( actual < currentActual )
1021 currentActual = actual;
1022 currentLocation = location;
1045 if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
1064 if( collideCompoundSubshapes( elemA, aB, aClearance ) )
1079 if( collideCompoundSubshapes( aA, elemB, aClearance ) )
1096 *aLocation = currentLocation;
1099 *aActual = currentActual;
1111 return collideShapes(
this, aShape, aClearance,
nullptr,
nullptr, aMTV );
1117 return collideShapes(
this, aShape, aClearance, aActual, aLocation,
nullptr );
bool Intersects(const BOX2< Vec > &aRect) const
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
int Length() const
Return the length (this).
static SEG::ecoord Square(int a)
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
const VECTOR2I & GetP1() const
int IntersectLine(const SEG &aSeg, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aSeg, treating aSeg as an infinite line.
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
int Intersect(const SHAPE_ARC &aArc, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aArc.
VECTOR2I GetCenter() const
const VECTOR2I & GetP0() const
wxString TypeName() const
SHAPE_TYPE Type() const
Return the type of the shape.
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
const VECTOR2I GetCenter() const
void SetCenter(const VECTOR2I &aCenter)
const std::vector< SHAPE * > & Shapes() const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual bool IsClosed() const =0
virtual const SEG GetSegment(int aIndex) const =0
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
bool IsClosed() const override
virtual const SEG GetSegment(int aIndex) const override
virtual size_t GetSegmentCount() const override
bool IsArcSegment(size_t aSegment) const
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
const SHAPE_LINE_CHAIN Outline() const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
const VECTOR2I & GetPosition() const
const VECTOR2I GetSize() const
const SEG & GetSeg() const
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
An abstract shape on 2D plane.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
static constexpr extended_type ECOORD_MAX
VECTOR2_TRAITS< int >::extended_type extended_type
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
@ SH_RECT
axis-aligned rectangle
@ SH_SIMPLE
simple polygon
@ SH_NULL
empty shape (no shape...),
@ SH_POLY_SET_TRIANGLE
a single triangle belonging to a POLY_SET triangulation
@ SH_LINE_CHAIN
line chain (polyline)
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
bool CollCaseReversed(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
bool CollCase(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
VECTOR2I::extended_type ecoord
double EuclideanNorm(const VECTOR2I &vector)