algorithm - 如何检测椭圆是否与圆相交(相撞)

Question

我想改善碰撞系统。

现在，我检测2个不规则对象的边界矩形是否碰撞。

我想获得for矩形的相应椭圆，而另一个则使用圆形。我找到了一种获取椭圆坐标的方法，但是当我尝试检测椭圆是否与圆相交时遇到了问题。

您知道一种测试圆是否与椭圆相交的算法吗？

Answer 1

简短的答案:精确地解决两个对象是否相交的问题足够复杂，以至于无法用于碰撞检测。将您的椭圆离散为n边的多边形(取决于您需要的精度)，并对该多边形进行碰撞检测。

长答案:如果您坚持确定光滑的椭圆和圆是否相交，则有两种主要方法。两者都涉及先求解最接近椭圆上圆心的点，然后再将该距离与圆半径进行比较。

方法1 :使用椭圆的参数化。变换坐标，使椭圆位于原点，其轴与x-y轴对齐。那是:

椭圆中心:(0,0)

圆心:c =(cx，cy)

圆的半径:r

椭圆的x对齐轴的半径:

椭圆的y轴的半径:b。

然后由a cos(t), b sin(t)给出椭圆的方程。为了找到最接近的点，我们要最小化平方距离|| (a cos t, b sin t) - c ||^2。正如Jean所指出的，这是“只是微积分”:取一个导数，并将其设置为0。但是，除非我缺少某些内容，否则无法通过解析来解决t的结果(非常讨厌)方程，并且必须用例如近似牛顿法。
将找到的t插入参数方程式以获得最接近的点。

Pro:数值求解仅在一个变量t中进行。

缺点:您必须能够写下椭圆的参数化，或变换坐标才能如此。对于您对椭圆的任何合理表示，这都不应该太难。但是，我将向您展示第二种方法，该方法更为通用，如果您必须将问题推广到3D模式，则可能会很有用。

方法2 :使用多维演算。无需更改坐标。

圆心:c =(cx，cy)

半径:r

椭圆由函数g的g(x，y)= 0给出。例如，根据Curd的答案，您可以使用g(x，y)=距焦点1的(x，y)的距离+距焦点2的(x，y)的距离-e。

然后在椭圆上找到最接近圆心的点可以说成是约束最小化问题:
Minimize ||(x,y) - c||^2 subject to g(x,y) = 0
(最小化平方距离等效于最小化距离，并且由于它是x，y的二次多项式，因此处理起来也更加令人愉快。)

为了解决约束最小化问题，我们引入了拉格朗日乘数 lambda ，并求解了方程组

2 * [ (x,y) -c ] + lambda * Jg(x,y) = 0
g(x,y) = 0

Jg是g的梯度。这是一个由三个(非线性)方程式组成的系统，其中包含三个未知数:x，y和lambda。我们可以使用牛顿法求解该系统，得到的(x，y)是最接近圆心的点。

Pro:无需找到参数化

Pro:方法非常通用，只要编写g比查找参数方程式(例如在3D中)容易，方法就可以很好地工作。

缺点:需要多变量牛顿求解，如果您无法访问数值方法包，则此函数非常耗时。

注意:这两种方法都从技术上解决了将圆弧中心距离最大化的问题。因此，找到的点可能是圆中最远的点，而不是最接近的点。对于这两种方法，都可以使用一个很好的初始猜测来播种您的解决方案(圆心对于方法2效果很好；对于方法1而言，您自己一个人)会减少这种危险。

潜在的第三种方法？ :可以直接在代表圆形和椭圆形的两个变量中求解两个二次方程组的系统根。如果存在真实根，则对象相交。再次使用牛顿法之类的数值算法来求解该系统的最直接方法将无济于事，因为缺乏收敛性不一定意味着不存在真实根。但是，对于两个变量中的两个二次方程式，可能存在一种专门的方法，可以保证找到真实的根(如果存在)。我自己想不出一种方法，但是您可能想自己研究一下(或者看看是否有stackoverflow的人可以详细说明)。