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

Question

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

编辑：我需要多次搜索不同线的同一点集。这些点始终是恒定的，但在每次搜索期间线会有所不同。通常，点集的数量级为数万（~50k）。

Answer 1

至于查询：

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

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

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

Answer 2

此搜索无法比线性搜索更快地完成，因为输入数据和结果总体具有相同的复杂性。