Javascript：通過兩個屬性搜索對象索引集

我在笛卡爾網格上有大量的點，由（x，y）指定的位置。我想快速搜索，返回位於x和y給定範圍內的一組點（對象）。（網格內的矩形）。

也許有一個輕量級框架可以做到這一點？

由於

2012-10-10 Jodes

點區域四叉樹？ –

我將存儲該點爲具有兩個屬性的對象：x和y，以及一個比較功能，這將它們排序，在一個屬性或其他，使用剩餘的屬性作爲領帶斷路器：

function Point(x, y){ 
    this.x = x; 
    this.y = y; 
    this.compareTo =function(otherPoint){ 
     if(otherPoint.x != this.x) 
      return this.x-otherPoint.x; 
     return this.y-otherPoint.y; 
    } 
} 

points[n] = new Point(someX, someY);

然後，您可以使用一個排序算法（例如快速排序 - 與O（N日誌（N）））對它們進行排序，並簡單插入排序，讓他們歸類爲點來來去去。當您需要使用矩形選擇時，可以簡單地在它們之間執行二進制搜索（O（log（n）））以找到第一個屬性的邊界（例如，x），然後再跨越該較小的集合到找到secont屬性的邊界（例如，y），剩下的設置將是您正在查找的設置，從而使您的搜索時間（O（4log（n））最差，並且您的插入時間。線性（最壞情況）太寒酸了，如果我不這樣說不是我自己

來源

2012-10-10 00:36:55 FrankieTheKneeMan

以下是一般問題的最優實現：

http://en.wikipedia.org/wiki/Interval_tree#Higher_dimension

How to search objects affecting a point in space

來源

2013-05-12 07:22:31 MetaChrome

Javascript：通過兩個屬性搜索對象索引集

回答

相關問題