用於2d範圍計數查詢的python中的數據結構

我需要一個數據結構來完成2d範圍計數查詢（即給定矩形中有多少個點）。用於2d範圍計數查詢的python中的數據結構

我認爲我最好的選擇是範圍樹（它可以在log^2中計數，甚至可以在優化之後記錄）。這聽起來像是一個不錯的選擇嗎？有人知道一個python實現嗎？或者我需要自己寫一個嗎？

來源

2010-06-17 Dani

參見scipy.spatial.KDTree一個實現。

還有一個使用shapelib的四叉樹的通用性較低（但偶爾更有用，尤其是考慮到您的想法）。見this blog和相應的package in PyPi。

可能有其他實現，太多，但這些都是我用兩個...

來源

2010-06-17 00:23:48

因爲我覺得kdtree我沒有使用它是O（開方（N））。我在談論一個不同的數據結構（範圍樹），它是O（log^2（n））。然而，看起來他們對多個查詢使用了非常酷的優化，文章（http://www.cs.cmu.edu/~agray/nips-final.ps）提到了我正在嘗試做的事情作爲該方法的應用（快核密度估計）。所以我會試一試。謝謝！ – Dani 2010-06-17 15:37:47

用於2d範圍計數查詢的python中的數據結構

回答

相關問題