从一个大的二维集合中挑选一个子集？

Question

从一个大的二维集合中挑选一个子集？

4

我有一些带有属性x和y（位置）的对象。我想获取并处理那些与我附近（！）但忽略超出范围（*）的对象。

 __________________________
|   __________             |
|  |     !    | *          |
|* |         !|      *     |  -me = center of subset
|  |    me    |            |  -!  = elements of subset
|  |  !       |            |  -*  = elements of full set, not visible
|  |_______!__|   *       *|
|__________________________|

慢速的方法是迭代整个未排序的集合，并忽略距离太远的元素。但是，我将有一个大数据集，并且需要相当高的性能。

相反，我正在寻找一种选择仅附近元素的方法。也许通过某种方式对2d集进行排序，并仅在一定范围内迭代集合（从子集的边界到边界）。

有没有好的方法来做到这一点？

（注意：对象的位置是静态的，集合可以进行预处理）

- user717572

X和Y是经度和纬度吗？ - Haney

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

构建一个包含所有点的四叉树。

给定查询矩形R和四叉树根节点Q，查询算法的伪代码如下。

query(Rectangle R, QuadTreeNode Q)
    if R and Q.bounds are disjoint
        yield no points
    else if R contains Q.bounds
        yield all points in the subtree of Q
    else (if R intersects Q.bounds)
        yield all points in query(R, Q.child[i]) for i = 0, 1, 2, 3

这假设一个QuadTreeNode有矩形边界（Rectangle bounds）和四个QuadTreeNode子节点（QuadTreeNode child[4]）。