java - 从位于一定距离内的集合中删除位置的算法

Question

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

我想删除优先级较低的位置，以便在任何位置的特定距离(比如 100 米)内没有剩余位置。

Answer 1

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

• 如果您要删除绝大多数点，从优先级最高的点开始可能最有意义，并且对每个点执行类似于最近邻搜索的操作(停止一次我们在树中得到一个以给定距离为界的点)来检查是否插入该点。

  您可能想尝试找到一个自平衡变体或在此过程中偶尔重新平衡树，因为不平衡的树会导致操作缓慢。

• 如果保留大部分点，最好将所有点插入树中以开始并从最低优先级并删除相关点。

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

在平衡树中插入和删除需要 O(log n)(一种简单的删除方法是在节点中设置一个“已删除”标志，但这不会使树变小)和 O(n ) 在不平衡的树中。最近邻搜索是类似的，尽管即使对于平衡树也可能需要 O(n)，但这是最坏的情况 - 平均而言它应该更接近于 O(log n)。

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane are represented by the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

Searching for a nearest neighbour in a k-d tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).
2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:
   1. If the current node is closer than the current best, then it becomes the current best.
   2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is lesser than the distance (overall coordinates) from the search point to the current best.
      1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.
      2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
4. When the algorithm finishes this process for the root node, then the search is complete.