如何检测椭圆是否与圆相交(碰撞) [英] How to detect if an ellipse intersects(collides with) a circle

问题描述

我想改进碰撞系统.

现在我检测到 2 个不规则对象是否发生碰撞，如果它们的边界矩形发生碰撞.

Right now I detect if 2 irregular objects collide if their bounding rectangles collide.

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

I want to obtain the for rectangle the corresponding ellipse while for the other one to use a circle. I found a method to obtain the ellipse coordinates but I have a problem when I try to detect if it intersects the circle.

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

Do you know a algorithm to test if a circle intersects an ellipse?

推荐答案

简答:精确求解两个对象是否相交非常复杂，无法实现碰撞检测.将您的椭圆离散化为一个 n 边多边形(取决于您需要的精确度)，并使用该多边形进行碰撞检测.

Short answer: Solving exactly for whether the two objects intersect is complicated enough to be infeasible for the purpose of collision detection. Discretize your ellipse as an n-sided polygon for some n (depending on how accurate you need to be) and do collision detection with that polygon.

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

Long answer: If you insist on determining if the smooth ellipse and circle intersect, there are two main approaches. Both involve solving first for the closest point to the circle's center on the ellipse, and then comparing that distance to the circle's radius.

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

Approach 1: Use a parametrization of the ellipse. Transform your coordinates so that the ellipse is at the origin, with its axes aligned to the x-y axes. That is:

• 椭圆中心:(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 插入参数方程以获得最近点.

The equation of the ellipse is then given by a cos(t), b sin(t). To find the closest point, we want to minimize the square distance || (a cos t, b sin t) - c ||^2. As Jean points out, this is "just calculus": take a derivative, and set it equal to 0. Unless I'm missing something, though, solving the resulting (quite nasty) equation for t is not possible analytically, and must be approximated using e.g. Newton's Method. Plug in the t you find into the parametric equation to get the closest point.

• 专业:数值求解仅在一个变量中，t.
• Con:您必须能够写下椭圆的参数化，或转换您的坐标，这样才能做到.对于您对椭圆的任何合理表示，这应该不会太难.不过，我将向您展示第二种方法，该方法更为通用，如果您必须将问题概括为 3D 等情况，它可能会很有用.

方法 2:使用多维微积分.无需更改坐标.

Approach 2: Use multidimensional calculus. No change of coordinates is necessary.

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

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

Finding the point on the ellipse closest to the center of the circle can then be phrased as a constrained minimization problem:

最小化 ||(x,y) - c||^2 服从 g(x,y) = 0

(最小化平方距离相当于最小化距离，而且处理起来更愉快，因为它是 x,y 的二次多项式.)

(Minimizing the square distance is equivalent to minimizing the distance, and much more pleasant to deal with since it's a quadratic polynomial in x,y.)

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

To solve the constrained minimization problem, we introduce Lagrange multiplier lambda, and solve the system of equations

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

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

Here Jg is the gradient of g. This is a system of three (nonlinear) equations in three unknowns: x, y, and lambda. We can solve this system using Newton's Method, and the (x,y) we get is the closest point to the circle's center.

• 专业人士:无需找到参数化
• 优点:方法非常通用，只要写 g 比找到参数方程(例如在 3D 中)更容易，它就可以很好地工作
• 缺点:需要多变量牛顿求解，如果您无法访问数值方法包，这将非常麻烦.

注意事项:这两种方法都在技术上解决了 使 距离圆心的距离极值的点.因此，找到的点可能是离圆最远的点，而不是最近的点.对于这两种方法，用一个好的初始猜测来解决你的问题(圆的中心对于方法 2 很有效；对于方法 1，你靠自己)会减少这种危险.

Caveat: both of these approaches technically solve for the point which extremizes the distance to the circle's center. Thus the point found might be the furthest point from the circle, and not the closest. For both methods, seeding your solve with a good initial guess (the center of the circle works well for Method 2; you're on your own for Method 1) will reduce this danger.

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

Potential Third Approach?: It may be possible to directly solve for the roots of the system of two quadratic equations in two variables representing the circle and ellipse. If a real root exists, the objects intersect. The most direct way of solving this system, again using a numerical algorithm like Newton's Method, won't help because lack of convergence does not necessary imply nonexistence of a real root. For two quadratic equations in two variables, however, there may exist a specialized method that's guaranteed to find real roots, if they exist. I myself can't think of a way of doing this, but you may want to research it yourself (or see if someone on stackoverflow can elaborate.)

这篇关于如何检测椭圆是否与圆相交(碰撞)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！