算法檢測軸對齊的矩形和定向的超橢圓之間的交集

Question

我正在編寫函數來測試矩形與超橢圓的交集。 矩形將始終是軸對齊的，而超橢圓可以以旋轉角度α定向。

在軸對齊的矩形與軸對齊的超橢圓相交的情況下，我寫了這兩個功能非常好的短函數。代碼簡潔，清晰，高效。如果可能的話，我想爲新的更一般的功能保持類似的結構。

這裏是我有，如果軸對齊的矩形相交軸對齊超橢圓檢測：

double fclamp(double x, double min, double max) 
{ 
    if (x <= min) return min; 
    if (x >= max) return max; 
    return x; 
} 

bool rect_intersects_superellipse(const t_rect *rect, double cx, double cy, double rx, double ry, double exponent) 
{ 
    t_pt closest; 
    closest.x = fclamp(cx, rect->x, rect->x + rect->width); 
    closest.y = fclamp(cy, rect->y, rect->y + rect->height); 
    return point_inside_superellipse(&closest, cx, cy, rx, ry, exponent); 
} 

bool point_inside_superellipse(const t_pt *pt, double cx, double cy, double rx, double ry, double exponent) 
{ 
    double dx = fabs(pt->x - cx); 
    double dy = fabs(pt->y - cy); 

    double dxp = pow(dx, exponent); 
    double dyp = pow(dy, exponent); 

    double rxp = pow(rx, exponent); 
    double ryp = pow(ry, exponent); 

    return (dxp * ryp + dyp * rxp) <= (rxp * ryp); 
} 

這工作正常，但 - 正如我所說的 - 只爲一個軸對齊超橢圓。

現在我想將它概括爲一個定向的超橢圓，使算法結構儘可能地接近上面。然後 的前兩個函數最明顯的擴大將成爲類似：

bool rect_intersects_oriented_superellipse(const t_rect *rect, double cx, double cy, double rx, double ry, double exponent, double radians) 
{ 
    t_pt closest; 
    closest.x = fclamp(cx, rect->x, rect->x + rect->width); 
    closest.y = fclamp(cy, rect->y, rect->y + rect->height); 
    return point_inside_oriented_superellipse(&closest, cx, cy, rx, ry, exponent, radians); 
} 

bool point_inside_oriented_superellipse(const t_pt *pt, double cx, double cy, double rx, double ry, double exponent, double radians) 
{ 
    double dx = pt->x - cx; 
    double dy = pt->y - cy; 

    if (radians) { 

     double c = cos(radians); 
     double s = sin(radians); 

     double new_x = dx * c - dy * s; 
     double new_y = dx * s + dy * c; 

     dx = new_x; 
     dy = new_y; 
    } 
    double dxp = pow(fabs(dx), exponent); 
    double dyp = pow(fabs(dy), exponent); 

    double rxp = pow(rx, exponent); 
    double ryp = pow(ry, exponent); 

    return (dxp * ryp + dyp * rxp) < (rxp * ryp); 
} 

用於面向超橢圓，上面並沒有正確地獨立工作達到預期效果，即使point_inside_oriented_superellipse()。我無法使用上述函數來測試與軸對齊的矩形的交點。我一直在線研究大約一週，我發現一些解決方案需要逆矩陣變換來均衡超橢圓軸並將其原點設置爲（0,0）。折衷是，現在我的矩形不再是矩形，並且當然不是軸對齊的。我想避免走這條路。 我的問題是展示如何使上述算法保持其結構或多或少不變。如果不可能保持相同的算法結構，請顯示最簡單，最有效的算法來測試軸對齊矩形和定向超橢圓之間的交集。我只需要知道交叉點是否發生（布爾結果）。 指數參數的範圍可以從0.25到100.0不等。

感謝您的任何幫助。

Answer 1

看看source中的第2點。簡單來說，你需要做以下檢查：

1.是否有橢圓任何矩形頂點？

2.是矩形邊緣相交的橢圓？

3是在矩形內橢圓的中心？

的橢圓形和矩形相交，其它如果上述任何可與是，所以，你的函數應該返回像這樣回答的問題：

return areVertexesInsideEllipse(/*params*/) || areRectangleEdgesIntersectingEllipse(/*params*/) || isEllipseCenterInsideRectangle(/*params*/); 

的文檔，甚至有這是一個相當接近你的實現的例子。

要檢查是否有任何頂點在橢圓內，可以根據橢圓的不等式計算它們的座標。要檢查邊緣是否與橢圓重疊，您需要檢查其線條是否通過橢圓或觸及橢圓。如果是這樣，您需要檢查線段通過橢圓或觸及它的線段是否與邊線定義的線段相交。要檢查橢圓的中心是否在矩形內，您需要檢查矩形的不平等中心。

請注意，這些都是非常一般的術語，它們甚至不假定您的矩形是面向軸的，而是獨立於您的橢圓。

Answer 2

首先，您應該使用分離軸定理排除明顯的不相交的情況 - 超橢圓有可能包含兩個邊界框（指數n> 1的情況）和n < = 1的情況。

在SAT中，邊界框ABCD中的所有頂點都與超橢圓的BB（abcd）中的所有（有向）邊相比較;反之亦然。如果到分隔軸的標記距離都是正值（即外部），則物體不會相互碰撞。

  b 
     a 
    A------B 
    |  |  d 
    |  | c 
    C------D 

指數n == 1進一步將案例 - Ñ< = 1使超橢圓凹的，在這種情況下僅ABCD相交ABCD，如果一個或多個點是超橢圓體的內部。 當n> 1時，必須求解AABB中的線段與超橢球的交點，可能必須用樣條或其他代理來近似。畢竟，實際的交點並不重要，但將方程式設置爲wolfram alpha並不能在標準執行時間內產生任何結果。