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_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 &aSeg, 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

Definition at line 40 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 477 of file shape_collisions.cpp.

480 {
481  return Collide( *static_cast<const T_a*>( aA ), *static_cast<const T_b*>( aB ),
482  aClearance, aActual, aLocation, aMTV);
483 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, 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 aLocation,
VECTOR2I aMTV 
)
inline

Definition at line 486 of file shape_collisions.cpp.

488 {
489  bool rv = Collide( *static_cast<const T_b*>( aB ), *static_cast<const T_a*>( aA ),
490  aClearance, aActual, aLocation, aMTV);
491 
492  if( rv && aMTV)
493  *aMTV = - *aMTV;
494 
495  return rv;
496 }
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

References Collide().

◆ Collide() [1/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.

44 {
45  ecoord min_dist = aClearance + aA.GetRadius() + aB.GetRadius();
46  ecoord min_dist_sq = min_dist * min_dist;
47 
48  const VECTOR2I delta = aB.GetCenter() - aA.GetCenter();
49  ecoord dist_sq = delta.SquaredEuclideanNorm();
50 
51  if( dist_sq == 0 || dist_sq < min_dist_sq )
52  {
53  if( aActual )
54  *aActual = std::max( 0, (int) sqrt( dist_sq ) - aA.GetRadius() - aB.GetRadius() );
55 
56  if( aLocation )
57  *aLocation = ( aA.GetCenter() + aB.GetCenter() ) / 2;
58 
59  if( aMTV )
60  *aMTV = delta.Resize( min_dist - sqrt( dist_sq ) + 3 ); // fixme: apparent rounding error
61 
62  return true;
63  }
64 
65  return false;
66 }
int GetRadius() const
Definition: shape_circle.h:99
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:104
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/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.

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

◆ Collide() [3/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.

176 {
177  int closest_dist = INT_MAX;
178  VECTOR2I nearest;
179 
180  if( aB.IsClosed() && aB.PointInside( aA.GetCenter() ) )
181  {
182  closest_dist = 0;
183  nearest = aA.GetCenter();
184  }
185  else
186  {
187  for( int s = 0; s < aB.GetSegmentCount(); s++ )
188  {
189  int collision_dist = 0;
190  VECTOR2I pn;
191 
192  if( aA.Collide( aB.GetSegment( s ), aClearance,
193  aActual || aLocation ? &collision_dist : nullptr,
194  aLocation ? &pn : nullptr ) )
195  {
196  if( collision_dist < closest_dist )
197  {
198  nearest = pn;
199  closest_dist = collision_dist;
200  }
201 
202  if( closest_dist == 0 )
203  break;
204 
205  // If we're not looking for aActual then any collision will do
206  if( !aActual )
207  break;
208  }
209  }
210  }
211 
212  if( closest_dist == 0 || closest_dist < aClearance )
213  {
214  if( aLocation )
215  *aLocation = nearest;
216 
217  if( aActual )
218  *aActual = closest_dist;
219 
220  if( aMTV )
221  {
222  SHAPE_CIRCLE cmoved( aA );
223  VECTOR2I f_total( 0, 0 );
224 
225  for( int s = 0; s < aB.GetSegmentCount(); s++ )
226  {
227  VECTOR2I f = pushoutForce( cmoved, aB.GetSegment( s ), aClearance );
228  cmoved.SetCenter( cmoved.GetCenter() + f );
229  f_total += f;
230  }
231 
232  *aMTV = f_total;
233  }
234 
235  return true;
236  }
237 
238  return false;
239 }
virtual bool IsClosed() const =0
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:104
virtual size_t GetSegmentCount() const =0
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
Definition: shape_circle.h:68
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
static VECTOR2I pushoutForce(const SHAPE_CIRCLE &aA, const SEG &aB, int aClearance)
virtual const SEG GetSegment(int aIndex) const =0

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

◆ Collide() [4/16]

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

Definition at line 242 of file shape_collisions.cpp.

244 {
245  if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual, aLocation ) )
246  {
247  if( aMTV )
248  *aMTV = -pushoutForce( aA, aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2);
249 
250  if( aActual )
251  *aActual = std::max( 0, *aActual - aSeg.GetWidth() / 2 );
252 
253  return true;
254  }
255 
256  return false;
257 }
const SEG & GetSeg() const
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
Definition: shape_circle.h:68
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() [5/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 260 of file shape_collisions.cpp.

262 {
263  // TODO: why doesn't this handle MTV?
264 
265  int closest_dist = INT_MAX;
266  VECTOR2I nearest;
267 
268  if( aB.IsClosed() && aA.GetPointCount() > 0 && aB.PointInside( aA.GetPoint( 0 ) ) )
269  {
270  closest_dist = 0;
271  nearest = aA.GetPoint( 0 );
272  }
273  else
274  {
275  for( int i = 0; i < aB.GetSegmentCount(); i++ )
276  {
277  int collision_dist = 0;
278  VECTOR2I pn;
279 
280  if( aA.Collide( aB.GetSegment( i ), aClearance,
281  aActual || aLocation ? &collision_dist : nullptr,
282  aLocation ? &pn : nullptr ) )
283  {
284  if( collision_dist < closest_dist )
285  {
286  nearest = pn;
287  closest_dist = collision_dist;
288  }
289 
290  if( closest_dist == 0 )
291  break;
292 
293  // If we're not looking for aActual then any collision will do
294  if( !aActual )
295  break;
296  }
297  }
298  }
299 
300  if( closest_dist == 0 || closest_dist < aClearance )
301  {
302  if( aLocation )
303  *aLocation = nearest;
304 
305  if( aActual )
306  *aActual = closest_dist;
307 
308  return true;
309  }
310 
311  return false;
312 }
virtual bool IsClosed() const =0
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
virtual const SEG GetSegment(int aIndex) const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0

References SHAPE_LINE_CHAIN_BASE::Collide(), SHAPE_LINE_CHAIN_BASE::GetPoint(), SHAPE_LINE_CHAIN_BASE::GetPointCount(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), and SHAPE_LINE_CHAIN_BASE::PointInside().

◆ Collide() [6/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 315 of file shape_collisions.cpp.

317 {
318  // TODO: why doesn't this handle MTV?
319 
320  int closest_dist = INT_MAX;
321  VECTOR2I nearest;
322 
323  if( aB.IsClosed() && aB.PointInside( aA.Centre() ) )
324  {
325  nearest = aA.Centre();
326  closest_dist = 0;
327  }
328  else
329  {
330  for( int s = 0; s < aB.GetSegmentCount(); s++ )
331  {
332  int collision_dist = 0;
333  VECTOR2I pn;
334 
335  if( aA.Collide( aB.GetSegment( s ), aClearance,
336  aActual || aLocation ? &collision_dist : nullptr,
337  aLocation ? &pn : nullptr ) )
338  {
339  if( collision_dist < closest_dist )
340  {
341  nearest = pn;
342  closest_dist = collision_dist;
343  }
344 
345  if( closest_dist == 0 )
346  break;
347 
348  // If we're not looking for aActual then any collision will do
349  if( !aActual )
350  break;
351  }
352  }
353  }
354 
355  if( closest_dist == 0 || closest_dist < aClearance )
356  {
357  if( aLocation )
358  *aLocation = nearest;
359 
360  if( aActual )
361  *aActual = closest_dist;
362 
363  return true;
364  }
365 
366  return false;
367 }
bool Collide(const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const override
Function Collide()
Definition: shape_rect.h:93
virtual bool IsClosed() const =0
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
virtual VECTOR2I Centre() const
Function Centre()
Definition: shape.h:232
virtual size_t GetSegmentCount() const =0
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
virtual const SEG GetSegment(int aIndex) const =0

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

◆ Collide() [7/16]

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

Definition at line 370 of file shape_collisions.cpp.

372 {
373  if( aA.Collide( aSeg.GetSeg(), aClearance + aSeg.GetWidth() / 2, aActual, aLocation ) )
374  {
375  if( aActual )
376  *aActual = std::max( 0, *aActual - aSeg.GetWidth() / 2 );
377 
378  // TODO: why doesn't this handle MTV?
379 
380  return true;
381  }
382 
383  return false;
384 }
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() [8/16]

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

Definition at line 387 of file shape_collisions.cpp.

389 {
390  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation ) )
391  {
392  if( aActual )
393  *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
394 
395  // TODO: why doesn't this handle MTV?
396 
397  return true;
398  }
399 
400  return false;
401 }
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() [9/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 404 of file shape_collisions.cpp.

406 {
407  if( aA.Collide( aB.GetSeg(), aClearance + aB.GetWidth() / 2, aActual, aLocation ) )
408  {
409  if( aActual )
410  *aActual = std::max( 0, *aActual - aB.GetWidth() / 2 );
411 
412  // TODO: why doesn't this handle MTV?
413 
414  return true;
415  }
416 
417  return false;
418 }
const SEG & GetSeg() const
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
int GetWidth() const

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

◆ Collide() [10/16]

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

Definition at line 421 of file shape_collisions.cpp.

423 {
424  return Collide( aA.Outline(), aB.Outline(), aClearance, aActual, aLocation, aMTV );
425 }
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:176
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [11/16]

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

Definition at line 427 of file shape_collisions.cpp.

429 {
430  const auto lc = aA.ConvertToPolyline();
431  return Collide( lc, aB.Outline(), aClearance, aActual, aLocation, aMTV );
432 }
const SHAPE_LINE_CHAIN Outline() const
Definition: shape_rect.h:176
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [12/16]

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

Definition at line 434 of file shape_collisions.cpp.

436 {
437  const auto lc = aA.ConvertToPolyline();
438  bool rv = Collide( aB, lc, aClearance, aActual, aLocation, aMTV );
439 
440  if( rv && aMTV )
441  *aMTV = - *aMTV ;
442 
443  return rv;
444 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [13/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 446 of file shape_collisions.cpp.

448 {
449  const auto lc = aA.ConvertToPolyline();
450  return Collide( lc, aB, aClearance, aActual, aLocation, aMTV );
451 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [14/16]

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

Definition at line 453 of file shape_collisions.cpp.

455 {
456  const auto lc = aA.ConvertToPolyline();
457  return Collide( lc, aB, aClearance, aActual, aLocation, aMTV );
458 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [15/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 460 of file shape_collisions.cpp.

462 {
463  const auto lc = aA.ConvertToPolyline();
464 
465  return Collide( lc, aB, aClearance, aActual, aLocation, aMTV );
466 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ Collide() [16/16]

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

Definition at line 468 of file shape_collisions.cpp.

470 {
471  const auto lcA = aA.ConvertToPolyline();
472  const auto lcB = aB.ConvertToPolyline();
473  return Collide( lcA, lcB, aClearance, aActual, aLocation, aMTV );
474 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:370
static bool Collide(const SHAPE_CIRCLE &aA, const SHAPE_CIRCLE &aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

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

◆ collideShapes()

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

Definition at line 700 of file shape_collisions.cpp.

702 {
703  int currentActual = std::numeric_limits<int>::max();
704  VECTOR2I currentLocation;
705  VECTOR2I currentMTV(0, 0);
706  bool colliding = false;
707 
708  auto canExit =
709  [&]()
710  {
711  if( !colliding )
712  return false;
713 
714  if( aActual && currentActual > 0 )
715  return false;
716 
717  if( aMTV )
718  return false;
719 
720  return true;
721  };
722 
723  auto collideCompoundSubshapes =
724  [&]( const SHAPE* elemA, const SHAPE* elemB, int clearance ) -> bool
725  {
726  int actual = 0;
727  VECTOR2I location;
728  VECTOR2I mtv;
729 
730  if( collideSingleShapes( elemA, elemB, clearance,
731  aActual || aLocation ? &actual : nullptr,
732  aLocation ? &location : nullptr,
733  aMTV ? &mtv : nullptr ) )
734  {
735  if( actual < currentActual )
736  {
737  currentActual = actual;
738  currentLocation = location;
739  }
740 
741  if( aMTV && mtv.SquaredEuclideanNorm() > currentMTV.SquaredEuclideanNorm() )
742  {
743  currentMTV = mtv;
744  }
745 
746  return true;
747  }
748 
749  return false;
750  };
751 
752  if( aA->Type() == SH_COMPOUND && aB->Type() == SH_COMPOUND )
753  {
754  const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
755  const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
756 
757  for( const SHAPE* elemA : cmpA->Shapes() )
758  {
759  for( const SHAPE* elemB : cmpB->Shapes() )
760  {
761  if( collideCompoundSubshapes( elemA, elemB, aClearance ) )
762  {
763  colliding = true;
764 
765  if( canExit() )
766  break;
767  }
768  }
769 
770  if( canExit() )
771  break;
772  }
773  }
774  else if( aA->Type() == SH_COMPOUND )
775  {
776  const SHAPE_COMPOUND* cmpA = static_cast<const SHAPE_COMPOUND*>( aA );
777 
778  for( const SHAPE* elemA : cmpA->Shapes() )
779  {
780  if( collideCompoundSubshapes( elemA, aB, aClearance ) )
781  {
782  colliding = true;
783 
784  if( canExit() )
785  break;
786  }
787  }
788  }
789  else if( aB->Type() == SH_COMPOUND )
790  {
791  const SHAPE_COMPOUND* cmpB = static_cast<const SHAPE_COMPOUND*>( aB );
792 
793  for( const SHAPE* elemB : cmpB->Shapes() )
794  {
795  if( collideCompoundSubshapes( aA, elemB, aClearance ) )
796  {
797  colliding = true;
798 
799  if( canExit() )
800  break;
801  }
802  }
803  }
804  else
805  {
806  return collideSingleShapes( aA, aB, aClearance, aActual, aLocation, aMTV );
807  }
808 
809  if( colliding )
810  {
811  if( aLocation )
812  *aLocation = currentLocation;
813 
814  if( aActual )
815  *aActual = currentActual;
816 
817  if( aMTV )
818  *aMTV = currentMTV;
819  }
820 
821  return colliding;
822 }
set of polygons (with holes, etc.)
Definition: shape.h:49
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
SHAPE.
Definition: shape.h:122
const std::vector< SHAPE * > & Shapes() const
static bool collideSingleShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:98

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 499 of file shape_collisions.cpp.

501 {
502  switch( aA->Type() )
503  {
504  case SH_NULL:
505  return false;
506 
507  case SH_RECT:
508  switch( aB->Type() )
509  {
510  case SH_RECT:
511  return CollCase<SHAPE_RECT, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
512 
513  case SH_CIRCLE:
514  return CollCase<SHAPE_RECT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
515 
516  case SH_LINE_CHAIN:
517  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
518 
519  case SH_SEGMENT:
520  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
521 
522  case SH_SIMPLE:
524  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
525 
526  case SH_ARC:
527  return CollCaseReversed<SHAPE_RECT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
528 
529  case SH_NULL:
530  return false;
531 
532  default:
533  break;
534  }
535  break;
536 
537  case SH_CIRCLE:
538  switch( aB->Type() )
539  {
540  case SH_RECT:
541  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
542 
543  case SH_CIRCLE:
544  return CollCase<SHAPE_CIRCLE, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
545 
546  case SH_LINE_CHAIN:
547  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
548 
549  case SH_SEGMENT:
550  return CollCase<SHAPE_CIRCLE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
551 
552  case SH_SIMPLE:
554  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
555 
556  case SH_ARC:
557  return CollCaseReversed<SHAPE_CIRCLE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
558 
559  case SH_NULL:
560  return false;
561 
562  default:
563  break;
564  }
565  break;
566 
567  case SH_LINE_CHAIN:
568  switch( aB->Type() )
569  {
570  case SH_RECT:
571  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
572 
573  case SH_CIRCLE:
574  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN>( aB, aA, aClearance, aActual, aLocation, aMTV );
575 
576  case SH_LINE_CHAIN:
577  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
578 
579  case SH_SEGMENT:
580  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
581 
582  case SH_SIMPLE:
584  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
585 
586  case SH_ARC:
587  return CollCaseReversed<SHAPE_LINE_CHAIN, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
588 
589  case SH_NULL:
590  return false;
591 
592  default:
593  break;
594  }
595  break;
596 
597  case SH_SEGMENT:
598  switch( aB->Type() )
599  {
600  case SH_RECT:
601  return CollCase<SHAPE_RECT, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
602 
603  case SH_CIRCLE:
604  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
605 
606  case SH_LINE_CHAIN:
607  return CollCase<SHAPE_LINE_CHAIN, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
608 
609  case SH_SEGMENT:
610  return CollCase<SHAPE_SEGMENT, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
611 
612  case SH_SIMPLE:
614  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aB, aA, aClearance, aActual, aLocation, aMTV );
615 
616  case SH_ARC:
617  return CollCaseReversed<SHAPE_SEGMENT, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
618 
619  case SH_NULL:
620  return false;
621 
622  default:
623  break;
624  }
625  break;
626 
627  case SH_SIMPLE:
629  switch( aB->Type() )
630  {
631  case SH_RECT:
632  return CollCase<SHAPE_RECT, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
633 
634  case SH_CIRCLE:
635  return CollCase<SHAPE_CIRCLE, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
636 
637  case SH_LINE_CHAIN:
638  return CollCase<SHAPE_LINE_CHAIN, SHAPE_LINE_CHAIN_BASE>( aB, aA, aClearance, aActual, aLocation, aMTV );
639 
640  case SH_SEGMENT:
641  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
642 
643  case SH_SIMPLE:
645  return CollCase<SHAPE_LINE_CHAIN_BASE, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
646 
647  case SH_ARC:
648  return CollCaseReversed<SHAPE_LINE_CHAIN_BASE, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
649 
650  case SH_NULL:
651  return false;
652 
653  default:
654  break;
655  }
656  break;
657 
658  case SH_ARC:
659  switch( aB->Type() )
660  {
661  case SH_RECT:
662  return CollCase<SHAPE_ARC, SHAPE_RECT>( aA, aB, aClearance, aActual, aLocation, aMTV );
663 
664  case SH_CIRCLE:
665  return CollCase<SHAPE_ARC, SHAPE_CIRCLE>( aA, aB, aClearance, aActual, aLocation, aMTV );
666 
667  case SH_LINE_CHAIN:
668  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN>( aA, aB, aClearance, aActual, aLocation, aMTV );
669 
670  case SH_SEGMENT:
671  return CollCase<SHAPE_ARC, SHAPE_SEGMENT>( aA, aB, aClearance, aActual, aLocation, aMTV );
672 
673  case SH_SIMPLE:
675  return CollCase<SHAPE_ARC, SHAPE_LINE_CHAIN_BASE>( aA, aB, aClearance, aActual, aLocation, aMTV );
676 
677  case SH_ARC:
678  return CollCase<SHAPE_ARC, SHAPE_ARC>( aA, aB, aClearance, aActual, aLocation, aMTV );
679 
680  case SH_NULL:
681  return false;
682 
683  default:
684  break;
685  }
686  break;
687 
688  default:
689  break;
690  }
691 
692  bool unsupported_collision = true;
693  (void) unsupported_collision; // make gcc quiet
694 
695  wxASSERT( unsupported_collision == false );
696 
697  return false;
698 }
compound shape, consisting of multiple simple shapes
Definition: shape.h:50
line chain (polyline)
Definition: shape.h:46
empty shape (no shape...),
Definition: shape.h:52
circular arc
Definition: shape.h:51
line segment
Definition: shape.h:45
Definition: shape.h:43
circle
Definition: shape.h:47
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:98
axis-aligned rectangle
Definition: shape.h:44

References SH_ARC, SH_CIRCLE, SH_LINE_CHAIN, SH_NULL, SH_POLY_SET_TRIANGLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, 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.

148 {
149  VECTOR2I f( 0, 0 );
150 
151  const VECTOR2I c = aA.GetCenter();
152  const VECTOR2I nearest = aB.NearestPoint( c );
153 
154  const int r = aA.GetRadius();
155 
156  int dist = ( nearest - c ).EuclideanNorm();
157  int min_dist = aClearance + r;
158 
159  if( dist < min_dist )
160  {
161  for( int corr = 0; corr < 5; corr++ )
162  {
163  f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );
164 
165  if( aB.Distance( c + f ) >= min_dist )
166  break;
167  }
168  }
169 
170  return f;
171 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
int GetRadius() const
Definition: shape_circle.h:99
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:104
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().