如何有效地分割單元格中的2D空間，使每個單元格至多包含K個點？

我有一個2D點的數據集（〜500k），我想在其上進行某種樣方數分析。樣方計數的基礎是將您的二維空間分成一個規則的網格（每個單元格的大小爲SxS）並計算每個單元格中的點數。如何有效地分割單元格中的2D空間，使每個單元格至多包含K個點？

出於某種原因，我想這樣做的一個微小的變化：而不是使用常規的網格，我想建立網格，使得每個單元包含最多K點。

我做了以下幾點：我從整個空間開始，將它分成4個單元格（通過將每個維度「切割」成一半）。然後，我計算每個單元格中的點數。對於那些包含K以上的點，我再將它們分開等等，直到完成。

我嘗試了這個簡單算法的遞歸和迭代實現，但是當應用於整個數據集時，沒有一個性能很好。主要的瓶頸是計數部分，顯然，所以我想知道什麼樣的數據結構可以讓我有效地做到這一點？

（現在，我只是用在Python「有條件索引」：points = points[points[,1] > x1 and points[,1] <= x2 and points[,2] > y1 and points[,2] <= y2,]）

另外，你對我怎麼能建立我的網格，也許另一個想法？

編輯：換句話說，可以使用什麼樣的數據結構來快速計算（並檢索）屬於給定矩形的點？((x1, y1), (x2, y2))？

來源

2011-03-30 Wookai

這並不完整，但它可能會指向正確的方向。

而不是開始大而小，開始小而大。

將您的空間劃分爲100x100個單元格。計算每個單元格中的數字（這正好是O（n），您將對每個單元格計數一次）。

從那裏開始，您不需要對單元格進行計數。您可以創建CellGroups來計算它具有的單元格，並從那裏使用算法將單元格合併到CellGroups中。

您可能會考慮採用兩個小單元將其合併並重新計算的方法。

while(true) { 
    take the smallest cellgroup 
    compare it to each other cellgroup starting with the second smallest 
    go up the list until you find two adjecent cell groups 
    if you find a match 
     merge them 
     update the cellgroup size rankings 
     repeat the process (continue the while(true) 
    otherwise 
     break out, you're done merging cells 

}

來源

2011-03-30 19:40:45 corsiKa

那麼，結果會不一樣。使用大到小的技術，我將最終獲得數據很少或沒有數據點的單元（因爲如果點非常聚集，大單元的第一個「切割」將最終只有一個包含所有單元的「子單元」分，其他三個都沒有）。另一方面，您所描述的從小到大的方法會將所有空單元與鄰居合併。換句話說，它將給出最小數量的單元格，使得每個單元格至多有K個點。 – Wookai 2011-03-30 20:30:37

儘管如此，我並不是說一種方法比另一種更好。只是他們不一樣。我不確定你的感覺是不是我想要做的事情（我將不得不考慮它）。 – Wookai 2011-03-30 20:31:43

但是，您會繼續合併單元格，直到達到無法進一步合併單元格的狀態。它可能不是最理想的狀態（即可能以不同的方式分裂細胞，產生更少的最終細胞羣），但它應該是相當體面的方法。 – corsiKa 2011-03-30 20:33:08

我不使用Python不夠熟悉，但如果你通過每個象限整個陣列上運行，它可以改善：根據每個象限分裂組點

後，他們對應。當進一步分裂一個象限時只分析相應的子陣列。這可能會加快計數。另外，由於您對不規則網格還可以，因此您可以考慮選擇分隔線，始終將平分點放入相同的組（水平和垂直分離應該分開進行）。

來源

2011-03-30 20:07:15 maxim1000

是的，我試過了，這有助於（在遞歸情況下）。但問題是，隨着遞歸，我達到了Python的最大遞歸深度...... – Wookai 2011-03-30 20:42:30

關於劃分成單獨組的最後一個想法可能會限制遞歸到日誌（點數）。你也可以切換到自己的堆棧... – maxim1000 2011-03-31 18:18:08

如何有效地分割單元格中的2D空間，使每個單元格至多包含K個點？

回答

相關問題