Python kdtree 找到 "n" 最近邻组（坐标）

Question

Objective：给定坐标 X，找到坐标 X 的 "n" 个最近的线多边形，而不仅仅是 "n" 个最近的点。示例：https://i.imgur.com/qyxV2MF.png

我有一组可以有两个以上坐标的空间线多边形。它们的坐标存储在 (scipy)KDtree 中以启用 NN 搜索。

首先，我将查询 "i" 个最近的坐标，然后查找相应的线-多边形-> "i" 坐标不一定会产生 "i" 线。

为了实现 "n" 最近的线路，我需要增加 "i"。我的问题是 "i" 可能无法预测，因为每个线多边形之间的坐标数量不同。例如，一个线多边形可以用 2 个坐标表示，但另一个可以用 10 个坐标表示。大多数时候，我只需要 2 个距离 X 点最近的相邻线多边形。

在示例图像中，我需要 A 行和 B 行作为我的结果。即使 "i" = 3，也只会找到 A 行，因为 A1、A2、A3 是 X 的最近邻居。

问题：有没有办法将一个形状的坐标组合在一起，然后进行NN搜索得到"n"个独特的形状？（除了强制 "i" 以确保 "n" 独特的形状）

当前的解决方法伪代码：

found = []
while True:
    if first_loop:
        result = look up N nearest coords
    else:
        result = look up Nth nearest coord

    look up shapes using result and append to found
    perform de-duplication of found

    if len(found) >= required:
         return found
    else:
         N = N+1 # to check the Nth neighbor next iteration

Answer 1

如果我没有正确理解你的问题，那就是拥有正确数据结构的问题。

让我们有以下数据结构， 1. 从线-多边形到点的字典 2. 另一个从点到线多边形的字典（或者等效于从 bidict 而不是几个字典的单个双向映射） 3. 一个布尔数组visited，大小等于点数

现在下面的算法应该可以解决你的问题（可以用上面的数据结构有效地实现）：

对于所有点初始化访问数组为False。
首先从kd-tree中找到离查询点最近的点，将匹配点和匹配点所属的对应多边形中的所有点标记为已访问，return 那个特定的多边形 (id) 作为最近的多边形（如果有多个这样的多边形，return 全部）。
重复第 2 步，直到 n 个这样的（不同的）多边形 returned。考虑来自 kd-tree 的新点 returned 与查询点 iff 尚未访问（如果 kd-tree 的匹配点 returned 已经被访问，则丢弃它并查询下一个最近的匹配点）。访问一个点后，将该点和相应多边形中的所有点标记为已访问，并 return 多边形。

Answer 2

我看到有两种有效的方法：

索引完整 "line-polygons"：为此，您可以通过最小边界矩形来限制每个线多边形。然后使用适当的索引结构（如 R-Tree）对所有矩形进行索引。您将在最低级别拥有线多边形而不是点，因此您必须针对这种情况调整距离。
使用Distance Browsing：这里的想法是将其线多边形的id附加到每个点并在索引结构（例如KD-Tree）中索引这些点。然后，您使用距离浏览连续检索下一个最近的点到您的查询。继续此操作，直到找到 n 个不同线多边形的点。

Python kdtree 找到 "n" 最近邻组（坐标）

Python kdtree find "n" nearest neighboring groups (of coordinates)

python

algorithm

data-structures

nearest-neighbor

kdtree