一尘不染

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

algorithm

我想改善碰撞系统。

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

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

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


阅读 1159

收藏
2020-07-28

共1个答案

一尘不染

简短的答案:精确地解决两个对象是否相交的问题足够复杂,以至于无法用于碰撞检测。将您的椭圆离散为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
  • 缺点:您必须能够记下椭圆的参数化,或者变换坐标才能如此。对于您对椭圆的任何合理表示,这都不应该太难。但是,我将向您展示第二种方法,该方法更为通用,如果您必须将问题推广到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中的二次多项式。)

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

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

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

  • 优点:无需找到参数化
  • 优点:方法非常通用,只要编写g比查找参数方程式容易(例如在3D中),方法就很好用
  • 缺点:需要使用多变量牛顿法求解,如果您无法访问数值方法包,则该方法将非常耗时。

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

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

2020-07-28