軌跡與同一區域的圓之間的交集

我是編碼方面的新手。現在我有一個問題。我有一個物體繼續在矩形區域移動。我在這方面也有很多圈子。我想獲得軌跡和所有圓的所有交點。當對象正在一步一步地移動時，我也可以計算出對象的位置與每個圓的所有中心之間的距離，並將該距離與圓的半徑進行比較。但是我認爲這會做很多計算，因爲你需要計算每一步的距離。你有什麼好主意或參考。順便說一下，我在python上開玩笑。謝謝。由於我沒有足夠的信譽，因此我無法添加有關此問題的圖片軌跡與同一區域的圓之間的交集

來源

2015-04-01 SoonSYJ

讓a是一個介於大圓的半徑和直徑之間的數字（如果它們具有不同的半徑）。

生成邊長爲a的正方形瓷磚的網格，以便grid(i,k)爲從(i*a,k*a)到((i+1)*a, (k+1)*a)的正方形。

網格的每個圖塊都包含一個列表，其中包含指向圓形數組中的圓或索引的列表。

對於每個圓圈，將其註冊到與其相交的每個圖塊。應小於4

我們測試軌跡圓的交點RESP點(x,y)。包含在相應的磁盤內，您只需要對照((int)(x/a), (int)(y/a)中的圓圈列表進行測試。

來源

2015-04-01 10:36:59 LutzL

除非您的軌跡已經是直線，否則您可能需要計算其分段線性逼近。然後對於每個分段，您可以使用二次方程式計算line-circle intersections，並檢查交點是否是實數（而不是複數，如果該線通過圓並且平方根下的項變爲負數）以及它們是否在段（而不是終點之外的部分）。

假設你有一個從（X1，Y1）至（X2，Y2）線段，並希望相交，與在中心圓（XC，YC）與半徑r。然後，你要解決的方程

((1 - t)*x1 + t*x2 - xc)² + ((1 - t)*y1 + t*y2 - yc)² = r²

如果你的基礎上噸您會收到以下二次方程在噸力量收集條款：

     ((x1 - x2)² + (y1 - y2)²)*t² 
+ 2*((x1 - x2)*(xc - x1) + (y1 - y2)*(yc - y1))*t 
+    ((xc - x1)² + (yc - y1)² - r²) = 0

所以你可以在寫這篇文章Python代碼如下（未經測試）：

def circleSegmentIntersections(x1, y1, x2, y2, xc, yc, r): 
    dx = x1 - x2 
    dy = y1 - y2 
    rx = xc - x1 
    ry = yc - y1 
    a = dx*dx + dy*dy 
    b = dx*rx + dy*ry 
    c = rx*rx + ry*ry - r*r 
    # Now solve a*t^2 + 2*b*t + c = 0 
    d = b*b - a*c 
    if d < 0.: 
     # no real intersection 
     return 
    s = math.sqrt(d) 
    t1 = (- b - s)/a 
    t2 = (- b + s)/a 
    if t1 >= 0. and t1 <= 1. 
     yield ((1 - t1)*x1 + t*x2, (1 - t1)*y1 + t*y2) 
    if t2 >= 0. and t2 <= 1. 
     yield ((1 - t2)*x1 + t*x2, (1 - t2)*y1 + t*y2)

如果您的軌跡是彎曲的，但有一些不錯的數學描述，如自由落體拋物線或貝塞爾曲線或類似的東西，那麼你可以避免分段線性逼近，並嘗試直接計算交點。但有可能這樣做會導致找到某些高階多項式的根，這隻能用數字來完成。

來源

2015-04-01 08:01:24 MvG

一個人應該首先測試一下'r + sqrt（dx * dx + dy * dy） LutzL 2015-04-01 09:28:56

@LutzL：計算平方根可能是一個昂貴的操作，所以我不確定這樣的額外測試會有用。但是，一如往常，關於表現的決定，只是在現實生活場景中嘗試並衡量效果比理論上爭論要好。這可能是值得的。 – MvG 2015-04-01 10:05:32

精算，我沒有線段。我的軌跡是每個點的位置設置的一個點。 – SoonSYJ 2015-04-01 10:13:49

一般來說，我會建議先讓你的算法工作，然後讓它更快，如果你需要。您會驚訝於Python與一系列精心挑選的庫的結合速度有多快。

因此，對於你的問題，我會做到以下幾點：

1）安裝一組庫，讓您的生活更輕鬆： - Matplotlib爲矩形，圓形和軌跡的2D繪圖

2.）numpy的通用陣列處理

3。）任選地SciPy的其KDTree支持（最近鄰搜索）

4.）開始執行你的問題 a。）創建一個矩形，並使用Matplotlib

b可視化它。）創建組圓和4a

C的矩形區域內的繪製它們。）創建的軌跡和矩形區域內的繪製出來

現在更困難的部分開始。前進的方向取決於你的軌跡是如何定義的。例如，如果您的軌跡由線段組成，則可以分析計算圓和線段之間的交點。存在三種可能的解決方案，不存在交集，1個交集（線接觸圓）和2個交集。如果你的軌跡更復雜，你可以通過沿軌跡生成許多點來離散它，並計算這個點是否位於其中一個圓的邊上。儘管關於如何識別3種可能的解決方案，你必須有一點聰明，因爲沿着軌跡的點是有限的。

另一種選擇是也離散圓的邊緣上的點。這意味着問題會減少很大一部分到您可以使用Scipy KDTree類的最近鄰居搜索。

來源

2015-04-01 08:04:25

我有關於這個問題的所有事情。但我不能張貼關於這個問題的圖片，因爲我沒有足夠的聲望。但我認爲你對KDTree的建議很有幫助。我會看看它。 – SoonSYJ 2015-04-01 10:16:09

軌跡與同一區域的圓之間的交集

回答

相關問題