寻找每一点最近线段的有效算法

Question

给定一个多边形次因子S和一组点P，求出每个点(在二维空间中)在S中最接近的线段。

在我的背景下，我有成千上万的片段和几千点。

检查每一行的每一个点将花费太长的时间。有一个有效的算法吗？

我在考虑多种选择，但不知道哪一个是最好的。

1. 建立一个梯形地图，并查询每个点在其中的脸。然后越过脸部的边缘(在细分部分)，找到最近的线。
2. 构建范围树或段树。在点周围查询一个框，并在其中找到最近的线段。盒子里必须有段才能找到任何东西。
3. 建立线段voronoi图。每个脸描述最近的段，但我不知道如何做点查询，因为边缘可以是抛物线弧线。

什么是解决这个问题的好的高层次方法？

Answer 1

Postgis中最近的邻居

Postgis的方法是使用R-树和自定义搜索算法.当像在常规查询中一样沿着树向下走时，它们会跟踪它们在树中遇到的边界区域中对象的最小距离和最大距离。树的每个遇到的分支都被添加到活动分支列表(ABL)中，使用距离度量对其进行修剪。

它们在ABL中选择分支的边界区域，并递归地应用该算法。在叶(像线段这样的对象)上，它更新最近的变量。当从递归返回时，它们应用最近的变量对ABL进行更多的剪枝，直到ABL为空为止。

理论上最坏的情况是每次查询都是线性的，但实际效果要好得多。