在numpy循環測試中的快速點

我有大量的(x,y)網格點與整數座標，我想測試它們是否在半徑和中心給出的圓圈數很少。點是圖像中的一些標記部分，這意味着有少量不規則形狀的塊包含點。在那裏我想檢查碰撞並計算一個圓圈內的點數。我目前的方法很慢（使用python和numpy）。在numpy循環測試中的快速點

現在我有兩個任務：

測試，如果集合A的任何點在任何圈子
計數這是在一個圈集B，點的數量

我目前的實施看起來像這樣（setA和setB是Nx2 numpy陣列和center是1x2陣列。）：

1）對於每個圓創建的point - center陣列，按元素將其平方和取總和，然後判斷是否小於radius**2

for circle in circles: 
    if (((setA - circle.center)**2).sum(axis=1) < circle.radius**2).any(): 
     return "collision" 
return "no collision"

這可以通過使用一個Python環和斷裂在所述第一碰撞被優化，但通常numpy循環比python循環要快得多，實際上兩個版本都比預期的要慢。

2）爲每個圓創建一個距離數組，並做一個元素小於半徑測試。將所有數組相加並計算結果的非零元素。

pixels = sp.zeros(len(setB)) 
for circle in circles: 
    pixels += (((setB - circle.center)**2).sum(axis=1) < circle.radius**2) 
return np.count_nonzero(pixels)

有沒有簡單的選項，以加速比呢？

我不想過度優化（並使程序更加複雜），但只是爲了以最有效的方式使用numpy，儘可能多地使用numpy向量化。因此，構建最完美的空間樹或類似物並不是我的目標，但我認爲一個O（n^2）算法對於幾千個點和10-20個圓應該是可能的平均速度最快臺式電腦今天。

來源

2017-02-19 allo

似乎非常相關 - ['Python的矢量化嵌套的loops'（http://stackoverflow.com/questions/39667089/）。 – Divakar

你在這裏關注的所有點都是像素嗎？更具體地說，某些點的座標是否只是整數網格索引？ –

是的，它們是圖像中的整數座標。 – allo

趁着座標是整數：

創建查找圖像

radius = max([circle.radius for circle in circles]) 
mask = np.zeros((image.shape[0] + 2*radius, image.shape[1] + 2*radius), dtype=int) 
for circle in circles: 
    center = circle.center + radius 
    mask[center[0]-circle.radius:center[0]+circle.radius + 1, 
     center[1]-circle.radius:center[1]+circle.radius + 1] += circle.mask

circle.mask是包含內部點的光盤的一個掩模

計數碰撞現在是作爲一個小的方形貼片就像

mask[radius:-radius, radius:-radius][setB[:,0], setB[:,1]].sum()

快速創建光盤（沒有乘法，沒有平方根）：

r = circle.radius 
h2 = np.r_[0, np.add.accumulate(np.arange(1, 2*r+1, 2))] 
w = np.searchsorted(h2[-1] - h2[::-1], h2) 
q = np.zeros(((r+1), (r+1)), dtype=int) 
q[np.arange(r+1), w[::-1]] = 1 
q[1:, 0] -= 1 
q = np.add.accumulate(q.ravel()).reshape(r+1, r+1) 
h = np.c_[q, q[:, -2::-1]] 
circle.mask = np.r_[h, h[-2::-1]]

來源

2017-02-19 20:03:19

我沒有看到，爲什麼這應該比我目前的解決方案更快。我認爲它使用了類似的numpy操作，並且在圓圈比像素數量小得多時具有優勢。但其餘的與面具創作非常相似。 – allo

@allo是的，你是對的，它取決於數字。你的是O（#circles x #setB）我的是O（#circles + #setB）我冒昧地假設恆定的最大半徑和圖像大小。（如果圓圈是固定的，你可以預先計算掩碼，查找我認爲是儘可能快的。） –

是的，我認爲查找新點或具有相同半徑的新圓圈不能比你的方法快。我會研究它，但我有固定點和不同半徑的圓。這可能會有所幫助，因爲#circles << #points，但可能經常#points（圓圈）大於#points。 – allo

在numpy循環測試中的快速點

回答

相關問題