移动圆和固定线段之间的2D碰撞

Question

在游戏程序的背景下，我有一个移动的圆和一条固定的线段。该线段可以具有任意大小和方向。

• 我知道圆的半径：r
• 我知道移动前圆的坐标：(xC1，yC1)
• 我知道移动后圆的坐标：(xC2，yC2)
• 我知道线段端点的坐标：(xL1，yL1) - (xL2，yL2)

计算时，我遇到了困难:

• 一个布尔值：如果圆在从（xC1，yC1）移动到（xC2，yC2）的过程中击中线段的任何部分
• 如果布尔值为真，则是圆第一次与线段相切时的圆心坐标（x，y）

- Joel

---

从技术上讲，您需要处理向量 xC1/yC1 和 xC2/yC2 之间的每个插值点，这是我将要使用的搜索术语。但是，这是一个编程主题的编程板块，我们无法在此回答这个问题，因为我们不知道您正在使用哪种技术/语言/API。抱歉。 - Russ Clarke

@Russ C：实际上，它确实属于这个社区，因为它涉及到一个“软件算法”。因此，它适用于任何可用于游戏编程的编程语言（至少是），所以问题是“与语言无关的”。 - Peter O.

不，这涉及到一个数学辩论。没有讨论技术、API或者OP尝试解决问题的内容。最好的情况是社区维基，最坏的情况是会变成关于最好或最差尝试的争论。有人可能发布了一个很好的答案，但因为他们使用极坐标而不是笛卡尔坐标而被踩。请参见http://stackoverflow.com/faq#dontask。我同意我应该更具体地表达我的评论，要求Joel进一步完善他的问题。 - Russ Clarke

Answer 1

我将用伪算法回答 - 不含任何代码。从我的角度看，根据下面的图像，我们可能会有两种情况返回true:

这里蓝色的是你的圆，虚线是轨迹线，红线是给定的线。

• 我们构建一个助手轨迹线，从两个圆的中心到中心。如果这条轨迹线与给定的线相交-返回true。请参见this question如何计算该交点。
• 在第二种情况下，第一次测试失败了，但很可能圆在轨迹上通过时会碰到线。我们需要以下构造：

从轨迹线我们构建到每个点A和B的法线。然后将这些线削减或延长成助手线(Ha和Hb)，使它们从A和B的长度恰好是圆的半径。然后检查这些辅助线是否与轨迹线相交。如果它们相交返回true。

• 否则返回false。

- Gleno

---

我认为这个答案比被选中的更好。它更易于理解，并且可以通过视觉方式更详细地帮助读者了解数学应该如何执行等内容。 - 1owk3y

听起来你对问题有很好的理解，但我不知道你的nudge case方法是如何工作的。你能解释一下为什么这个方法有效或者更详细地说明一下吗？ - dylan

你的方法是否能够计算线段和圆的交点？ - dylan

如果任何一条线是垂直或水平的呢？或者如果这条线试图串穿圆形呢？ - dylan

Answer 2

看这里：

线段/圆相交

如果在计算x或y的平方根下得到的值为负数，则该线段不相交。除此之外，一旦您获得了x和y（注意：您可能会得到两个答案），就可以停止计算。

更新 我已经修改了我的答案，非常具体地解决了您的问题。我要感谢Doswa提供的解决方案，因为我基本上是跟着他的思路写的C#代码。基本策略是我们要找到线段最靠近圆心的点。基于这个点，我们将查看该最接近点的距离，如果它在半径范围内，则沿着指向最接近点的方向定位到刚好在圆的半径处的点。

// I'll bet you already have one of these.
public class Vec : Tuple<double, double>
{
  public Vec(double item1, double item2) : base(item1, item2) { }
  public double Dot(Vec other) 
    { return Item1*other.Item1 + Item2*other.Item2; }
  public static Vec operator-(Vec first, Vec second) 
    { return new Vec(first.Item1 - second.Item1, first.Item2 - second.Item2);}
  public static Vec operator+(Vec first, Vec second) 
    { return new Vec(first.Item1 + second.Item1, first.Item2 + second.Item2);}
  public static Vec operator*(double first, Vec second) 
    { return new Vec(first * second.Item1, first * second.Item2);}
  public double Length() { return Math.Sqrt(Dot(this)); }
  public Vec Normalize() { return (1 / Length()) * this; }
}

public bool IntersectCircle(Vec origin, Vec lineStart, 
      Vec lineEnd, Vec circle, double radius, out Vec circleWhenHit)
{
    circleWhenHit = null;

    // find the closest point on the line segment to the center of the circle
    var line = lineEnd - lineStart;
    var lineLength = line.Length();
    var lineNorm = (1/lineLength)*line;
    var segmentToCircle = circle - lineStart;
    var closestPointOnSegment = segmentToCircle.Dot(line) / lineLength;

    // Special cases where the closest point happens to be the end points
    Vec closest;
    if (closestPointOnSegment < 0) closest = lineStart;
    else if (closestPointOnSegment > lineLength) closest = lineEnd;
    else closest = lineStart + closestPointOnSegment*lineNorm;

    // Find that distance.  If it is less than the radius, then we 
    // are within the circle
    var distanceFromClosest = circle - closest;
    var distanceFromClosestLength = distanceFromClosest.Length();
    if (distanceFromClosestLength > radius) return false;

    // So find the distance that places the intersection point right at 
    // the radius.  This is the center of the circle at the time of collision
    // and is different than the result from Doswa
    var offset = (radius - distanceFromClosestLength) *
                 ((1/distanceFromClosestLength)*distanceFromClosest);
    circleWhenHit = circle - offset;

    return true;
}

- Michael Hays

---

除了这个问题，圆形是在移动的。您建议模拟运动并在模拟的每一步计算此交点吗？ - Gleno

是的。就计算而言，点积和平方是比较廉价的。我利用GPU进行实时光线追踪，我调用点积的次数非常多。而光线与球体相交方程式是你工具箱中最有用的方程之一。唯一更好的可能是轴向包围盒（ABB）。球体和ABB通常用于包装场景中更复杂的对象，将场景划分为更小的测试集，因为它们的计算成本相对较低。 - Michael Hays

编辑 - 糟糕...我的意思是AABB（轴对齐包围盒）。哦，好吧，在答案中说对了。 - Michael Hays

Answer 3

这里有一些Java代码，用于计算点到线的距离（这不是完整的代码，但可以给你一个基本的概念）。该代码来自一个名为“Vector”的类。假设向量对象已初始化为线向量。方法“distance”接受线向量起始点（当然称为“at”）和感兴趣的点。它计算并返回该点到线的距离。

public class Vector
{
double x_ = 0;
double y_ = 0;
double magnitude_ = 1;

public Vector()
{
}

public Vector(double x,double y)
{
    x_ = x;
    y_ = y;
}

public Vector(Vector other)
{
    x_ = other.x_;
    y_ = other.y_;
}

public void add(Vector other)
{
    x_ += other.x_;
    y_ += other.y_;
}

public void scale(double val)
{
    x_ *= val;
    y_ *= val;
}

public double dot(Vector other)
{
    return x_*other.x_+y_*other.y_;
}

public void cross(Vector other)
{
    x_ = x_*other.y_ - y_*other.x_;
}

public void unit()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    x_/=magnitude_;
    y_/=magnitude_;
}

public double distance(Vector at,Vector point)
{
    //
    // Create a perpendicular vector
    //
    Vector perp = new Vector();
    perp.perpendicular(this);
    perp.unit();

    Vector offset = new Vector(point.x_ - at.x_,point.y_ - at.y_);
    double d = Math.abs(offset.dot(perp));

    double m = magnitude();
    double t = dot(offset)/(m*m);
    if(t < 0)
    {
        offset.x_ -= at.x_;
        offset.y_ -= at.y_;
        d = offset.magnitude();
    }
    if(t > 1)
    {
        offset.x_ -= at.x_+x_;
        offset.y_ -= at.y_+y_;
        d = offset.magnitude();
    }
    return d;
}

private void perpendicular(Vector other)
{
    x_ = -other.y_;
    y_ = other.x_;
}

public double magnitude()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    return magnitude_;
}
}

- Jim