最接近线段集的点

Question

我在2d空间中有一个点p和n个线段。是否有一种方法可以对线段进行预处理，以便有效地(即亚直线)找到最接近P的线段(即垂直距离最低的线段)？

这是我们想要解决的现实问题。我们得到的最佳(近似)答案是将点的线段的末端预处理成四叉树/2d kd树，并找到最近的点。在大多数情况下，这将导致一个近乎最佳的答案(甚至可能是正确的答案)。

另外，我们也可以使用Mongodb的geonear，它也与点一起工作。

我们能做得更好吗，特别是在准确性方面？

Answer 1

如果您的分段是均匀分布的，并且不太长，您可以考虑一种网格方法:选择一个单元格大小，并确定每个单元格与之交叉的单元格(这是通过“绘制”网格上的分段来完成的)。然后，对于一个查询点，通过访问越来越大的邻居，找到最近的非空单元格，并计算出与所找到的段的最接近的距离。您需要继续搜索，只要查询点与下一个单元格之间的距离不超过到目前为止找到的最短距离。

​

​

如果分布不均匀，则四叉树分解效果更好.

更广泛地说，一种合适的策略是使用任何加速装置，快速报告少量候选段，并保证:最近的段必须在候选段中。