算法來檢測靜止的圓形列表是否與另一個圓弧從起點到終點沿同一平面上的直線相交

Question

我有一個圓形（我的遊戲中的Striker），它沿着我的2D平面從一點移動到另一點沿着一條直線。我在同一架飛機上還有其他一些圈子沒有移動。尋找在運動過程中與運動圓相交的圓圈列表的最佳算法是什麼？如果我想在python中編寫這個代碼，最好的辦法是什麼（內存效率，因爲我想爲許多不同的狀態執行此操作來解決我的問題）？什麼是用於此目的的最佳圖書館？

Answer 1

你問了一個算法，而不是代碼，所以這是主意。您可能需要使用math模塊，但如果您知道基本的美國11年級分析幾何，則不需要其他任何東西。

固定圓可以通過兩種方式與您的移動圓相交：它可以與路徑開始或結束處的移動圓相交（紅色圓圈集中在下圖中的A和B），或者它可以與由移動圓形成的矩形（圖中標記爲EGHF的藍色矩形）相交。

與端圈檢查相交很簡單：圓相交如果它們的中心之間的距離不小於其半徑之和更大。

檢查矩形的交點有點困難。如果滿足兩個要求，則I處的圓與矩形EGHF相交。首先，中心I必須在構成矩形末端的GH和EF線之間。其次，從I到AB線的距離（包圍動圈中心的路徑的線）必須不大於I處靜止圓的半徑和動圈的半徑之和。

檢查與矩形交點的交替，更一致的方法是檢查從靜止圓的中心到運動圓的起點和終點的垂直平分線（品紅色線標記爲p）的距離，它必須至少是A點和B點之間距離的一半，AB線的距離必須至多是移動和固定圓的半徑之和。

所有這些計算（兩點之間的距離，諸如GH，EF，AB和垂直平分線之類的線的方程，查看點是否在兩條平行線之間，以及點與線之間的距離）在分析幾何中是標準的。這些計算中的大部分僅取決於運動圓 - 每個靜止圓的計算很少且很快。讓我知道你是否需要這些公式的幫助。這樣的公式可能有一個模塊，但我不知道其中的一個。

---

涉及該方法中的存儲器是最小的，假設半徑和起點和終點中心移動圓，以及半徑和中心座標的靜止圈的座標是已經在存儲器中。如果您選擇我的替代方法，則可以通過預先計算移動圓的某些值來節省執行時間。如果圓的圓心開始座標是（X1，Y1）和終點座標是（x2，y2），你會預先計算：

dx = x2 - x1 
dy = y2 - y1 
d = math.hypot(dx, dy) 
det = x2 * y1 - x1 * y2 
c = (x1 * x1 + y1 * y1 - x2 * x2 - y2 * y2)/2 

（注意這五個值存儲只有一次，對於）然後，對於每個靜止圓，找出從該圓的中心到垂直平分線（我的圖中的p）的有符號距離，然後使用該距離查找到起始圓，結束圓或移動線的距離。如果您有很多固定圓圈，並且與運動場相比運動圓圈的路徑很小，則可以使用路徑的邊界矩形快速消除大部分靜止圓圈。