shape_collisions.cpp File Reference

#include <cmath>
#include <limits.h>
#include <geometry/seg.h>
#include <geometry/shape.h>
#include <geometry/shape_arc.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_circle.h>
#include <geometry/shape_rect.h>
#include <geometry/shape_segment.h>
#include <geometry/shape_compound.h>
#include <math/vector2d.h>

Go to the source code of this file.

Typedefs
typedef VECTOR2I::extended_type	ecoord

Functions
static bool	Collide (const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_RECT &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static VECTOR2I	pushoutForce (const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
static bool	Collide (const SHAPE_CIRCLE &aA, const SHAPE_LINE_CHAIN_BASE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_CIRCLE &aA, const SHAPE_SEGMENT &aSeg, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_LINE_CHAIN_BASE &aA, const SHAPE_LINE_CHAIN_BASE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_RECT &aA, const SHAPE_LINE_CHAIN_BASE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_RECT &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_SEGMENT &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_LINE_CHAIN_BASE &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_RECT &aA, const SHAPE_RECT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_RECT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_LINE_CHAIN &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_LINE_CHAIN_BASE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	Collide (const SHAPE_ARC &aA, const SHAPE_ARC &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
template<class T_a , class T_b >
bool	CollCase (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
template<class T_a , class T_b >
bool	CollCaseReversed (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
static bool	collideSingleShapes (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)

Typedef Documentation

ecoord

typedef VECTOR2I::extended_type ecoord

Definition at line 39 of file shape_collisions.cpp.

Function Documentation

CollCase()

template<class T_a , class T_b >

bool CollCase ( const SHAPE *  aA, const SHAPE *  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inline

Definition at line 761 of file shape_collisions.cpp.

{
 return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
 aClearance, aActual, aLocation, aMTV);
}

References Collide().

CollCaseReversed()

template<class T_a , class T_b >

bool CollCaseReversed ( const SHAPE *  aA, const SHAPE *  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inline

Definition at line 771 of file shape_collisions.cpp.

{
 bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
 aClearance, aActual, aLocation, aMTV);
 
 if( rv && aMTV)
 *aMTV = - *aMTV;
 
 return rv;
}

References Collide().

Collide() [1/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_ARC &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 672 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 SEG mediatrix( aA.GetCenter(), aB.GetCenter() );
 
 std::vector<VECTOR2I> ips;
 
 // Basic case - arcs intersect
 if( aA.Intersect( aB, &ips ) > 0 )
 {
 if( aActual )
 *aActual = 0;
 
 if( aLocation )
 *aLocation = ips[0]; // Pick the first intersection point
 
 return true;
 }
 
 // Arcs don't intersect, build a list of points to check
 std::vector<VECTOR2I> ptsA;
 std::vector<VECTOR2I> ptsB;
 
 bool cocentered = ( mediatrix.A == mediatrix.B );
 
 // 1: Interior points of both arcs, which are on the line segment between the two centres
 if( !cocentered )
 {
 aA.IntersectLine( mediatrix, &ptsA );
 aB.IntersectLine( mediatrix, &ptsB );
 }
 
 // 2: Check arc end points
 ptsA.push_back( aA.GetP0() );
 ptsA.push_back( aA.GetP1() );
 ptsB.push_back( aB.GetP0() );
 ptsB.push_back( aB.GetP1() );
 
 // 3: Endpoint of one and "projected" point on the other, which is on the
 // line segment through that endpoint and the centre of the other arc
 aA.IntersectLine( SEG( aB.GetP0(), aA.GetCenter() ), &ptsA );
 aA.IntersectLine( SEG( aB.GetP1(), aA.GetCenter() ), &ptsA );
 
 aB.IntersectLine( SEG( aA.GetP0(), aB.GetCenter() ), &ptsB );
 aB.IntersectLine( SEG( aA.GetP1(), aB.GetCenter() ), &ptsB );
 
 double minDist = std::numeric_limits<double>::max();
 SEG minDistSeg;
 bool rv = false;
 
 int widths = ( aA.GetWidth() / 2 ) + ( aB.GetWidth() / 2 );
 
 // @todo performance could be improved by only checking certain points (e.g only check end
 // points against other end points or their corresponding "projected" points)
 for( const VECTOR2I& ptA : ptsA )
 {
 for( const VECTOR2I& ptB : ptsB )
 {
 SEG candidateMinDist( ptA, ptB );
 int dist = candidateMinDist.Length() - widths;
 
 if( dist < aClearance )
 {
 if( !rv || dist < minDist )
 {
 minDist = dist;
 minDistSeg = candidateMinDist;
 }
 
 rv = true;
 }
 }
 }
 
 if( rv && aActual )
 *aActual = std::max( 0, minDistSeg.Length() - widths );
 
 if( rv && aLocation )
 *aLocation = minDistSeg.Center();
 
 return rv;
}

References SEG::A, SEG::B, SEG::Center(), Format(), SHAPE_ARC::GetCenter(), SHAPE_ARC::GetP0(), SHAPE_ARC::GetP1(), SHAPE_ARC::GetWidth(), SHAPE_ARC::Intersect(), SHAPE_ARC::IntersectLine(), SEG::Length(), and SHAPE_BASE::TypeName().

Collide() [2/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_CIRCLE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 511 of file shape_collisions.cpp.

{
 const SHAPE_LINE_CHAIN lc( aA );
 
 bool rv = Collide( aB, lc, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
 
 if( rv && aActual )
 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
 
 return rv;
}

References Collide(), and SHAPE_ARC::GetWidth().

Collide() [3/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_LINE_CHAIN &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 525 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 int closest_dist = INT_MAX;
 VECTOR2I nearest;
 
 if( aB.IsClosed() && aB.PointInside( aA.GetP0() ) )
 {
 closest_dist = 0;
 nearest = aA.GetP0();
 }
 else
 {
 for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
 {
 int collision_dist = 0;
 VECTOR2I pn;
 
 // ignore arcs - we will collide these separately
 if( aB.IsArcSegment( i ) )
 continue;
 
 if( aA.Collide( aB.GetSegment( i ), aClearance,
 aActual || aLocation ? &collision_dist : nullptr,
 aLocation ? &pn : nullptr ) )
 {
 if( collision_dist < closest_dist )
 {
 nearest = pn;
 closest_dist = collision_dist;
 }
 
 if( closest_dist == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( !aActual )
 break;
 }
 }
 
 for( size_t i = 0; i < aB.ArcCount(); i++ )
 {
 const SHAPE_ARC& arc = aB.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( &aA, aClearance, aActual, aLocation ) )
 return true;
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 return true;
 }
 
 return false;
}

References SHAPE_LINE_CHAIN::Arc(), SHAPE_LINE_CHAIN::ArcCount(), SHAPE_ARC::Collide(), Format(), SHAPE_ARC::GetP0(), SHAPE_LINE_CHAIN::GetSegment(), SHAPE_LINE_CHAIN::GetSegmentCount(), SHAPE_ARC::GetWidth(), SHAPE_LINE_CHAIN::IsArcSegment(), SHAPE_LINE_CHAIN::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SHAPE_BASE::TypeName().

Collide() [4/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_LINE_CHAIN_BASE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 615 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 int closest_dist = INT_MAX;
 VECTOR2I nearest;
 
 if( aB.IsClosed() && aB.PointInside( aA.GetP0() ) )
 {
 closest_dist = 0;
 nearest = aA.GetP0();
 }
 else
 {
 for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
 {
 int collision_dist = 0;
 VECTOR2I pn;
 
 if( aA.Collide( aB.GetSegment( i ), aClearance,
 aActual || aLocation ? &collision_dist : nullptr,
 aLocation ? &pn : nullptr ) )
 {
 if( collision_dist < closest_dist )
 {
 nearest = pn;
 closest_dist = collision_dist;
 }
 
 if( closest_dist == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( !aActual )
 break;
 }
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 return true;
 }
 
 return false;
}

References SHAPE_ARC::Collide(), Format(), SHAPE_ARC::GetP0(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SHAPE_BASE::TypeName().

Collide() [5/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_RECT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 493 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 const SHAPE_LINE_CHAIN lc( aA );
 
 bool rv = Collide( lc, aB.Outline(), aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
 
 if( rv && aActual )
 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
 
 return rv;
}

References Collide(), Format(), SHAPE_ARC::GetWidth(), SHAPE_RECT::Outline(), and SHAPE_BASE::TypeName().

Collide() [6/16]

static bool Collide ( const SHAPE_ARC &  aA, const SHAPE_SEGMENT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 597 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 const SHAPE_LINE_CHAIN lc( aA );
 
 bool rv = Collide( lc, aB, aClearance + aA.GetWidth() / 2, aActual, aLocation, aMTV );
 
 if( rv && aActual )
 *aActual = std::max( 0, *aActual - aA.GetWidth() / 2 );
 
 return rv;
}

References Collide(), Format(), SHAPE_ARC::GetWidth(), and SHAPE_BASE::TypeName().

Collide() [7/16]

static bool Collide ( const SHAPE_CIRCLE &  aA, const SHAPE_CIRCLE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 42 of file shape_collisions.cpp.

{
 ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
 ecoord min_dist_sq = min_dist * min_dist;
 
 const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
 ecoord dist_sq = delta.SquaredEuclideanNorm();
 
 if( dist_sq == 0 || dist_sq < min_dist_sq )
 {
 if( aActual )
 *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() - aB.GetRadius() );
 
 if( aLocation )
 *aLocation = ( aA.GetCenter() + aB.GetCenter() ) / 2;
 
 if( aMTV )
 *aMTV = delta.Resize( min_dist - sqrt( dist_sq ) + 3 ); // fixme: apparent rounding error
 
 return true;
 }
 
 return false;
}

References delta, SHAPE_CIRCLE::GetCenter(), and SHAPE_CIRCLE::GetRadius().

Referenced by BOOST_AUTO_TEST_CASE(), CollCase(), CollCaseReversed(), Collide(), and DRC_TEST_PROVIDER_COPPER_CLEARANCE::testTrackAgainstItem().

Collide() [8/16]

static bool Collide ( const SHAPE_CIRCLE &  aA, const SHAPE_LINE_CHAIN_BASE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 174 of file shape_collisions.cpp.

{
 int closest_dist = INT_MAX;
 int closest_mtv_dist = INT_MAX;
 VECTOR2I nearest;
 int closest_mtv_seg = -1;
 
 if( aB.IsClosed() && aB.PointInside( aA.GetCenter() ) )
 {
 nearest = aA.GetCenter();
 closest_dist = 0;
 
 if( aMTV )
 {
 for( int s = 0; s < aB.GetSegmentCount(); s++ )
 {
 int dist = aB.GetSegment(s).Distance( aA.GetCenter() );
 
 if( dist < closest_mtv_dist )
 {
 closest_mtv_dist = dist;
 closest_mtv_seg = s;
 }
 }
 }
 
 }
 else
 {
 for( size_t s = 0; s < aB.GetSegmentCount(); s++ )
 {
 int collision_dist = 0;
 VECTOR2I pn;
 
 if( aA.Collide( aB.GetSegment( s ), aClearance,
 aActual || aLocation ? &collision_dist : nullptr,
 aLocation ? &pn : nullptr ) )
 {
 if( collision_dist < closest_dist )
 {
 nearest = pn;
 closest_dist = collision_dist;
 }
 
 if( closest_dist == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( !aActual )
 break;
 }
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 if( aMTV )
 {
 SHAPE_CIRCLE cmoved( aA );
 VECTOR2I f_total( 0, 0 );
 
 VECTOR2I f;
 
 if (closest_mtv_seg >= 0)
 {
 SEG cs = aB.GetSegment( closest_mtv_seg );
 VECTOR2I np = cs.NearestPoint( aA.GetCenter() );
 f = ( np - aA.GetCenter() ) + ( np - aA.GetCenter() ).Resize( aA.GetRadius() );
 }
 
 cmoved.SetCenter( cmoved.GetCenter() + f );
 f_total += f;
 
 for( int s = 0; s < aB.GetSegmentCount(); s++ )
 {
 VECTOR2I f = pushoutForce( cmoved, aB.GetSegment( s ), aClearance );
 cmoved.SetCenter( cmoved.GetCenter() + f );
 f_total += f;
 }
 
 *aMTV = f_total;
 }
 
 return true;
 }
 
 return false;
}

References SHAPE_CIRCLE::Collide(), SEG::Distance(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SEG::NearestPoint(), SHAPE_LINE_CHAIN_BASE::PointInside(), pushoutForce(), and SHAPE_CIRCLE::SetCenter().

Collide() [9/16]

static bool Collide ( const SHAPE_CIRCLE &  aA, const SHAPE_SEGMENT &  aSeg, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 271 of file shape_collisions.cpp.

{
 if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual, aLocation ) )
 {
 if( aMTV )
 *aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
 
 if( aActual )
 *aActual = std::max( 0, *aActual - aSeg.GetWidth() / 2 );
 
 return true;
 }
 
 return false;
}

References SHAPE_CIRCLE::Collide(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), and pushoutForce().

Collide() [10/16]

static bool Collide ( const SHAPE_LINE_CHAIN_BASE &  aA, const SHAPE_LINE_CHAIN_BASE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 289 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 int closest_dist = INT_MAX;
 VECTOR2I nearest;
 
 if( aB.IsClosed() && aA.GetPointCount() > 0 && aB.PointInside( aA.GetPoint( 0 ) ) )
 {
 closest_dist = 0;
 nearest = aA.GetPoint( 0 );
 }
 else
 {
 for( size_t i = 0; i < aB.GetSegmentCount(); i++ )
 {
 int collision_dist = 0;
 VECTOR2I pn;
 
 if( aB.Type() == SH_LINE_CHAIN )
 {
 const SHAPE_LINE_CHAIN* aB_line_chain = static_cast<const SHAPE_LINE_CHAIN*>( &aB );
 
 // ignore arcs - we will collide these separately
 if( aB_line_chain->IsArcSegment( i ) )
 continue;
 }
 
 if( aA.Collide( aB.GetSegment( i ), aClearance,
 aActual || aLocation ? &collision_dist : nullptr,
 aLocation ? &pn : nullptr ) )
 {
 if( collision_dist < closest_dist )
 {
 nearest = pn;
 closest_dist = collision_dist;
 }
 
 if( closest_dist == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( !aActual )
 break;
 }
 }
 
 if( aB.Type() == SH_LINE_CHAIN )
 {
 const SHAPE_LINE_CHAIN* aB_line_chain = static_cast<const SHAPE_LINE_CHAIN*>( &aB );
 
 for( size_t i = 0; i < aB_line_chain->ArcCount(); i++ )
 {
 const SHAPE_ARC& arc = aB_line_chain->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( &aA, aClearance, aActual, aLocation ) )
 return true;
 }
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 return true;
 }
 
 return false;
}

References SHAPE_LINE_CHAIN::Arc(), SHAPE_LINE_CHAIN::ArcCount(), SHAPE_ARC::Collide(), SHAPE_LINE_CHAIN_BASE::Collide(), Format(), SHAPE_LINE_CHAIN_BASE::GetPoint(), SHAPE_LINE_CHAIN_BASE::GetPointCount(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_ARC::GetWidth(), SHAPE_LINE_CHAIN::IsArcSegment(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointInside(), SH_LINE_CHAIN, SHAPE_BASE::Type(), and SHAPE_BASE::TypeName().

Collide() [11/16]

static bool Collide ( const SHAPE_LINE_CHAIN_BASE &  aA, const SHAPE_SEGMENT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 460 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
 
 if( aActual )
 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
 
 return rv;
}

References SHAPE_LINE_CHAIN_BASE::Collide(), Format(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), and SHAPE_BASE::TypeName().

Collide() [12/16]

static bool Collide ( const SHAPE_RECT &  aA, const SHAPE_CIRCLE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 69 of file shape_collisions.cpp.

{
 const VECTOR2I c = aB.GetCenter();
 const VECTOR2I p0 = aA.GetPosition();
 const VECTOR2I size = aA.GetSize();
 const int r = aB.GetRadius();
 const int min_dist = aClearance + r;
 const ecoord min_dist_sq = SEG::Square( min_dist );
 
 const VECTOR2I vts[] =
 {
 VECTOR2I( p0.x, p0.y ),
 VECTOR2I( p0.x, p0.y + size.y ),
  VECTOR2I( p0.x + size.x, p0.y + size.y ),
 VECTOR2I( p0.x + size.x, p0.y ),
 VECTOR2I( p0.x, p0.y )
 };
 
 ecoord nearest_side_dist_sq = VECTOR2I::ECOORD_MAX;
 VECTOR2I nearest;
 
 bool inside = c.x >= p0.x && c.x <= ( p0.x + size.x )
 && c.y >= p0.y && c.y <= ( p0.y + size.y );
 
 // If we're not looking for MTV or actual, short-circuit once we find a hard collision
 if( inside && !aActual && !aLocation && !aMTV )
 return true;
 
 for( int i = 0; i < 4; i++ )
 {
 const SEG side( vts[i], vts[ i + 1] );
 
 VECTOR2I pn = side.NearestPoint( c );
 ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
 
 if( side_dist_sq < nearest_side_dist_sq )
 {
 nearest = pn;
 nearest_side_dist_sq = side_dist_sq;
 
 if( aMTV )
 continue;
 
 if( nearest_side_dist_sq == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( nearest_side_dist_sq < min_dist_sq && !aActual )
 break;
 }
 }
 
 if( inside || nearest_side_dist_sq == 0 || nearest_side_dist_sq < min_dist_sq )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = std::max( 0, (int) sqrt( nearest_side_dist_sq ) - r );
 
 if( aMTV )
 {
 VECTOR2I delta = c - nearest;
 
 if( inside )
 *aMTV = -delta.Resize( abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
 else
 *aMTV = delta.Resize( abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
 }
 
 return true;
 }
 
 return false;
}

References std::abs(), delta, VECTOR2< int >::ECOORD_MAX, SHAPE_CIRCLE::GetCenter(), SHAPE_RECT::GetPosition(), SHAPE_CIRCLE::GetRadius(), SHAPE_RECT::GetSize(), SEG::NearestPoint(), r, SEG::Square(), VECTOR2< T >::x, and VECTOR2< T >::y.

Collide() [13/16]

static bool Collide ( const SHAPE_RECT &  aA, const SHAPE_LINE_CHAIN_BASE &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 371 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
  aB.TypeName() ) );
 
 int closest_dist = INT_MAX;
 VECTOR2I nearest;
 
 if( aB.IsClosed() && aB.PointInside( aA.Centre() ) )
 {
 nearest = aA.Centre();
 closest_dist = 0;
 }
 else
 {
 for( size_t s = 0; s < aB.GetSegmentCount(); s++ )
 {
 int collision_dist = 0;
 VECTOR2I pn;
 
 if( aA.Collide( aB.GetSegment( s ), aClearance,
 aActual || aLocation ? &collision_dist : nullptr,
 aLocation ? &pn : nullptr ) )
 {
 if( collision_dist < closest_dist )
 {
 nearest = pn;
 closest_dist = collision_dist;
 }
 
 if( closest_dist == 0 )
 break;
 
 // If we're not looking for aActual then any collision will do
 if( !aActual )
 break;
 }
 }
 }
 
 if( closest_dist == 0 || closest_dist < aClearance )
 {
 if( aLocation )
 *aLocation = nearest;
 
 if( aActual )
 *aActual = closest_dist;
 
 return true;
 }
 
 return false;
}

References SHAPE::Centre(), SHAPE_RECT::Collide(), Format(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SHAPE_BASE::TypeName().

Collide() [14/16]

static bool Collide ( const SHAPE_RECT &  aA, const SHAPE_RECT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 476 of file shape_collisions.cpp.

{
 if( aClearance || aActual || aLocation || aMTV )
 {
 return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aLocation, aMTV );
 }
 else
 {
 BOX2I bboxa = aA.BBox();
 BOX2I bboxb = aB.BBox();
 
 return bboxa.Intersects( bboxb );
 }
}

References SHAPE_RECT::BBox(), Collide(), BOX2< Vec >::Intersects(), and SHAPE_RECT::Outline().

Collide() [15/16]

static bool Collide ( const SHAPE_RECT &  aA, const SHAPE_SEGMENT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 428 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
 
 if( aActual )
 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
 
 return rv;
}

References SHAPE_RECT::Collide(), Format(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), and SHAPE_BASE::TypeName().

Collide() [16/16]

static bool Collide ( const SHAPE_SEGMENT &  aA, const SHAPE_SEGMENT &  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

inlinestatic

Definition at line 444 of file shape_collisions.cpp.

{
 wxASSERT_MSG( !aMTV, wxString::Format( wxT( "MTV not implemented for %s : %s collisions" ),
 aA.TypeName(),
 aB.TypeName() ) );
 
 bool rv = aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation );
 
 if( aActual )
 *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
 
 return rv;
}

References SHAPE_SEGMENT::Collide(), Format(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), and SHAPE_BASE::TypeName().

collideShapes()

static bool collideShapes ( const SHAPE *  aA, const SHAPE *  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

static

Definition at line 984 of file shape_collisions.cpp.

{
 int currentActual = std::numeric_limits<int>::max();
 VECTOR2I currentLocation;
 VECTOR2I currentMTV(0, 0);
 bool colliding = false;
 
 auto canExit =
 [&]()
 {
 if( !colliding )
 return false;
 
 if( aActual && currentActual > 0 )
 return false;
 
 if( aMTV )
 return false;
 
 return true;
 };
 
 auto collideCompoundSubshapes =
 [&]( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
 {
 int actual = 0;
 VECTOR2I location;
 VECTOR2I mtv;
 
 if( collideSingleShapes( elemA, elemB, clearance,
 aActual || aLocation ? &actual : nullptr,
 aLocation ? &location : nullptr,
 aMTV ? &mtv : nullptr ) )
 {
 if( actual < currentActual )
 {
 currentActual = actual;
 currentLocation = location;
 }
 
 if( aMTV && mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
 {
 currentMTV = mtv;
 }
 
 return true;
 }
 
 return false;
 };
 
 if( aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
 {
 const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
 const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
 
 for( const SHAPE* elemA : cmpA->Shapes() )
 {
 for( const SHAPE* elemB : cmpB->Shapes() )
 {
 if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
 {
 colliding = true;
 
 if( canExit() )
 break;
 }
 }
 
 if( canExit() )
 break;
 }
 }
 else if( aA->Type() == SH_COMPOUND )
 {
 const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
 
 for( const SHAPE* elemA : cmpA->Shapes() )
 {
 if( collideCompoundSubshapes( elemA, aB, aClearance ) )
 {
 colliding = true;
 
 if( canExit() )
 break;
 }
 }
 }
 else if( aB->Type() == SH_COMPOUND )
 {
 const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
 
 for( const SHAPE* elemB : cmpB->Shapes() )
 {
 if( collideCompoundSubshapes( aA, elemB, aClearance ) )
 {
 colliding = true;
 
 if( canExit() )
 break;
 }
 }
 }
 else
 {
 return collideSingleShapes( aA, aB, aClearance, aActual, aLocation, aMTV );
 }
 
 if( colliding )
 {
 if( aLocation )
 *aLocation = currentLocation;
 
 if( aActual )
 *aActual = currentActual;
 
 if( aMTV )
 *aMTV = currentMTV;
 }
 
 return colliding;
}

References collideSingleShapes(), SH_COMPOUND, SHAPE_COMPOUND::Shapes(), VECTOR2< T >::SquaredEuclideanNorm(), and SHAPE_BASE::Type().

Referenced by SHAPE::Collide().

collideSingleShapes()

static bool collideSingleShapes ( const SHAPE *  aA, const SHAPE *  aB, int  aClearance, int *  aActual, VECTOR2I *  aLocation, VECTOR2I *  aMTV  )

static

Definition at line 784 of file shape_collisions.cpp.

{
 switch( aA->Type() )
 {
 case SH_NULL:
 return false;
 
 case SH_RECT:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 case SH_CIRCLE:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 case SH_LINE_CHAIN:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 case SH_SEGMENT:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 case SH_ARC:
 switch( aB->Type() )
 {
 case SH_RECT:
 return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_CIRCLE:
 return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_LINE_CHAIN:
 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SEGMENT:
 return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_SIMPLE:
 case SH_POLY_SET_TRIANGLE:
 return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_ARC:
 return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
 
 case SH_NULL:
 return false;
 
 default:
 break;
 }
 break;
 
 default:
 break;
 }
 
 wxFAIL_MSG( wxString::Format( wxT( "Unsupported collision: %s with %s" ),
 SHAPE_TYPE_asString( aA->Type() ),
 SHAPE_TYPE_asString( aB->Type() ) ) );
 
 return false;
}

References Format(), SH_ARC, SH_CIRCLE, SH_LINE_CHAIN, SH_NULL, SH_POLY_SET_TRIANGLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, SHAPE_TYPE_asString(), and SHAPE_BASE::Type().

Referenced by collideShapes().

pushoutForce()

static VECTOR2I pushoutForce ( const SHAPE_CIRCLE &  aA, const SEG &  aB, int  aClearance  )

static

Definition at line 147 of file shape_collisions.cpp.

{
 VECTOR2I f( 0, 0 );
 
 const VECTOR2I c = aA.GetCenter();
 const VECTOR2I nearest = aB.NearestPoint( c );
 
 const int r = aA.GetRadius();
 
 int dist = ( nearest - c ).EuclideanNorm();
 int min_dist = aClearance + r;
 
 if( dist < min_dist )
 {
 for( int corr = 0; corr < 5; corr++ )
 {
 f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
 
 if( aB.Distance( c + f ) >= min_dist )
 break;
 }
 }
 
 return f;
}

References SEG::Distance(), EuclideanNorm(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), SEG::NearestPoint(), and r.

Referenced by Collide().