c# - 从更大的二维集合中挑选一个子集？

Question

我有一些具有属性 x 和 y(位置)的对象。我想获取并处理我附近的对象(!)，但忽略超出范围的对象(*)。

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

缓慢的方法是迭代完整的、未排序的、设置的和忽略那些距离太大的元素。但是我将拥有一个大数据集，并且需要相当多的性能。

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

有什么好的方法吗？

(注意:物体的位置是静态的，可以对集合进行预处理)

Answer 1

构造一个 quadtree包含您的所有积分。

给定查询矩形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 child[4]。