有什么方法可以在Scipy中为KD树实现添加点

Question

我有一组点，我想为其构建 KD 树。一段时间后，我想定期向该 KDTree 添加更多点。有没有办法在 scipy 实现中做到这一点

Answer 1

k-d-树的问题在于它们不是为更新而设计的。

虽然您可以轻松地插入对象（如果您使用基于指针的表示，这比基于数组的树需要更多的内存），并使用逻辑删除消息等技巧进行删除，但进行此类更改会降低对象的性能树.

我不知道增量重新平衡 k-d-树的好方法。对于一维树，有红黑树、B 树、B* 树、B+ 树等等。由于旋转轴和不同的排序，这些显然不适用于 k-d-树。所以最后，对于 k-d-tree，最好只是收集更改，并时不时地进行“完整的树重建”。那么至少树的这一部分会相当不错。 但是，存在一个类似的结构（在我的实验中，它通常优于 k-d-树！）：

R*-树

。它不执行二进制分割，而是使用矩形边界框来收集对象，并且花了很多心思使树成为动态数据结构。这也是 R* 树比 R 树表现更好的地方：它对 kNN 搜索有更巧妙的分割，并且执行增量重新平衡来改进其结构。

Answer 2

https://github.com/stefankoegl/kdtree

，可以从一个空的 KD 树开始并一个接一个地添加节点。

pip install kdtree

import kdtree
# Create an empty tree by specifying the number of
# dimensions its points will have
tree = kdtree.create(dimensions=3)
tree.add((1, 2, 3))

我不知道它是否比 SciPy 提供的慢，但至少它可以很好地满足我的需求（向树添加点，除非有一个点已经太接近了）。

这是一个更完整的示例：

import random
import matplotlib.pyplot as plt
import kdtree

SIZE = 100
N = 10_000
MIN_DISTANCE = 5
MIN_DISTANCE_2 = MIN_DISTANCE * MIN_DISTANCE

x, y = random.uniform(0, SIZE), random.uniform(0, SIZE)

tree = kdtree.create(dimensions=2)
tree.add((x, y))

xs, ys = [], []
not_xs, not_ys = [], []

for _ in range(N):
    x, y = random.uniform(0, SIZE), random.uniform(0, SIZE)
    _neighbour, distance_2 = tree.search_nn((x, y))
    if distance_2 > MIN_DISTANCE_2:
        xs.append(x)
        ys.append(y)
        tree.add((x, y))
    else:
        not_xs.append(x)
        not_ys.append(y)

plt.axes().set_aspect(1)
plt.scatter(not_xs, not_ys, color='red', s=0.1)
plt.scatter(xs, ys)
plt.show()

它尝试在 100 * 100 的正方形中随机放置 10000 个点，但不小于 5。
已放置的点为蓝色，拒绝的点为红色。