KiCad PCB EDA Suite
shape_collisions.cpp File Reference
#include <assert.h>
#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_simple.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 *aMTV)
 
static bool Collide (const SHAPE_RECT &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, 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 &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_CIRCLE &aA, const SHAPE_SIMPLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_CIRCLE &aA, const SHAPE_SEGMENT &aSeg, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_LINE_CHAIN &aA, const SHAPE_LINE_CHAIN &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_LINE_CHAIN &aA, const SHAPE_SIMPLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_SIMPLE &aA, const SHAPE_SIMPLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_RECT &aA, const SHAPE_LINE_CHAIN &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_RECT &aA, const SHAPE_SIMPLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_RECT &aA, const SHAPE_SEGMENT &aSeg, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_SEGMENT &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_LINE_CHAIN &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_SIMPLE &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_RECT &aA, const SHAPE_RECT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_RECT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_LINE_CHAIN &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_SEGMENT &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_SIMPLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool Collide (const SHAPE_ARC &aA, const SHAPE_ARC &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
template<class T_a , class T_b >
bool CollCase (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
template<class T_a , class T_b >
bool CollCaseReversed (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool collideSingleShapes (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 
static bool collideShapes (const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
 

Typedef Documentation

◆ ecoord

Definition at line 41 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 aMTV 
)
inline

Definition at line 427 of file shape_collisions.cpp.

430 {
431  return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
432  aClearance, aActual, aMTV);
433 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)

References Collide().

◆ CollCaseReversed()

template<class T_a , class T_b >
bool CollCaseReversed ( const SHAPE aA,
const SHAPE aB,
int  aClearance,
int *  aActual,
VECTOR2I aMTV 
)
inline

Definition at line 436 of file shape_collisions.cpp.

438 {
439  bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
440  aClearance, aActual, aMTV);
441 
442  if( rv && aMTV)
443  *aMTV = - *aMTV;
444 
445  return rv;
446 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)

References Collide().

◆ Collide() [1/21]

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

Definition at line 43 of file shape_collisions.cpp.

45 {
46  ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
47  ecoord min_dist_sq = min_dist * min_dist;
48 
49  const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
50 
51  ecoord dist_sq = delta.SquaredEuclideanNorm();
52 
53  if( dist_sq >= min_dist_sq )
54  return false;
55 
56  if( aActual )
57  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() - aB.GetRadius() );
58 
59  if( aMTV )
60  *aMTV = delta.Resize( min_dist - sqrt( dist_sq ) + 3 ); // fixme: apparent rounding error
61 
62  return true;
63 }
int GetRadius() const
Definition: shape_circle.h:94
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
VECTOR2I::extended_type ecoord
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392

References SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), VECTOR2< T >::Resize(), and VECTOR2< T >::SquaredEuclideanNorm().

Referenced by BOOST_AUTO_TEST_CASE(), CollCase(), CollCaseReversed(), and Collide().

◆ Collide() [2/21]

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

Definition at line 66 of file shape_collisions.cpp.

68 {
69  const VECTOR2I c = aB.GetCenter();
70  const VECTOR2I p0 = aA.GetPosition();
71  const VECTOR2I size = aA.GetSize();
72  const int r = aB.GetRadius();
73  const int min_dist = aClearance + r;
74  const ecoord min_dist_sq = (ecoord) min_dist * min_dist;
75 
76  const VECTOR2I vts[] =
77  {
78  VECTOR2I( p0.x, p0.y ),
79  VECTOR2I( p0.x, p0.y + size.y ),
80  VECTOR2I( p0.x + size.x, p0.y + size.y ),
81  VECTOR2I( p0.x + size.x, p0.y ),
82  VECTOR2I( p0.x, p0.y )
83  };
84 
85  ecoord nearest_side_dist_sq = VECTOR2I::ECOORD_MAX;
86  VECTOR2I nearest;
87 
88  bool inside = c.x >= p0.x && c.x <= ( p0.x + size.x )
89  && c.y >= p0.y && c.y <= ( p0.y + size.y );
90 
91  // If we're not looking for MTV, short-circuit once we find a hard collision
92  if( !aMTV && inside )
93  {
94  if( aActual )
95  *aActual = 0;
96 
97  return true;
98  }
99 
100  for( int i = 0; i < 4; i++ )
101  {
102  const SEG side( vts[i], vts[ i + 1] );
103 
104  VECTOR2I pn = side.NearestPoint( c );
105  ecoord side_dist_sq = ( pn - c ).SquaredEuclideanNorm();
106 
107  // If we're not looking for MTV or actual, short-circuit once we find any collision
108  if( !aMTV && !aActual && ( side_dist_sq == 0 || side_dist_sq < min_dist_sq ) )
109  return true;
110 
111  if( side_dist_sq < nearest_side_dist_sq )
112  {
113  nearest = pn;
114  nearest_side_dist_sq = side_dist_sq;
115  }
116  }
117 
118  if( !inside && nearest_side_dist_sq >= min_dist_sq )
119  return false;
120 
121  VECTOR2I delta = c - nearest;
122 
123  if( aActual )
124  *aActual = std::max( 0, (int) sqrt( nearest_side_dist_sq ) - r );
125 
126  if( aMTV )
127  {
128  if( inside )
129  *aMTV = -delta.Resize( abs( min_dist + 1 + sqrt( nearest_side_dist_sq ) ) + 1 );
130  else
131  *aMTV = delta.Resize( abs( min_dist + 1 - sqrt( nearest_side_dist_sq ) ) + 1 );
132  }
133 
134 
135  return true;
136 }
int GetRadius() const
Definition: shape_circle.h:94
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
const VECTOR2I GetSize() const
Function GetSize()
Definition: shape_rect.h:121
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
const VECTOR2I & GetPosition() const
Function GetPosition()
Definition: shape_rect.h:111
VECTOR2I::extended_type ecoord
Definition: seg.h:39
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392

References VECTOR2< T >::ECOORD_MAX, SHAPE_CIRCLE::GetCenter(), SHAPE_RECT::GetPosition(), SHAPE_CIRCLE::GetRadius(), SHAPE_RECT::GetSize(), SEG::NearestPoint(), VECTOR2< T >::Resize(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ Collide() [3/21]

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

Definition at line 166 of file shape_collisions.cpp.

168 {
169  bool collided = false;
170 
171  for( int s = 0; s < aB.SegmentCount(); s++ )
172  {
173  if( aA.Collide( aB.CSegment( s ), aClearance, aActual ) )
174  {
175  collided = true;
176  break;
177  }
178  }
179 
180  if( !collided )
181  return false;
182 
183  if( aMTV )
184  {
185  SHAPE_CIRCLE cmoved( aA );
186  VECTOR2I f_total( 0, 0 );
187 
188  for( int s = 0; s < aB.SegmentCount(); s++ )
189  {
190  VECTOR2I f = pushoutForce( cmoved, aB.CSegment( s ), aClearance );
191  cmoved.SetCenter( cmoved.GetCenter() + f );
192  f_total += f;
193  }
194 
195  *aMTV = f_total;
196  }
197 
198  return true;
199 }
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
Definition: shape_circle.h:68
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

References SHAPE_CIRCLE::Collide(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_CIRCLE::GetCenter(), pushoutForce(), SHAPE_LINE_CHAIN::SegmentCount(), and SHAPE_CIRCLE::SetCenter().

◆ Collide() [4/21]

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

Definition at line 202 of file shape_collisions.cpp.

204 {
205  int min_dist = aClearance + aA.GetRadius();
206  ecoord dist_sq = aB.Vertices().SquaredDistance( aA.GetCenter() );
207 
208  if( dist_sq > (ecoord) min_dist * min_dist )
209  return false;
210 
211  if( aActual )
212  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() );
213 
214  if( aMTV )
215  {
216  SHAPE_CIRCLE cmoved( aA );
217  VECTOR2I f_total( 0, 0 );
218 
219  for( int s = 0; s < aB.Vertices().SegmentCount(); s++ )
220  {
221  VECTOR2I f = pushoutForce( cmoved, aB.Vertices().CSegment( s ), aClearance );
222  cmoved.SetCenter( cmoved.GetCenter() + f );
223  f_total += f;
224  }
225 
226  *aMTV = f_total;
227  }
228  return true;
229 }
int GetRadius() const
Definition: shape_circle.h:94
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
VECTOR2I::extended_type ecoord
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

References SHAPE_LINE_CHAIN::CSegment(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), pushoutForce(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_CIRCLE::SetCenter(), SHAPE_LINE_CHAIN::SquaredDistance(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [5/21]

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

Definition at line 232 of file shape_collisions.cpp.

234 {
235  if( !aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual ) )
236  return false;
237 
238  if( aMTV )
239  *aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
240 
241  return true;
242 }
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
Definition: shape_circle.h:68
const SEG & GetSeg() const
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
int GetWidth() const

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

◆ Collide() [6/21]

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

Definition at line 245 of file shape_collisions.cpp.

247 {
248  // TODO: why doesn't this handle MTV?
249 
250  for( int i = 0; i < aB.SegmentCount(); i++ )
251  {
252  if( aA.Collide( aB.CSegment( i ), aClearance, aActual ) )
253  return true;
254  }
255 
256  return false;
257 }
int SegmentCount() const
Function SegmentCount()
bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
const SEG CSegment(int aIndex) const
Function CSegment()

References SHAPE_LINE_CHAIN::Collide(), SHAPE_LINE_CHAIN::CSegment(), and SHAPE_LINE_CHAIN::SegmentCount().

◆ Collide() [7/21]

static bool Collide ( const SHAPE_LINE_CHAIN aA,
const SHAPE_SIMPLE aB,
int  aClearance,
int *  aActual,
VECTOR2I aMTV 
)
inlinestatic

Definition at line 260 of file shape_collisions.cpp.

262 {
263  return Collide( aA, aB.Vertices(), aClearance, aActual, aMTV );
264 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132

References Collide(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [8/21]

static bool Collide ( const SHAPE_SIMPLE aA,
const SHAPE_SIMPLE aB,
int  aClearance,
int *  aActual,
VECTOR2I aMTV 
)
inlinestatic

Definition at line 267 of file shape_collisions.cpp.

269 {
270  return Collide( aA.Vertices(), aB.Vertices(), aClearance, aActual, aMTV );
271 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132

References Collide(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [9/21]

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

Definition at line 274 of file shape_collisions.cpp.

276 {
277  int minActual = INT_MAX;
278  int actual;
279 
280  for( int s = 0; s < aB.SegmentCount(); s++ )
281  {
282  if( aA.Collide( aB.CSegment( s ), aClearance, &actual ) )
283  {
284  minActual = std::min( minActual, actual );
285 
286  // If we're not looking for MTV or Actual, short-circuit after any collision
287  if( !aActual && !aMTV )
288  return true;
289  }
290  }
291 
292  if( aActual )
293  *aActual = std::max( 0, minActual );
294 
295  // TODO: why doesn't this handle MTV?
296 
297  return minActual < INT_MAX;
298 }
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_rect.h:93
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()

References SHAPE_RECT::Collide(), SHAPE_LINE_CHAIN::CSegment(), and SHAPE_LINE_CHAIN::SegmentCount().

◆ Collide() [10/21]

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

Definition at line 301 of file shape_collisions.cpp.

303 {
304  return Collide( aA, aB.Vertices(), aClearance, aActual, aMTV );
305 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132

References Collide(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [11/21]

static bool Collide ( const SHAPE_RECT aA,
const SHAPE_SEGMENT aSeg,
int  aClearance,
int *  aActual,
VECTOR2I aMTV 
)
inlinestatic

Definition at line 308 of file shape_collisions.cpp.

310 {
311  int actual;
312 
313  if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, &actual ) )
314  {
315  if( aActual )
316  *aActual = std::max( 0, actual - aSeg.GetWidth() / 2 );
317 
318  // TODO: why doesn't this handle MTV?
319 
320  return true;
321  }
322 
323  return false;
324 }
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_rect.h:93
const SEG & GetSeg() const
int GetWidth() const

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

◆ Collide() [12/21]

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

Definition at line 327 of file shape_collisions.cpp.

329 {
330  int actual;
331 
332  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, &actual ) )
333  {
334  if( aActual )
335  *aActual = std::max( 0, actual - aB.GetWidth() / 2 );
336 
337  // TODO: why doesn't this handle MTV?
338 
339  return true;
340  }
341 
342  return false;
343 }
const SEG & GetSeg() const
int GetWidth() const
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_segment.h:59

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

◆ Collide() [13/21]

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

Definition at line 346 of file shape_collisions.cpp.

348 {
349  int actual;
350 
351  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, &actual ) )
352  {
353  if( aActual )
354  *aActual = std::max( 0, actual - aB.GetWidth() / 2 );
355 
356  // TODO: why doesn't this handle MTV?
357 
358  return true;
359  }
360 
361  return false;
362 }
const SEG & GetSeg() const
bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
int GetWidth() const

References SHAPE_LINE_CHAIN::Collide(), SHAPE_SEGMENT::GetSeg(), and SHAPE_SEGMENT::GetWidth().

◆ Collide() [14/21]

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

Definition at line 365 of file shape_collisions.cpp.

367 {
368  return Collide( aA.Vertices(), aB, aClearance, aActual, aMTV );
369 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132

References Collide(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [15/21]

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

Definition at line 371 of file shape_collisions.cpp.

373 {
374  return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aMTV );
375 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:174

References Collide(), and SHAPE_RECT::Outline().

◆ Collide() [16/21]

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

Definition at line 377 of file shape_collisions.cpp.

379 {
380  const auto lc = aA.ConvertToPolyline();
381  return Collide( lc, aB.Outline(), aClearance, aActual, aMTV );
382 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:174
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

References Collide(), SHAPE_ARC::ConvertToPolyline(), and SHAPE_RECT::Outline().

◆ Collide() [17/21]

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

Definition at line 384 of file shape_collisions.cpp.

386 {
387  const auto lc = aA.ConvertToPolyline();
388  bool rv = Collide( aB, lc, aClearance, aActual, aMTV );
389 
390  if( rv && aMTV )
391  *aMTV = - *aMTV ;
392 
393  return rv;
394 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

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

◆ Collide() [18/21]

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

Definition at line 396 of file shape_collisions.cpp.

398 {
399  const auto lc = aA.ConvertToPolyline();
400  return Collide( lc, aB, aClearance, aActual, aMTV );
401 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

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

◆ Collide() [19/21]

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

Definition at line 403 of file shape_collisions.cpp.

405 {
406  const auto lc = aA.ConvertToPolyline();
407  return Collide( lc, aB, aClearance, aActual, aMTV );
408 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

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

◆ Collide() [20/21]

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

Definition at line 410 of file shape_collisions.cpp.

412 {
413  const auto lc = aA.ConvertToPolyline();
414 
415  return Collide( lc, aB.Vertices(), aClearance, aActual, aMTV );
416 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:132
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

References Collide(), SHAPE_ARC::ConvertToPolyline(), and SHAPE_SIMPLE::Vertices().

◆ Collide() [21/21]

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

Definition at line 418 of file shape_collisions.cpp.

420 {
421  const auto lcA = aA.ConvertToPolyline();
422  const auto lcB = aB.ConvertToPolyline();
423  return Collide( lcA, lcB, aClearance, aActual, aMTV );
424 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aMTV)
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231

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

◆ collideShapes()

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

Definition at line 623 of file shape_collisions.cpp.

624 {
625  int currentActual = std::numeric_limits<int>::max();
626  VECTOR2I currentMTV(0, 0);
627  bool colliding = false;
628 
629  bool exitOnFirstCollision = aActual == nullptr && aMTV == nullptr;
630 
631  auto collideCompoundSubshapes = [&] ( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
632  {
633  int actual;
634  VECTOR2I mtv;
635 
636  bool c = collideSingleShapes( elemA, elemB,
637  clearance,
638  aActual ? &actual : nullptr,
639  aMTV ? &mtv : nullptr );
640  if(c)
641  {
642  if (aActual)
643  {
644  currentActual = std::min( actual, currentActual );
645  }
646  if( aMTV )
647  {
648  if( mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
649  currentMTV = mtv;
650  }
651  }
652 
653  return c;
654  };
655 
656  if (aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
657  {
658  auto cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
659  auto cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
660 
661  for( auto elemA : cmpA->Shapes() )
662  {
663  for( auto elemB : cmpB->Shapes() )
664  {
665  if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
666  {
667  colliding = true;
668  if ( exitOnFirstCollision )
669  break;
670  }
671  }
672  if( colliding && exitOnFirstCollision )
673  break;
674  }
675  }
676  else if ( aA->Type() == SH_COMPOUND )
677  {
678  auto cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
679  for( auto elemA : cmpA->Shapes() )
680  {
681  if( collideCompoundSubshapes( elemA, aB, aClearance ) )
682  {
683  colliding = true;
684  if ( exitOnFirstCollision )
685  break;
686  }
687  }
688  }
689  else if ( aB->Type() == SH_COMPOUND )
690  {
691  auto cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
692  for( auto elemB : cmpB->Shapes() )
693  {
694  if( collideCompoundSubshapes( aA, elemB, aClearance ) )
695  {
696  colliding = true;
697  if ( exitOnFirstCollision )
698  break;
699  }
700  }
701  }
702  else
703  {
704  return collideSingleShapes( aA, aB, aClearance, aActual, aMTV );
705  }
706 
707  if( colliding )
708  {
709  if( aActual )
710  *aActual = currentActual;
711  if( aMTV )
712  *aMTV = currentMTV;
713  }
714 
715  return colliding;
716 }
set of polygons (with holes, etc.)
Definition: shape.h:47
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:99
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)
SHAPE.
Definition: shape.h:74

References collideSingleShapes(), SH_COMPOUND, VECTOR2< T >::SquaredEuclideanNorm(), and SHAPE::Type().

Referenced by SHAPE::Collide().

◆ collideSingleShapes()

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

Definition at line 449 of file shape_collisions.cpp.

450 {
451 
452 
453  switch( aA->Type() )
454  {
455  case SH_RECT:
456  switch( aB->Type() )
457  {
458  case SH_RECT:
459  return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
460 
461  case SH_CIRCLE:
462  return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
463 
464  case SH_LINE_CHAIN:
465  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
466 
467  case SH_SEGMENT:
468  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
469 
470  case SH_SIMPLE:
471  return CollCase<SHAPE_RECT, SHAPE_SIMPLE>( aA, aB, aClearance, aActual, aMTV );
472 
473  case SH_ARC:
474  return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
475 
476  default:
477  break;
478  }
479  break;
480 
481  case SH_CIRCLE:
482  switch( aB->Type() )
483  {
484  case SH_RECT:
485  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
486 
487  case SH_CIRCLE:
488  return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
489 
490  case SH_LINE_CHAIN:
491  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
492 
493  case SH_SEGMENT:
494  return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
495 
496  case SH_SIMPLE:
497  return CollCase<SHAPE_CIRCLE, SHAPE_SIMPLE>( aA, aB, aClearance, aActual, aMTV );
498 
499  case SH_ARC:
500  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
501 
502  default:
503  break;
504  }
505  break;
506 
507  case SH_LINE_CHAIN:
508  switch( aB->Type() )
509  {
510  case SH_RECT:
511  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aMTV );
512 
513  case SH_CIRCLE:
514  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aMTV );
515 
516  case SH_LINE_CHAIN:
517  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
518 
519  case SH_SEGMENT:
520  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
521 
522  case SH_SIMPLE:
523  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SIMPLE>( aA, aB, aClearance, aActual, aMTV );
524 
525  case SH_ARC:
526  return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
527 
528  default:
529  break;
530  }
531  break;
532 
533  case SH_SEGMENT:
534  switch( aB->Type() )
535  {
536  case SH_RECT:
537  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
538 
539  case SH_CIRCLE:
540  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
541 
542  case SH_LINE_CHAIN:
543  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
544 
545  case SH_SEGMENT:
546  return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
547 
548  case SH_SIMPLE:
549  return CollCase<SHAPE_SIMPLE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aMTV );
550 
551  case SH_ARC:
552  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
553 
554  default:
555  break;
556  }
557  break;
558 
559  case SH_SIMPLE:
560  switch( aB->Type() )
561  {
562  case SH_RECT:
563  return CollCase<SHAPE_RECT, SHAPE_SIMPLE>( aB, aA, aClearance, aActual, aMTV );
564 
565  case SH_CIRCLE:
566  return CollCase<SHAPE_CIRCLE, SHAPE_SIMPLE>( aB, aA, aClearance, aActual, aMTV );
567 
568  case SH_LINE_CHAIN:
569  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SIMPLE>( aB, aA, aClearance, aActual, aMTV );
570 
571  case SH_SEGMENT:
572  return CollCase<SHAPE_SIMPLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
573 
574  case SH_SIMPLE:
575  return CollCase<SHAPE_SIMPLE, SHAPE_SIMPLE>( aA, aB, aClearance, aActual, aMTV );
576 
577  case SH_ARC:
578  return CollCaseReversed<SHAPE_SIMPLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
579 
580  default:
581  break;
582  }
583  break;
584 
585  case SH_ARC:
586  switch( aB->Type() )
587  {
588  case SH_RECT:
589  return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aMTV );
590 
591  case SH_CIRCLE:
592  return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aMTV );
593 
594  case SH_LINE_CHAIN:
595  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aMTV );
596 
597  case SH_SEGMENT:
598  return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aMTV );
599 
600  case SH_SIMPLE:
601  return CollCase<SHAPE_ARC, SHAPE_SIMPLE>( aA, aB, aClearance, aActual, aMTV );
602 
603  case SH_ARC:
604  return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aMTV );
605 
606  default:
607  break;
608  }
609  break;
610 
611  default:
612  break;
613  }
614 
615  bool unsupported_collision = true;
616  (void) unsupported_collision; // make gcc quiet
617 
618  assert( unsupported_collision == false );
619 
620  return false;
621 }
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:99
compound shape, consisting of multiple simple shapes
Definition: shape.h:48
line chain (polyline)
Definition: shape.h:44
line segment
Definition: shape.h:43
Definition: shape.h:41
circle
Definition: shape.h:45
axis-aligned rectangle
Definition: shape.h:42

References SH_ARC, SH_CIRCLE, SH_LINE_CHAIN, SH_RECT, SH_SEGMENT, SH_SIMPLE, and SHAPE::Type().

Referenced by collideShapes().

◆ pushoutForce()

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

Definition at line 139 of file shape_collisions.cpp.

140 {
141  VECTOR2I f( 0, 0 );
142 
143  const VECTOR2I c = aA.GetCenter();
144  const VECTOR2I nearest = aB.NearestPoint( c );
145 
146  const int r = aA.GetRadius();
147 
148  int dist = ( nearest - c ).EuclideanNorm();
149  int min_dist = aClearance + r;
150 
151  if( dist < min_dist )
152  {
153  for( int corr = 0; corr < 5; corr++ )
154  {
155  f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
156 
157  if( aB.Distance( c + f ) >= min_dist )
158  break;
159  }
160  }
161 
162  return f;
163 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
int GetRadius() const
Definition: shape_circle.h:94
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:99
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395

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

Referenced by Collide().