circl rectangle intersect 圆与矩形相交

A Box-Sphere Intersection Test

A very elegant box-sphere intersection test is described in [1]. Figure 7 shows two configurations of a sphere and a box in 2D. Sphere A is closest to an edge, whereas sphere B is closest to a corner. The algorithm calculates the square of the distance from the box to the sphere by analyzing the orientation of the sphere relative to the box in a single loop.

If the box is not axis aligned, simply transform the center of the sphere to the box's local coordinate frame. Listing 5 gives an implementation of Arvo's algorithm.

Listing 5. Arvo's algorithm.

#include "aabb.h"
//Check to see if the sphere overlaps the AABB
const bool AABBOverlapsSphere ( const AABB& B, const SCALAR r, VECTOR& C )
{
  float s, d = 0;
  //find the square of the distance from the sphere to the box
  for( long i=0 ; i<3 ; i++ )
  {
    if( C[i] < B.min(i) )
    {
      s = C[i] - B.min(i);
      d += s*s;
    }
    else if( C[i] > B.max(i) )
    {
      s = C[i] - B.max(i);
      d += s*s;
    }
  }
  return d <= r*r;
}

refer:

https://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php?print=1

说说自己的理解.

1)虽然上面的算法仅仅适用于aabb和圆相交.但是可以通过以矩形自己为坐标系,重新定义圆相对于该矩形的坐标,这样在矩形坐标系下,矩形自身就是aabb了.
2)算法的核心是寻找一个圆形(球)距离aabb最近的点. 对于2d的aabb而言, aabb可以把自身外部分隔为8个空间, 其中上下左右这四个空间最近点就是圆心垂直改边. 另外四个空间最近点就是矩形的四个顶点.显而易见, 最近点到圆心的距离小于等于radius的话, 两者就相交.