如何檢測橢圓與圓相交（碰撞）

Question

我想改善碰撞系統。

現在我檢測到2個不規則物體是否碰撞邊界矩形時發生碰撞。

我想獲取矩形的相應橢圓，而另一個使用圓。我找到了一種獲得橢圓座標的方法，但是當我嘗試檢測它是否與圓相交時，我遇到了一個問題。

你知道一個算法來測試一個圓與橢圓相交嗎？

Answer 1

簡短回答：準確解決兩個物體相交是否足夠複雜以至於碰撞檢測的目的不可行。將橢圓分解爲n邊的n邊多邊形（取決於您需要的準確度），並使用該多邊形進行碰撞檢測。

長答案：如果你堅持要確定光滑的橢圓和圓是否相交，有兩種主要方法。兩者都首先求解橢圓上最接近圓的中心點，然後將該距離與圓的半徑進行比較。

方法1：使用橢圓的參數化。轉換座標，使橢圓位於原點，其軸與x-y軸對齊。那就是：

• 中心橢圓的：（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以獲得最近點。

• 專業：數值解決只在一個變量，t。答：你必須能夠寫下橢圓的參數化，或者變換你的座標以便你可以。對於橢圓的任何合理表示，這不應該太難。但是，我將向您展示第二種方法，如果您必須將問題概括爲3D，則該方法更爲一般化，並且可能有用。

方法2：使用多維演算。不需要改變座標。

• 圓的中心：C =（CX，CY）
• 半徑cirlce如下：R
• 橢圓由g（x，y）= 0的函數g給出。例如，根據Curd的答案，你可以使用g（x，y）=焦點1的距離（x，y）+焦點2的距離（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）是最接近圓心的點。

• 臨：沒有參數化需要找到
• 臨：方法很一般，而且效果很好，只要寫g是比找一個參數方程（如3D）
• 精讀更容易：需要多變量牛頓解決方案，如果您無法訪問數值方法包，則這非常多毛。

警告：這兩種方法在技術上解決這extremizes到圓的圓心的距離的點。因此，發現的點可能是離圓圈最遠的點，而不是最接近的點。對於這兩種方法，用一個好的初始猜測（圓的中心適用於方法2;對於方法1來說你自己的方法）可以減少這種危險。

潛在的第三種方法？：有可能直接求解兩個二次方程系統的根在兩個變量代表圓和橢圓。如果存在真實的根，則這些對象相交。解決這個系統的最直接的方法，再次使用像牛頓法那樣的數值算法，將不會有幫助，因爲缺乏收斂並不意味着不存在真正的根。然而，對於兩個變量中的兩個二次方程，可能存在保證找到真正根的專門方法（如果存在的話）。我自己無法想到這樣做，但你可能想自己研究它（或看看有人在stackoverflow可以詳細說明。）

Answer 2

找到橢圓最接近的點到圓
的中心，然後檢查是否從該點的距離比圓的半徑小
，如果你需要幫助，這樣做只是發表評論，但它只是結石

編輯：這裏是朝着解決方案的方式，因爲有什麼不對的凝乳

給出中心αβ的橢圓
和（缺乏記住的術語）X半徑，Y （θ）=α+ sin（θ）r（Θ）=（ab）/（（Bcosθ）^ 2 +（asinΘ）^ 2） Θ）
Y（Θ）=β+ COS（Θ）R（Θ）

，然後只取與中心的圓在（φ，ψ）和半徑r 然後距離d（Θ）=（其中d'（θ）= 0（'爲導數）時，該距離的最小值爲

（φ-x（θ））^ 2 +（ψ-y（θ））^ 2）

d '（Θ）= 1/d（Θ）*（-φx'（Θ）+ X（Θ）X '（Θ） - ΨY'（ ）+ y（Θ）y'（Θ））
==>
x'（Θ）*（-φ+ x（Θ））= y'（Θ）*（ψ-y（Θ））

，並保留通過Newton's Method

Answer 3

打算和準備，希望你能解決Θ
你工作中可能有事情來幫助你解決這個問題的框架，你總是可以採取簡單的出路和近似解

橢圓定義爲一組點，其距離點A的距離和到點B的距離的總和爲常數e。 （A和B被稱爲橢圓的焦點）。

總和AP + BP小於e的所有點P位於橢圓內。

的圓被定義爲一組，其 距離的點C爲r的點。

一個簡單的測試爲圓和橢圓的交點以下：

查找
數p作爲所述圓的交點與線AC和
Q作爲圓的交點與線BC。

圓和橢圓相交（或圓完全位於橢圓內）如果
AP + BP < = E  或  AQ + BQ < = E

EDIT：

經過Martin DeMello的評論並相應地調整了我的答案之後，我想到了更多關於該問題的信息，並發現答案（與第二次檢查）仍未檢測所有十字路口：

如果圓形和橢圓相交的只有極很少（僅比相切）P和Q多一點的橢圓內不會說謊：

因此，上述測試僅在重疊「足夠大」時才檢測碰撞。 也許它已經足夠滿足您的實際需要，儘管在數學上它並不完美。

Answer 4

如果一個圓和一個橢圓碰撞，那麼它們的邊界相交1,2,3或4次（或者在與該圓一致的圓形橢圓的情況下，其邊界相交無限多），或者圓在橢圓或反之亦然。我假定圓的方程爲（x - a）^ 2 +（y - b）^ 2 < = r^2（1）並且橢圓的方程爲[（x - c）^2]/[d^2] + [（y - e）^ 2]/[f^2] < = 1（2）

要檢查其中一個是否在另一個內，在橢圓的中心的座標的圓的方程（X = C，Y = e）中，或反之亦然，並且看到如果不等式成立。

，以檢查那些它們的邊界交叉的其他情況下，你必須檢查由（1）中描述的方程系統，以及是否（2）具有任何解決方案。

您可以通過添加（1）和（2），讓您

(x - a)^2 + (y - b)^2 + [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] = r^2 + 1

下次繁衍出來的條款做到這一點，讓

x^2 - 2ax + a^2 + y^2 - 2by + b^2 + x^2/d^2 - 2cx/d^2 + c^2/d^2 + y^2/f^2 - 2ey/f^2 + e^2/f^2 = r^2 + 1

收集同類項，我們得到

(1 + 1/d^2)x^2 - (2a + 2c/d^2)x + (1 + 1/f^2)y^2 - (2b + 2e/f^2)y = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

現在就讓m = (1 + 1/d^2), n = -(2a + 2c/d^2), o = (1 + 1/f^2), and p = -(2b + 2e/f^2)

現在的方程是mx^2 + nx + oy^2 + py = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

現在我們需要完成對左側的方形

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 

這個系統有一個解決方案iff 11 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 >= 0

有你有它，如果我沒有犯任何代數錯誤。我不知道有多少可以簡化所得的表達，所以如果你要檢查很多圓圈/橢圓

Answer 5

忘掉一個數學的解決了這個解決方案可能是相當耗費計算。正如您可以通過繪圖很容易看到的那樣，最多可以有四個解，因此可能是四階多項式。

，而不是僅僅做沿的人物之一邊緣的二進制搜索。很容易確定一個點是否位於橢圓內，甚至更確定一個圓（如果距離比半徑短）。

如果你真的想去數學，Wolfram MathWorld在這裏有一篇很好的文章：http://mathworld.wolfram.com/Circle-EllipseIntersection.html但是要注意，你仍然必須編寫一個多項式方程求解器，可能使用類似二進制搜索的東西。

Answer 6

假設： 橢圓是在原點和與沿x軸方向（長度A）半長軸 軸線爲中心，並與長度b的半短軸 軸; E2是偏心的平方，即（一個A-B B）/（A * A）; 圓圈以X，Y和半徑r爲中心。簡單的情況是： 圓心位於橢圓內（即hypot（X/a，Y/b）< = 1） 所以有一個交點; 圓心位於以半徑a + r （即hypot（X，Y）> a + r）0爲中心的圓的外部，所以不存在相交。

其他情況下的一種方法是計算圓心的座標（緯度，高度）的大地測量 。當且僅當高度小於半徑時，圓 與橢圓相交。

在橢圓上的點的測地緯度爲角度 的法線橢圓在點與x軸使得，和 橢圓之外的點的高度是從所述 點的距離指向最接近它的橢圓。注意大地緯度與從橢圓中心到點的極角不同，除非橢圓實際上是圓形的。

在式從大地座標緯度轉換，HT到 直角座標X，Y是 X =（ν+ 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 = ATAN2（Y + E2 * NU 罪（LAT），X） ，其可用於計算連續近似緯度， 開始在LAT = ATAN2（Y ，X（1.0-E2））或（更有效地）可以使用牛頓法解決。

E2越大，即橢圓越平坦，迭代所需的次數越多。例如，如果橢圓近似爲圓形（例如E2 < 0.1），則五次迭代將使得x，y在 以下在* 1e-12內，但是如果橢圓非常平坦，例如， E2 = 0.999 您需要大約300次迭代才能獲得相同的準確度！

最後，給定緯度，高度可以通過計算（X，Y）來計算 ： X = NU COS（LAT），Y = NU（1-E2）* SIN（LAT） 和那麼h是從x，y到圓心的距離， h = hypot（xx，yy）

Answer 7

這並不難。 user168715的回答總的來說是對的，但是做微積分並不是必須的。只是三角。

找到兩個物體中心之間的角度。利用這一點，你可以找到的最近點到圓的圓心上使用極形式橢圓：

（從Ellipses維基百科文章摘自）

現在比較兩個物體之間的距離中心，減去橢圓半徑和圓半徑。

也許我錯過了一些東西;也許ArcTan/Cos/Sin很慢 - 但我不這麼認爲，如果需要，應該有快速近似。

Answer 8

按圓的半徑放大橢圓的主半徑和副半徑。然後通過累計到擴大橢圓的焦點的距離來測試給定圓的中心是否在這個新的較大橢圓內。

該算法效率很高。如果給定的圓不與橢圓外接的圓相交，則可以提前退出。這比邊界框測試慢，但找到非軸對齊的橢圓的邊界框是棘手的。

Answer 9

我想提供一些輸入到涉及兩個省略號之間接觸的更一般問題。計算兩個橢圓最接近的方法的距離是一個長期存在的問題，並且只在過去的十年中以分析方式解決 - 這絕不是簡單的問題。解決問題的方法可以在這裏找到http://www.e-lc.org/docs/2007_01_17_00_46_52/。

確定兩個橢圓之間是否有接觸的一般方法是首先計算橢圓在它們當前配置中最接近的方法的距離，然後從它們當前的分離量中減去這個距離。如果這個結果小於或等於0，那麼他們就會聯繫起來。

如果有人有興趣，我可以發佈代碼來計算最接近的方法的距離 - 它是用C++編寫的。該代碼適用於兩個任意橢圓的一般情況，但您明顯可以對圓和橢圓執行該操作，因爲圓是具有相等小軸和長軸的橢圓。

Answer 10

我知道這太晚了，但我希望它能幫助別人。我解決這個問題的方法是將橢圓內插到一個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軸對齊半徑。

現在我們有了插值點，我們可以找到圓與每2點之間的線之間的交點。 找到線 - 交叉點交點的一種方法是here, 如果交點發生在任何線和圓之間，則發生交集。

希望這可以幫助任何人。