如何更有效地找到离特定点最近的线段？

Question

这是我经常遇到的一个问题，我正在寻找更有效的方法来解决它。看看这张照片：

在此处输入图片说明

假设您想找到从红点到线段 a _n的最短距离。假设您只知道线段的起点/终点 (x,y) 和点。现在这可以在 O(n) 中完成，其中 n 是线段，通过检查从点到线段的每个距离。这是 IMO 无效的，因为在最坏的情况下，必须进行 n-1 次距离检查，直到找到正确的距离。

对于 n = 1000 fe（这是一个可能的数字），这可能是一个真正的性能问题，特别是如果距离计算不仅通过勾股定理在欧几里得空间中完成，而且例如通过像半正弦公式或文森蒂的。

这是在不同情况下的普遍问题：

要回答这些问题，我知道的唯一方法是 O(n)。现在我想知道是否有数据结构或不同的策略可以更有效地解决这些问题？

简而言之：我正在寻找一种方法，在我开始距离计算之前，可以以某种方式“过滤”线段/顶点以获得一组潜在的候选对象。将复杂度降低到 O(m) 的方法，其中 m < n。

Answer 1

可能不是可接受的答案，但评论太长：此处最合适的答案取决于您未在问题中说明的详细信息。

如果您只想执行一次此测试，则无法避免线性搜索。但是，如果您有一组固定的行（或一组不会随时间变化太大的行），那么您可以使用各种技术来加速查询。这些有时被称为空间索引，如四叉树。

您必须期望在多个因素之间进行权衡，例如查询时间和内存消耗，或者查询时间和在给定的一组行更改时更新数据结构所需的时间。后者还取决于是结构变化（添加或删除线），还是仅更改现有线的位置。