我是編碼方面的新手。現在我有一個問題。我有一個物體繼續在矩形區域移動。我在這方面也有很多圈子。我想獲得軌跡和所有圓的所有交點。當對象正在一步一步地移動時,我也可以計算出對象的位置與每個圓的所有中心之間的距離,並將該距離與圓的半徑進行比較。但是我認爲這會做很多計算,因爲你需要計算每一步的距離。你有什麼好主意或參考。順便說一下,我在python上開玩笑。謝謝。由於我沒有足夠的信譽,因此我無法添加有關此問題的圖片軌跡與同一區域的圓之間的交集
回答
讓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)
中的圓圈列表進行測試。
除非您的軌跡已經是直線,否則您可能需要計算其分段線性逼近。然後對於每個分段,您可以使用二次方程式計算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)
如果您的軌跡是彎曲的,但有一些不錯的數學描述,如自由落體拋物線或貝塞爾曲線或類似的東西,那麼你可以避免分段線性逼近,並嘗試直接計算交點。但有可能這樣做會導致找到某些高階多項式的根,這隻能用數字來完成。
一般來說,我會建議先讓你的算法工作,然後讓它更快,如果你需要。您會驚訝於Python與一系列精心挑選的庫的結合速度有多快。
因此,對於你的問題,我會做到以下幾點:
1)安裝一組庫,讓您的生活更輕鬆: - Matplotlib爲矩形,圓形和 軌跡的2D繪圖
2.)numpy的通用陣列處理
3。)任選地SciPy的其KDTree支持(最近鄰搜索)
4.)開始執行你的問題 a。)創建一個矩形,並使用Matplotlib
b可視化它。)創建組圓和4a
C的矩形區域內的繪製它們。)創建的軌跡和矩形區域內的繪製出來
現在更困難的部分開始。前進的方向取決於你的軌跡是如何定義的。例如,如果您的軌跡由線段組成,則可以分析計算圓和線段之間的交點。存在三種可能的解決方案,不存在交集,1個交集(線接觸圓)和2個交集。如果你的軌跡更復雜,你可以通過沿軌跡生成許多點來離散它,並計算這個點是否位於其中一個圓的邊上。儘管關於如何識別3種可能的解決方案,你必須有一點聰明,因爲沿着軌跡的點是有限的。
另一種選擇是也離散圓的邊緣上的點。這意味着問題會減少很大一部分到您可以使用Scipy KDTree類的最近鄰居搜索。
我有關於這個問題的所有事情。但我不能張貼關於這個問題的圖片,因爲我沒有足夠的聲望。但我認爲你對KDTree的建議很有幫助。我會看看它。 – SoonSYJ 2015-04-01 10:16:09
- 1. 查找交點基於區域的軌跡與線軌跡
- 2. 圓形曲線之間的區域
- 3. 什麼算法用於查找多邊形和圓之間的交集區域?
- 4. libgdx中的矩形和圓形扇區之間的交集
- 5. 在Canvas中標記兩個圓圈之間的相交區域
- 6. 兩個橢圓(橢圓)的交集區域?
- 7. OpenLayers 3,幾何圖形之間的區域交集
- 8. 導軌之間的區別與差異
- 9. Python中的區域交集
- 10. 軌連接兩個表之間的查詢與同類領域
- 11. 散點圖與軌跡跨數據集
- 12. 在圓圈內繪製文本的交集區域
- 13. 根據信號強度查找位置(圓圈之間的交叉區域)
- 14. 兩個圓形扇區的交集
- 15. 計劃之間的交集之間的交集
- 16. ListBox.DataSource集合與ListBox.Items之間的區別?
- 17. 圓形軌跡在畫布上淡出
- 18. 區域之間的RedirectToAction?
- 19. 找到一個圓和一組多邊形之間的重疊區域
- 20. 計算軸未對齊的兩個矩形之間的交集區域
- 21. 在R中繪製地圖(軌跡值落在特定區域之外)
- 22. 查找同一表的多個clolumns之間的交集
- 23. 在同一區域的視圖之間切換棱鏡
- 24. wpf4,prim4在同一區域中的視圖之間切換
- 25. DIV原樣與帶顯示的SPAN之間的區別:區域
- 26. 類區域和堆之間的區別
- 27. NSFetchRequest與變化軌跡不一致
- 28. 刪除.widget區域,.comment區域和.main-navigation之間的空間。
- 29. 與軌跡網格碰撞
- 30. 繪圖軌跡與VBA
一個人應該首先測試一下'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