Javascript：通过两个属性搜索对象索引集

Question

我应该使用哪种数据结构/算法？

我在笛卡尔网格上有大量的点，由（x，y）指定的位置。我想快速搜索，返回位于x和y给定范围内的一组点（对象）。 （网格内的矩形）。

也许有一个轻量级框架可以做到这一点？

由于

Answer 1

我将存储该点为具有两个属性的对象：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））最差，并且您的插入时间。线性（最坏情况）太寒酸了，如果我不这样说不是我自己

Answer 2

以下是一般问题的最优实现：

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

How to search objects affecting a point in space