我想提高碰撞系统。

现在我发现，如果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边形对于某个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 ：使用椭圆的参数化。变换的坐标，使所述椭圆位于原点，以其轴对齐于xy轴。那就是：

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轴对准半径：一个 在椭圆的y轴对准半径：B

椭圆的方程，然后通过给予COS（T），B罪（T）。要找到最近的点，我们要尽量减少平方距离 || （CoS的T，B罪T） - ç|| ^ 2 。正如吉恩指出，这只是微积分：取一个衍生，并将其设置为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 缺点：你必须能够写出椭圆的参数化，或者改变你的坐标，​​以便您可以。这应该不是太难的任何合理的再presentation你有椭圆形的。但是，我要告诉你一个第二个方法，这是更为普遍，可能是，如果你有来概括您的问题，比方说，3D有用的。

办法2 ：使用多维积分。坐标没有变化是必要的。

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

圆的中心：C =（CX，CY） 在半径cirlce的，R 椭圆是由克（X，Y）= 0为一个函数g给出。例如，每豆腐的答案，你可能会从重点2用G（X，Y）=距离（X，Y）为重点1 +距离（X，Y） - 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是克的梯度。这是三个（非线性）方程在三个未知数的系统：X，Y，和拉姆达。我们可以解决使用牛顿法这个系统中，和（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）更容易 精读：需要一个多变量牛顿解决了，这是非常毛茸茸的，如果你没有获得一个数值方法包

警告：这两种方法在技术上解决的量的 extremizes 的点到圆的中心的距离。因此，找到的点可能是从圆的最远点，而不是最近的一刻。对于这两种方法，播种你的解决具有良好的初始猜测（圆的中心，非常适用于方法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.

潜在的第三条道路：它可能会直接解决了两个二次方程系统的两个变量的根重presenting圆和椭圆。如果一个真正的根存在，对象相交。解决这一系统，采用数值算法像牛顿的方法再次的最直接的方式，也无济于事，因为缺乏衔接并不一定意味着真正的根不存在。对于两个变量两个二次方程式，然而，有可能存在有保证找到实根，如果它们存在一个专门的方法。我自己想不出这样做的方式，但你可能要自己研究它（或者看看是否有人在计算器可以详细说明。）

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.)