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

Question

我想改进碰撞系统.

现在我发现如果它们的边界矩形碰撞,是否有2个不规则物体碰撞.

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

你知道一个算法来测试圆是否与椭圆相交吗？

Answer 1

简短回答:准确地确定两个物体是否相交是复杂到足以使其不可能用于碰撞检测.将椭圆分离为某个n的n边多边形(取决于您需要的准确度),并使用该多边形进行碰撞检测.

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

方法1:使用椭圆的参数化.变换坐标,使椭圆位于原点,其轴与xy轴对齐.那是:

• 椭圆中心:(0,0)
• 圆心:c =(cx,cy)
• 圆的半径:r
• x对齐椭圆轴的半径:a
• y对齐椭圆轴的半径:b.

然后给出椭圆的方程a cos(t), b sin(t).为了找到最近的点,我们希望最小化平方距离 || (a cos t, b sin t) - c ||^2.正如Jean指出的那样,这只是"微积分":取一个导数,并将其设置为0.除非我遗漏了某些东西,否则t解析得到的(非常讨厌的)方程式是不可能的,并且必须近似使用例如牛顿法.插入t您在参数方程中找到最接近的点.

• Pro:数值求解只在一个变量中t.
• Con:您必须能够记下椭圆的参数化,或者转换坐标以便可以.对于椭圆的任何合理表示,这不应该太难.但是,我将向您展示第二种方法,这种方法更为通用,如果您必须将问题概括为3D,可能会有用.

方法2:使用多维微积分.不需要改变坐标.

• 圆心:c =(cx,cy)
• cirlce半径:r
• 对于函数g,椭圆由g(x,y)= 0给出.例如,根据Curd的答案,您可以使用g(x,y)=距焦点1的距离(x,y)+焦点2-e的距离(x,y).

找到最接近圆心的椭圆上的点可以表达为约束最小化问题:

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)更容易,效果很好
• Con:需要多变量Newton求解,如果您无法访问数值方法包,则非常多毛.

警告:这两种方法在技术上都解决了极限距离圆心的距离.因此,找到的点可能是圆的最远点,而不是最接近的点.对于这两种方法,通过良好的初始猜测来播种你的求解(方法2的圆心适用于方法2;你自己为方法1)将减少这种危险.

第三种方法？:有可能在表示圆和椭圆的两个变量中直接求解两个二次方程组的根.如果存在真正的根,则对象相交.解决这个系统的最直接的方法,再次使用像牛顿方法这样的数值算法,将无济于事,因为缺乏收敛并不一定意味着不存在真正的根.然而,对于两个变量中的两个二次方程,可能存在一种专门的方法,如果它们存在,它们可以保证找到真正的根.我自己也想不出这样做的方法,但你可能想自己研究它(或者看看stackoverflow上的某个人是否可以详细说明.)

Answer 2

椭圆被定义为一组点,其到点A的距离和到点B的距离之和是常数e.(A和B称为椭圆的焦点).

所有点P,其总和AP + BP小于e,位于椭圆内.

圆被定义为到点C的距离为r的点集.

圆和椭圆相交的简单测试如下:

找到
P作为圆与线AC和
Q的交点作为圆与线BC的交点.

如果
AP + BP <= e或AQ + BQ <= e,则圆和椭圆相交(或圆完全位于椭圆内)

编辑:

在Martin DeMello发表评论并相应地调整我的答案后,我更多地考虑了问题并发现答案(第二次检查)仍未检测到所有交叉点:

如果圆和椭圆仅相交很少(只是略微相切)P和Q不会位于椭圆内:

因此,上述测试仅在重叠"足够大"时才检测到碰撞.也许这对你的实际目的来说已经足够了,虽然在数学上它并不完美.

Answer 3

我知道为时已晚，但希望对您有所帮助。我解决此问题的方法是将椭圆插值成n维多边形，然后在每2个点之间构造一条直线，并确定该圆是否与任何直线相交。这不能提供最佳性能，但是它方便且易于实现。

要将椭圆插值到n维多边形，可以使用：

float delta = (2 * PI) / n;

std::vector<Point*> interpolation;

for(float t = 0; t < (2 * PI); t += delta) {

    float x = rx * cos(t) + c->get_x();
    float y = ry * sin(t) + c->get_y();

    interpolation.push_back(new Point(x, y));
}

c：椭圆的中心。rx：椭圆的x对齐轴的半径。ry：椭圆的y轴的半径。

现在我们有了插值点，我们可以找到圆与直线之间每2个点之间的交点。此处描述了一种找到线与线交点的方法，如果任何一条线与圆之间发生交点，就会发生交点。

希望这对任何人有帮助。