我想改进一下碰撞系统。
目前，我是通过检测包围矩形是否相交来判断两个不规则物体是否碰撞。
我想得到对于一个矩形而言相应的椭圆，而对于另一个物体则使用圆形。我找到了一种方法来获取椭圆坐标，但是当我尝试检测它是否与圆相交时遇到了问题。
你知道如何测试一个圆是否与一个椭圆相交的算法吗？
10个回答
26
简短回答：精确解决两个对象是否相交的问题非常复杂，无法用于碰撞检测。将椭圆离散化为n边形（n取决于您需要多么准确），并使用该多边形进行碰撞检测。
长回答：如果您坚持确定光滑的椭圆和圆是否相交，则有两种主要方法。两种方法都涉及首先解决椭圆上距离圆心最近的点，然后将该距离与圆的半径进行比较。
方法1：使用椭圆的参数化。转换坐标，使椭圆位于原点，并使其轴与x-y轴对齐。也就是说：
- 椭圆中心：(0,0) - 圆的中心：c=(cx,cy) - 圆的半径：r - 椭圆x轴对齐轴的半径：a - 椭圆y轴对齐轴的半径：b。
然后，椭圆的方程由acos(t)，bsin(t)给出。为了找到最接近的点，我们要最小化平方距离|| (a cos t, b sin t) - c || ^ 2。正如Jean所指出的那样，这只是微积分：求导，将其设置为0。除非我错过了什么，否则解决结果（相当难看）的等式对t进行解析，必须使用例如牛顿法进行近似计算。将找到的t插入参数方程中以获得最接近的点。
优点：数值求解仅涉及一个变量t。 缺点：您必须能够写出椭圆的参数化表达式，或者转换坐标使您能够这样做。对于您拥有的任何合理表示，这不应该太难。但是，我将向您展示第二种方法，这种方法更通用，并且如果您必须将问题推广到例如3D等方面，则可能很有用。
方法2：使用多维微积分。无需更改坐标。
- 圆的中心：c = (cx, cy) - 圆的半径：r - 椭圆由函数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
长回答：如果您坚持确定光滑的椭圆和圆是否相交，则有两种主要方法。两种方法都涉及首先解决椭圆上距离圆心最近的点，然后将该距离与圆的半径进行比较。
方法1：使用椭圆的参数化。转换坐标，使椭圆位于原点，并使其轴与x-y轴对齐。也就是说：
- 椭圆中心：(0,0) - 圆的中心：c=(cx,cy) - 圆的半径：r - 椭圆x轴对齐轴的半径：a - 椭圆y轴对齐轴的半径：b。
然后，椭圆的方程由acos(t)，bsin(t)给出。为了找到最接近的点，我们要最小化平方距离|| (a cos t, b sin t) - c || ^ 2。正如Jean所指出的那样，这只是微积分：求导，将其设置为0。除非我错过了什么，否则解决结果（相当难看）的等式对t进行解析，必须使用例如牛顿法进行近似计算。将找到的t插入参数方程中以获得最接近的点。
优点：数值求解仅涉及一个变量t。 缺点：您必须能够写出椭圆的参数化表达式，或者转换坐标使您能够这样做。对于您拥有的任何合理表示，这不应该太难。但是，我将向您展示第二种方法，这种方法更通用，并且如果您必须将问题推广到例如3D等方面，则可能很有用。
方法2：使用多维微积分。无需更改坐标。
- 圆的中心：c = (cx, cy) - 圆的半径：r - 椭圆由函数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）是离圆心最近的点。
- 优点：无需找到参数化
- 优点：该方法非常通用，在编写g比查找参数方程更容易的情况下效果很好（例如在3D中）
- 缺点：需要多元牛顿求解，如果您没有访问数字方法包，则非常棘手。
提示：这两种方法都从技术上解决了极小化到圆心距离的点。因此，找到的点可能是距离圆最远的点，而不是最近的点。对于这两种方法，使用良好的初始猜测（圆的中心对于方法2效果很好；对于方法1，您需要自己解决）将减少此风险。
第三种可能的方法？：直接解决代表圆和椭圆的两个二次方程组的根可能是可行的。如果存在实根，则对象相交。再次使用像牛顿法这样的数值算法直接解决这个系统是行不通的，因为缺乏收敛并不一定意味着不存在实根。然而，对于两个二次方程的两个变量，可能存在一种专门的方法，可以保证找到实根（如果存在）。我自己想不出如何做到这一点，但您可能需要自己研究它（或查看stackoverflow上是否有人可以详细说明）。
- user168715
2
1请注意，您需要另一组检查来确定圆是否完全位于椭圆内。 - Martin DeMello
谢谢，我以为有更简单的解决方案。显然，不仅在碰撞检测方面难以实现，而且速度也会非常慢。 - adiian
22
椭圆被定义为一组点，这些点到点A和点B的距离之和是常数e（A和B被称为椭圆的焦点）。
所有满足AP + BP小于e的点P都在椭圆内部。
圆被定义为到点C距离为r的点的集合。
以下是圆和椭圆相交的简单测试：
找到P作为圆与线段AC的交点
找到Q作为圆与线段BC的交点
如果AP + BP <= e或AQ + BQ <= e，则圆和椭圆相交（或圆完全位于椭圆内部）
编辑：
根据Martin DeMello的评论并相应调整我的答案后，我进一步思考了这个问题，并发现（带有第二个检查）仍然不能检测到所有交点：
如果圆和椭圆只是轻微地相交（仅比切线多一点），则P和Q将不在椭圆内：
因此，上述描述的测试仅在重叠区域“足够大”时检测到碰撞。也许对于您的实际目的来说已经足够好了，尽管从数学上讲它不是完美的。
- Curd
6
1兄弟，说得好。你是引用了教科书吗？ - Warren P
1不，椭圆和圆的定义是共通的。其他部分你可以很容易地推导出来。 - Curd
6我相当确定一个圆可以与椭圆相交，且圆心与椭圆焦点的交点仍在椭圆外。考虑一个圆的顶部与一端细长椭圆相交，并选择远离它的焦点。编辑：这是一个图示：http://i.imgur.com/FU2MN.png - Martin DeMello
@Martin DeMello：你说得对。我认为再进行一次检查就可以解决问题了（尽管没有被证明）。谢谢。我会相应地编辑答案。 - Curd
一个想法：我没有证据，但在这个问题的情况下，我认为交点将必须位于锐角弧PQ之间。如果是这种情况，您可以通过测试该弧内圆上的一组点并查看其中是否有任何点在椭圆内来使测试更准确。 - aspo
据我所知，这个程序是通过“尝试在椭圆内找到一个交点”来实现的，但由于你制作了两个椭圆，你不知道它们之间的行为。那么，如果你只通过连接椭圆和圆的中心来创建一个交点呢？那个方向应该是“最接近连接两个中心”的...或者也许检查所有三个中心。 - Carlo Moretti
7
我知道现在可能已经太晚了，但我希望这能帮到某些人。我的解决方法是将椭圆插值为n维多边形，然后构造每两个点之间的线段，并查找圆是否与任何线段相交。这种方法的性能并不是最好的，但它很方便且易于实现。
要将椭圆插值为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 轴半径。
现在我们有了插值点，就可以找到圆与每两个点之间连线的交点。一种查找线圆交点的方式在这里描述，如果任何一条线与圆相交，则会发生交点。
希望这能帮助任何人。
- Mo Abdul-Hameed
3
如果一个圆和一个椭圆相撞，那么它们的边界要么相交1、2、3或4次（或在圆形椭圆与圆重合的情况下无限多次），要么圆在椭圆内部或反之亦然。
我假设圆的方程为(x-a)² + (y-b)² ≤ r² （1），椭圆的方程为[(x-c)²]/[d²] + [(y-e)²]/[f²] ≤ 1 （2）。
要检查它们中的一个是否在另一个内部，可以在椭圆的中心坐标处（x=c，y=e）评估圆的方程，反之亦然，并查看不等式是否成立。
要检查它们的边界相交的其他情况，必须检查由（1）和（2）描述的方程组是否有任何解。
你可以通过将（1）和（2）相加来实现这一点，得到
(x-a)² + (y-b)² + [(x-c)²]/[d²] + [(y-e)²]/[f²] = r² + 1
接下来，你需要展开这些项，得到
x² - 2ax + a² + y² - 2by + b² + x²/d² - 2cx/d² + c²/d² + y²/f² - 2ey/f² + e²/f² = r² + 1
将同类项收集起来，我们得到
(1 + 1/d²)x² - (2a + 2c/d²)x + (1 + 1/f²)y² - (2b + 2e/f²)y = 1 + r² - a² - b² - c²/d² - e²/f²
现在令m = (1 + 1/d²)，n = -(2a + 2c/d²)，o = (1 + 1/f²)，p = -(2b + 2e/f²)
方程现在变为mx² + nx + oy² + py = 1 + r² - a² - b² - c²/d² - e²/f²
现在我们需要对左边进行平方处理。
我假设圆的方程为(x-a)² + (y-b)² ≤ r² （1），椭圆的方程为[(x-c)²]/[d²] + [(y-e)²]/[f²] ≤ 1 （2）。
要检查它们中的一个是否在另一个内部，可以在椭圆的中心坐标处（x=c，y=e）评估圆的方程，反之亦然，并查看不等式是否成立。
要检查它们的边界相交的其他情况，必须检查由（1）和（2）描述的方程组是否有任何解。
你可以通过将（1）和（2）相加来实现这一点，得到
(x-a)² + (y-b)² + [(x-c)²]/[d²] + [(y-e)²]/[f²] = r² + 1
接下来，你需要展开这些项，得到
x² - 2ax + a² + y² - 2by + b² + x²/d² - 2cx/d² + c²/d² + y²/f² - 2ey/f² + e²/f² = r² + 1
将同类项收集起来，我们得到
(1 + 1/d²)x² - (2a + 2c/d²)x + (1 + 1/f²)y² - (2b + 2e/f²)y = 1 + r² - a² - b² - c²/d² - e²/f²
现在令m = (1 + 1/d²)，n = -(2a + 2c/d²)，o = (1 + 1/f²)，p = -(2b + 2e/f²)
方程现在变为mx² + nx + oy² + py = 1 + r² - a² - b² - c²/d² - e²/f²
现在我们需要对左边进行平方处理。
m[x^2 + (n/m)x] + o[y^2 + (p/o)y] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2
m[x^2 + (n/m)x + (n/2m)^2 - (n/2m)^2] + o[y^2 + (p/o)y + (p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2
m[(x + n/2m)^2 - (n/2m)^2] + o[(y + p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2
m(x + n/2m)^2 - m(n/2m)^2 + o(y + p/2o)^2 - o(p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2
m(x + n/2m)^2 + o(y + p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2
这个系统有一个解决方案，当且仅当11 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 >= 0
如果我没有犯代数错误，这就是答案。我不知道你能简化多少，所以如果你要检查很多圆/椭圆，这个解决方案可能会非常耗费计算资源。
- Bwmat
4
1为什么椭圆不能在
xy 中有交叉项（例如，如果它不是轴对齐的）？我认为类似的方法可能会起作用。 - user168715哎呀，我完全忘记了偏斜的椭圆，我在各种数学课程中从未真正遇到过它们。我不确定是否容易修改这种方法来处理它们。 - Bwmat
由于圆无论如何旋转和平移坐标系都不会改变形状，所以您可以将坐标轴重新定义为椭圆的主轴。 - Martin DeMello
请问能否澄清开始时的步骤，其中您有 f(x,y) = r^2 (1)，g(x,y) = 1 (2)，然后说当 f(x, y) + g(x, y) = r^2 + 1 (3) 时它们具有联合解？我不确定是否我理解错了，但我不明白为什么这是真的。例如，满足联合方程（3）的解 X,Y 可能是使得 f(X,Y) = 2 和 g(X,Y) = r^2 - 1 的值。那将不是(1)或(2)的解。 - andrew cooke
3
找到椭圆上距离圆心最近的点，
然后检查该点到圆心的距离是否小于圆的半径
如果需要帮助，请评论，但这只是微积分问题。
编辑：以下是解决方案的一种方法，由于curds有问题，因此需要进行更正。
给定椭圆上的中心αβ
以及（由于不记得术语）x半径a、y半径b
参数化为
r（Θ）=（ab）/（（（BcosΘ）^2 +（asinΘ）^2）^.5）
x（Θ）=α+sin（Θ）r（Θ）
y（Θ）=β+cos（Θ）r（Θ）
然后取以（φ，ψ）为圆心、半径为r的圆
那么距离d（Θ）=（（φ-x（Θ））^2 +（ψ-y（Θ））^2）^.5
当d'（Θ）= 0（'表示导数）时，这个距离的最小值就出现了
d'（Θ）=1/d（Θ）*（-φx'（Θ）+x（Θ）x'（Θ）-ψy'（Θ）+y（Θ）y'（Θ））
==>
x'（Θ）*（-φ + x（Θ））= y'（Θ）*（ψ-y（Θ））
然后继续推导，希望你能解出Θ的值
你所使用的框架可能有助于解决这个问题，你也可以通过牛顿法来近似求根。
然后检查该点到圆心的距离是否小于圆的半径
如果需要帮助，请评论，但这只是微积分问题。
编辑：以下是解决方案的一种方法，由于curds有问题，因此需要进行更正。
给定椭圆上的中心αβ
以及（由于不记得术语）x半径a、y半径b
参数化为
r（Θ）=（ab）/（（（BcosΘ）^2 +（asinΘ）^2）^.5）
x（Θ）=α+sin（Θ）r（Θ）
y（Θ）=β+cos（Θ）r（Θ）
然后取以（φ，ψ）为圆心、半径为r的圆
那么距离d（Θ）=（（φ-x（Θ））^2 +（ψ-y（Θ））^2）^.5
当d'（Θ）= 0（'表示导数）时，这个距离的最小值就出现了
d'（Θ）=1/d（Θ）*（-φx'（Θ）+x（Θ）x'（Θ）-ψy'（Θ）+y（Θ）y'（Θ））
==>
x'（Θ）*（-φ + x（Θ））= y'（Θ）*（ψ-y（Θ））
然后继续推导，希望你能解出Θ的值
你所使用的框架可能有助于解决这个问题，你也可以通过牛顿法来近似求根。
- Jean-Bernard Pellerin
3
忘记数学解法吧。通过绘图，您可以看到最多有四个解，因此可能是一个四次多项式。
相反，只需沿着其中一个图形的边界进行二分搜索。很容易确定一个点是否在椭圆内，甚至更容易在圆内（只需查看距离是否小于半径）。
如果您真的想尝试数学方法，Wolfram MathWorld 在这里有一篇不错的文章：http://mathworld.wolfram.com/Circle-EllipseIntersection.html 但请注意，您仍然需要编写一个多项式方程求解器，可能使用类似二分搜索的东西。
相反，只需沿着其中一个图形的边界进行二分搜索。很容易确定一个点是否在椭圆内，甚至更容易在圆内（只需查看距离是否小于半径）。
如果您真的想尝试数学方法，Wolfram MathWorld 在这里有一篇不错的文章：http://mathworld.wolfram.com/Circle-EllipseIntersection.html 但请注意，您仍然需要编写一个多项式方程求解器，可能使用类似二分搜索的东西。
- Thomas Ahle
3
将椭圆的长轴和短轴半径分别增加圆的半径。然后通过将到扩大后椭圆的两个焦点的距离相加来测试给定圆的中心是否位于这个新的更大的椭圆内。
这个算法非常高效。如果给定的圆不与外接椭圆相交，您可以提前退出。这比边界框测试要慢，但是找到非轴对齐椭圆的边界框很棘手。
- Danny Epstein
1
1不正确。我按照您在此示例中的步骤进行操作：http://imgur.com/aFheiHM。正如您所看到的，圆和椭圆相交，但圆的中心不在放大后的椭圆内。 - Jaxan
1
假设：
椭圆以原点为中心，半长轴（长度为a）沿x轴方向，半短轴长度为b；E2是离心率的平方，即(a*a-b*b)/(a*a)；
圆心在X,Y处，半径为r。
简单情况如下： 圆心在椭圆内部（即hypot(X/a, Y/b) <= 1），则有交集； 圆心在以0为中心、半径为a+r的圆外部（即hypot(X,Y) > a+r），则没有交集。
其他情况的一种方法是计算圆心的大地坐标（纬度、高度）。当且仅当高度小于半径时，圆与椭圆相交。
椭圆上一点的大地纬度是该点法线与x轴的夹角，而椭圆外一点的高度是该点到最靠近它的椭圆上的点的距离。请注意，除非椭圆实际上是圆形，否则大地纬度与从椭圆中心到该点的极角不同。
在公式中，从大地坐标lat、ht到笛卡尔坐标X、Y的转换为： X = (nu+ht)*cos(lat)，Y = (nu*(1-E2)+ht)*sin(lat) 其中nu = a/sqrt(1 - E2*sin(lat) * sin(lat))。离X、Y最近的椭圆上的点是具有相同纬度但高度为零的点，即x = nu*cos(lat)，y = nu*(1-E2)*sin(lat)。请注意，nu是纬度的函数。
不幸的是，从X、Y找到lat、ht的过程是一个迭代的过程。一种方法是先找到纬度，然后再找到高度。
一些代数运算表明纬度满足： lat = atan2(Y + E2*nu*sin(lat), X) 可以用来计算纬度的连续逼近，从lat = atan2(Y, X*(1.0-E2))开始，或者（更有效地）可以使用牛顿法来解决。
简单情况如下： 圆心在椭圆内部（即hypot(X/a, Y/b) <= 1），则有交集； 圆心在以0为中心、半径为a+r的圆外部（即hypot(X,Y) > a+r），则没有交集。
其他情况的一种方法是计算圆心的大地坐标（纬度、高度）。当且仅当高度小于半径时，圆与椭圆相交。
椭圆上一点的大地纬度是该点法线与x轴的夹角，而椭圆外一点的高度是该点到最靠近它的椭圆上的点的距离。请注意，除非椭圆实际上是圆形，否则大地纬度与从椭圆中心到该点的极角不同。
在公式中，从大地坐标lat、ht到笛卡尔坐标X、Y的转换为： X = (nu+ht)*cos(lat)，Y = (nu*(1-E2)+ht)*sin(lat) 其中nu = a/sqrt(1 - E2*sin(lat) * sin(lat))。离X、Y最近的椭圆上的点是具有相同纬度但高度为零的点，即x = nu*cos(lat)，y = nu*(1-E2)*sin(lat)。请注意，nu是纬度的函数。
不幸的是，从X、Y找到lat、ht的过程是一个迭代的过程。一种方法是先找到纬度，然后再找到高度。
一些代数运算表明纬度满足： lat = atan2(Y + E2*nu*sin(lat), X) 可以用来计算纬度的连续逼近，从lat = atan2(Y, X*(1.0-E2))开始，或者（更有效地）可以使用牛顿法来解决。
当E2越大，即椭圆越扁平时，需要的迭代次数就越多。例如，如果椭圆几乎是圆形（例如E2<0.1），那么五次迭代就可以使x、y在a*1e-12以内，但如果椭圆非常扁平，例如E2=0.999，则需要约300次迭代才能获得相同的精度！
最后，给定纬度，可以通过计算（x，y）来计算高度： x = nucos(lat)，y = nu(1-E2)*sin(lat) 然后h是从x，y到圆心的距离， h = hypot(X-x，Y-y)
- dmuir
1
这并不难。user168715的答案基本上是正确的，但是做微积分并不是必要的。只需要用三角函数。
找到两个物体中心之间的角度。使用这个角度，你可以使用极坐标形式找到椭圆上距离圆心最近的点：
（摘自维基百科关于椭圆的文章）
现在比较两个物体中心之间的距离，减去椭圆半径和圆半径。
也许我漏了什么；也许ArcTan/Cos/Sin很慢——但我不这么认为，而且如果需要的话应该有快速逼近方法。
- phillipwei
2
1谢谢，这比其他答案都更有帮助！而且实现起来非常容易。这也使得非旋转椭圆-椭圆碰撞检测变得容易，只需要将两个椭圆都转换为圆形即可。 - dreta
4我认为你不能使用中心之间的角度来计算距离。例如，两个重叠的对象，但你计算出的距离将是正数：http://imgur.com/FOE9ZkW - Jaxan
1
我希望为涉及两个椭圆之间的联系的更一般问题提供一些输入。计算两个椭圆最接近距离是一个长期存在的问题，只有在过去十年内才得到解决，这绝不是简单的。该问题的解决方案可以在此处找到http://www.e-lc.org/docs/2007_01_17_00_46_52/。
确定两个椭圆是否有接触的一般方法是首先计算它们当前配置下的最接近距离，然后从它们当前的分离大小中减去这个距离。如果结果小于或等于0，则它们是有接触的。
如果有人感兴趣，我可以发布计算最接近距离的代码--它是用C++编写的。该代码适用于任意两个椭圆的一般情况，但你显然也可以将其用于圆和椭圆，因为圆是具有相等短轴和长轴的椭圆。
确定两个椭圆是否有接触的一般方法是首先计算它们当前配置下的最接近距离，然后从它们当前的分离大小中减去这个距离。如果结果小于或等于0，则它们是有接触的。
如果有人感兴趣，我可以发布计算最接近距离的代码--它是用C++编写的。该代码适用于任意两个椭圆的一般情况，但你显然也可以将其用于圆和椭圆，因为圆是具有相等短轴和长轴的椭圆。
- Fred Minkowski
1
由于医生不在，如果你能的话，请分享代码。谢谢！ - undefined
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接