47 ecoord min_dist_sq = min_dist * min_dist;
52 if( dist_sq == 0 || dist_sq < min_dist_sq )
61 *aMTV =
delta.Resize( min_dist - sqrt( dist_sq ) + 3 );
77 const int min_dist = aClearance + r;
92 bool inside = c.
x >= p0.
x && c.
x <= ( p0.
x + size.
x )
93 && c.
y >= p0.
y && c.
y <= ( p0.
y + size.
y );
96 if( inside && !aActual && !aLocation && !aMTV )
99 for(
int i = 0; i < 4; i++ )
101 const SEG side( vts[i], vts[ i + 1] );
104 ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
106 if( side_dist_sq < nearest_side_dist_sq )
109 nearest_side_dist_sq = side_dist_sq;
114 if( nearest_side_dist_sq == 0 )
118 if( nearest_side_dist_sq < min_dist_sq && !aActual )
123 if( inside || nearest_side_dist_sq == 0 || nearest_side_dist_sq < min_dist_sq )
126 *aLocation = nearest;
129 *aActual = std::max( 0, (
int) sqrt( nearest_side_dist_sq ) - r );
136 *aMTV = -
delta.Resize( abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
138 *aMTV =
delta.Resize( abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
158 int min_dist = aClearance + r;
160 if( dist < min_dist )
162 for(
int corr = 0; corr < 5; corr++ )
164 f = ( aA.
GetCenter() - nearest ).Resize( min_dist - dist + corr );
166 if( aB.
Distance( c + f ) >= min_dist )
178 int closest_dist = std::numeric_limits<int>::max();
179 int closest_mtv_dist = std::numeric_limits<int>::max();
181 int closest_mtv_seg = -1;
194 if( dist < closest_mtv_dist )
196 closest_mtv_dist = dist;
207 int collision_dist = 0;
211 aActual || aLocation ? &collision_dist :
nullptr,
212 aLocation ? &pn :
nullptr ) )
214 if( collision_dist < closest_dist )
217 closest_dist = collision_dist;
220 if( closest_dist == 0 )
230 if( closest_dist == 0 || closest_dist < aClearance )
233 *aLocation = nearest;
236 *aActual = closest_dist;
245 if (closest_mtv_seg >= 0)
281 *aActual = std::max( 0, *aActual - aSeg.
GetWidth() / 2 );
293 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
297 int closest_dist = std::numeric_limits<int>::max();
309 int collision_dist = 0;
322 aActual || aLocation ? &collision_dist :
nullptr,
323 aLocation ? &pn :
nullptr ) )
325 if( collision_dist < closest_dist )
328 closest_dist = collision_dist;
331 if( closest_dist == 0 )
344 for(
size_t i = 0; i < aB_line_chain->
ArcCount(); i++ )
349 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
351 if( arc.
Collide( &aA, aClearance, aActual, aLocation ) )
357 if( closest_dist == 0 || closest_dist < aClearance )
360 *aLocation = nearest;
363 *aActual = closest_dist;
375 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
379 int closest_dist = std::numeric_limits<int>::max();
391 int collision_dist = 0;
395 aActual || aLocation ? &collision_dist :
nullptr,
396 aLocation ? &pn :
nullptr ) )
398 if( collision_dist < closest_dist )
401 closest_dist = collision_dist;
404 if( closest_dist == 0 )
414 if( closest_dist == 0 || closest_dist < aClearance )
417 *aLocation = nearest;
420 *aActual = closest_dist;
432 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
439 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
448 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
455 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
464 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
471 *aActual = std::max( 0, *aActual - aB.
GetWidth() / 2 );
480 if( aClearance || aActual || aLocation || aMTV )
497 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
506 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
517 bool rv =
Collide( aB, lc, aClearance + aA.
GetWidth() / 2, aActual, aLocation, aMTV );
520 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
529 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
533 int closest_dist = std::numeric_limits<int>::max();
539 nearest = aA.
GetP0();
545 int collision_dist = 0;
553 aActual || aLocation ? &collision_dist :
nullptr,
554 aLocation ? &pn :
nullptr ) )
556 if( collision_dist < closest_dist )
559 closest_dist = collision_dist;
562 if( closest_dist == 0 )
571 for(
size_t i = 0; i < aB.
ArcCount(); i++ )
576 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
578 if( arc.
Collide( &aA, aClearance, aActual, aLocation ) )
583 if( closest_dist == 0 || closest_dist < aClearance )
586 *aLocation = nearest;
589 *aActual = closest_dist;
601 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
607 bool rv =
Collide( lc, aB, aClearance + aA.
GetWidth() / 2, aActual, aLocation, aMTV );
610 *aActual = std::max( 0, *aActual - aA.
GetWidth() / 2 );
619 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
623 int closest_dist = std::numeric_limits<int>::max();
629 nearest = aA.
GetP0();
635 int collision_dist = 0;
639 aActual || aLocation ? &collision_dist :
nullptr,
640 aLocation ? &pn :
nullptr ) )
642 if( collision_dist < closest_dist )
645 closest_dist = collision_dist;
648 if( closest_dist == 0 )
658 if( closest_dist == 0 || closest_dist < aClearance )
661 *aLocation = nearest;
664 *aActual = closest_dist;
676 wxASSERT_MSG( !aMTV, wxString::Format( wxT(
"MTV not implemented for %s : %s collisions" ),
682 std::vector<VECTOR2I> ips;
697 std::vector<VECTOR2I> ptsA;
698 std::vector<VECTOR2I> ptsB;
700 bool cocentered = ( mediatrix.
A == mediatrix.
B );
710 ptsA.push_back( aA.
GetP0() );
711 ptsA.push_back( aA.
GetP1() );
712 ptsB.push_back( aB.
GetP0() );
713 ptsB.push_back( aB.
GetP1() );
723 double minDist = std::numeric_limits<double>::max();
735 SEG candidateMinDist( ptA, ptB );
736 int dist = candidateMinDist.
Length() - widths;
738 if( dist < aClearance )
740 if( !rv || dist < minDist )
743 minDistSeg = candidateMinDist;
752 *aActual = std::max( 0, minDistSeg.
Length() - widths );
754 if( rv && aLocation )
755 *aLocation = minDistSeg.
Center();
761template<
class T_a,
class T_b>
766 return Collide( *
static_cast<const T_a*
>( aA ), *
static_cast<const T_b*
>( aB ),
767 aClearance, aActual, aLocation, aMTV);
771template<
class T_a,
class T_b>
775 bool rv =
Collide( *
static_cast<const T_b*
>( aB ), *
static_cast<const T_a*
>( aA ),
776 aClearance, aActual, aLocation, aMTV);
793 return polySetA->
Collide( aB, aClearance, aActual, aLocation );
800 return polySetB->
Collide( aA, aClearance, aActual, aLocation );
812 return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
815 return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
818 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
821 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
825 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
828 return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
842 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
845 return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
848 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
851 return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
855 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
858 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
872 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
875 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
878 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
881 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
885 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
888 return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
902 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
905 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
908 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
911 return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
915 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
918 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
933 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
936 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
939 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
942 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
946 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
949 return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
963 return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
966 return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
969 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
972 return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
976 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
979 return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
993 wxFAIL_MSG( wxString::Format( wxT(
"Unsupported collision: %s with %s" ),
1003 int currentActual = std::numeric_limits<int>::max();
1006 bool colliding =
false;
1014 if( aActual && currentActual > 0 )
1023 auto collideCompoundSubshapes =
1024 [&](
const SHAPE* elemA,
const SHAPE* elemB,
int clearance ) ->
bool
1031 aActual || aLocation ? &actual :
nullptr,
1032 aLocation ? &location :
nullptr,
1033 aMTV ? &mtv :
nullptr ) )
1035 if( actual < currentActual )
1037 currentActual = actual;
1038 currentLocation = location;
1061 if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
1080 if( collideCompoundSubshapes( elemA, aB, aClearance ) )
1095 if( collideCompoundSubshapes( aA, elemB, aClearance ) )
1112 *aLocation = currentLocation;
1115 *aActual = currentActual;
1127 return collideShapes(
this, aShape, aClearance,
nullptr,
nullptr, aMTV );
1133 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
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
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
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
Represent a set of closed polygons.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
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
@ SH_POLY_SET
set of polygons (with holes, etc.)
@ 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)