寻找高效的算法，快速找到最近的线（由垂直距离定义）到任意点

Question

我在2D中有一组大量的线，具有已知的起点和终点，并且想找到那些边缘的最近（由垂直距离定义）（或者将这些边的扩展到它们的开始和终点））到任意点。

到目前为止，我所做的最好的是，沿着每行生成一组样本点，并使用KD树来解决点的最接近的邻难 - 即找到最近的线采样点到查询点。但这是不准确的，需要大量的长线样品。

我确实看到了： 最近的边缘算法检测相对于点（在所有方向上）

但它依赖于扫描方法和少量有限长度的线条。

Answer 1

所有线都定义了平面细分，其中每个多边形区域由有限数量的线段或光线界定。因此，首先，您需要找到一个（可能是无限的）区域，包含查询点，然后您将能够从这一点选择最小距离的边界线。

有很多方法可以预处理平面细分，以便解决点位置问题具有对数时间复杂性。通常设计了一些分层数据结构，可以遍历任何查询点，并且证明，遍历路径的长度受 $ o（log（n））$ ，其中 $ n $ 是区域数。作为@pseud中的评论中提到，您也可以使用二进制空间分区（bsp）来构建一个BSP树 - 它也是一个分层数据结构（二进制树），它将允许您有效地找到包含查询点的区域。它看起来像你的问题适合这种BSP方法。

抱歉说，您可以使用 $ o（n）$ 边界段/光线，其中 $ n $ 是行数。为了克服这个困难，您可以进一步将每个区域细分为 voronoi图，为其边界段和光线。很容易看出，这种精致区域的总数将受到 $ O（n ^ 2）$ 的限制，这仍然为您提供最近的线路的对数时间复杂度搜索。然而，平均情况下，这些具有许多边界段/射线的区域将占所有地区的一小部分 - 因此，平均您仍然能够通过在区域边界上循环快速选择最近的边界段/射线。

---

如果您想了解您正在使用的几何结构的常规属性 - 读取这个 wiki页面。

Answer 2

我可能已经误解了你的目标 - 你是否假设边缘在两个方向上继续进行，即使它们是由它们的2个特定点定义？我假设是因为你说距离由垂直距离定义。在这种情况下怎么样 -
1.对于每个线段，计算角度。
2.绘制一个虚线，以垂直于线段的角度穿过任意点。
3.找到线段和新的虚线之间的交叉点，找到该点之间的距离和任意点。保持最低距离。
如果线路不是无限的，那么当你检查距离时，检查min（距离开始点，距离到终点）。