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

debugcn 发表于 Dev

史蒂夫·贝内特（Steve Benett）

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

在此处输入图片说明

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

对于n = 1000 fe（这是一个可能的数字），这可能是一个实际的性能问题，尤其是如果距离的计算不仅是通过勾股定理在欧几里德空间中完成的，而是例如通过诸如hasrsine公式或文森蒂的。

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

该点是否在顶点的半径内？
哪一组顶点最接近该点？
该点是否被线段包围？

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

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

马可13

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

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

您将不得不在几个因素之间做出权衡，例如查询时间和内存消耗，或者查询时间和给定行集更改时更新数据结构所需的时间。后者还取决于是结构更改（添加或删除线），还是仅现有线的位置发生变化。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-06-7

我来说两句

0条评论

登录后参与评论

来自分类Dev