0

我应该为此使用什么数据结构/算法？

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

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

谢谢

4

2 回答 2

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);

然后，您可以使用排序算法（例如 QuickSort - 使用O(n log(n))）对它们进行排序，并使用简单的插入排序来保持它们随着点的来来去去而排序。当您需要使用矩形选择时，您可以简单地对它们进行二进制搜索（O(log(n))）以找到第一个属性的边界（例如，x），然后再次越过那个较小的集合以找到边界的第二个属性（比如说，y），其余的集合将是您正在寻找的那些，使您的搜索时间（O(4 log(n)）最坏情况，而您的插入时间线性（最坏情况）。不是太破旧，如果我自己这么说的话。

于 2012-10-10T00:36:55.573 回答
0

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

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

如何搜索影响空间点的对象

于 2013-05-12T07:22:31.410 回答