从位于距离范围内的集合中移除位置的算法

Question

我正在寻找一个解决方案，我拥有一组具有一定优先级的位置。

我想删除较低优先级的位置，使得没有剩余位置位于特定距离（比如100米）内的任何位置。

Answer 1

A k-d tree听起来很适合这个问题。

• 如果你删除了绝大多数的点，它可能使最有意义，从具有最高优先级的点开始，并为每个点，做类似的近邻搜索的东西（停止一旦我们得到由给定距离限定的点），以检查是否插入点。

  您可能需要尝试查找自动平衡变体或在此过程中偶尔重新平衡树，因为不平衡树会导致操作速度变慢。

• 如果有很大一部分点将保留下来，最好将所有点插入树中，以便从最低点开始修改最近邻点搜索（忽略点本身，以距离为界）在我们走的时候优先考虑并删除相关的要点

  使用适当的施工技术，您可以从一开始就构建平衡树。

插入和删除需要O均衡树（log n）的（一个简单的方法来删除是刚刚设置的节点的“删除”标志，但这并不永远做树更小）和O（n）在不平衡的树中。最近邻居搜索是相似的，尽管即使对于平衡树也可能会花费O（n），但这是最差的情况 - 平均而言，它应该更接近于O（log n）。

k-d树是一个二叉树，其中每个节点都是一个k维点。每个非叶节点都可以被认为是隐式地生成一个分裂超平面，该空间将空间分成两部分，称为半空间。该超平面左侧的点由该节点的左侧子树表示，超平面的点右侧由右侧子树表示。超平面方向的选择方式如下：树中的每个节点都与其中一个k维关联，超平面与该维的轴垂直。因此，例如，如果对于特定分割选择“x”轴，具有比该节点更小的“x”值的子树中的所有点将出现在左子树中，并且具有更大“x”值的所有点将是在正确的子树中。在这种情况下，超平面将由该点的x值设置，其法线将为单位x轴。

搜索在kd树收益的近邻如下：

1. 根节点开始，算法递归地向下移动的树，以同样的方式，它会如果正在插入搜索点（即，根据点是否小于或大于拆分维中的当前节点，向左或向右）。
2. 一旦算法到达叶节点，它保存该节点点为“当前最佳”
3. 该算法解开树的递归，在每个节点处执行以下步骤：
   1. 如果当前节点比当前最好的接近，那么它就成为当前最好的。
   2. 该算法检查分裂平面中距离搜索点较近的另一侧是否存在任何点。在概念上，这是通过将分裂超平面与具有半径等于当前最近距离的搜索点周围的超球体相交来完成的。由于超平面都是轴对齐的，因此将其作为简单比较来实现，以查看搜索点的分割坐标与当前节点之间的距离是否小于从搜索点到当前最佳点的距离（总体坐标）。
      1. 如果超球面穿过平面，平面另一侧可能会有更近的点，所以算法必须从当前节点向下移动树的另一个分支，寻找更近的点，遵循相同的递归处理为整个搜索。
      2. 如果超球面不与分裂平面相交，则算法继续向上走树，并且该节点另一侧的整个分支被消除。
4. 当算法结束本过程对于根节点，则搜索完成。

Answer 2

我假设你打算删除位置，从最低优先级的位置开始，距离另一个位置有一定的距离。

您可以使用quad tree来表示相对位置。这个想法是，你构造一棵树，每个节点有四个孩子。每个孩子代表一个象限，当你添加每个位置时，你遍历树。如果您击中无孩子的节点，那么您将创建新的子节点，再次表示划分为四个区域的同一区域，直到每个位置都在其自己的区域中。

创建此树后，您可以将每个位置之间的距离检查的样本大小减少到仅限于特定深度内的距离，并且仅限附近象限内的位置。

这种方法是但近似和不保证您检查跨越整个主象限的位置，但它确实有效地让你距离检查大部分地区被附近有效地降低了运行时间。为了解决这个问题，您可以使用相同的数据创建多个具有轻微偏移的四叉树，但是当然，每个四叉树将在运行时成为倍增因子，因为您将逐个构建并检查每个树。

这是回答您的问题吗？