algorithm - 搜索靠近一条线的点的更快方法

Question

我在二维空间中有一组点和一条线。我需要找到距离直线 D 以内的所有点。有没有办法让我不必实际计算所有点与直线的距离 di 就可以做到这一点？有没有比线性搜索更好的解决方案？

编辑:我需要为不同的线多次搜索相同的点集。这些点总是不变的，但在每次搜索期间线会有所不同。通常，点集的数量级为数万 (~50k)。

Answer 1

至于查询:

如果您使用这些点创建一个 kd 树，并使用线上的一些等距点(可能在 d 附近)点，您应该能够使用修改后的最近邻查询来找到所有在 d 范围内的点大致为 O(k + log(N))。 kd-tree 需要 O(N log N) 预处理，所以只有使用相同的点集才会更好(可能略有不同，因为您可以在 O(log N) 中从 kd-tree 添加/删除点)和不同的线路。唯一的问题是 kd-tree 并不是真的要与线条一起使用。我敢肯定有类似的东西可以更好地工作，但我不熟悉它。

注意:根据事物的排列方式，可能会出现误报和漏报，因为您实际上是在查询与线上某个点的距离，而不是线上的距离。这有多大问题在很大程度上取决于线的长度与 d 之间的比率。因此，您要么会得到相当数量的误报或漏报，除非大多数点不在该线附近。一般来说，这可能不会成为太大的问题，因为即使有误报，与 N 相比，k 也应该相当小，除非 d 相对较大。

经过一些审查，我注意到查询是针对一条线而不是线段。然而，它可以通过使线段以最小/最大 x/y 为界来转换为一个。我想可能还有更有效的方法来为此使用 kd-tree。