优化多边形搜索

Question

我将世界分成 X 个随机多边形。

然后给我一个坐标C1，比如(-21.45, 7.10)，我想把正确的多边形归于这个坐标。

第一个解决方案是对每个应用我的“point_in_polygon”算法（给定一组定义多边形的坐标和一个定义点的坐标，告诉我该点是否在内部）多边形，直到我找到正确的那个。但是，如果我有很多点要放入很多多边形，那将是非常昂贵的。

对此的改进依赖于以下想法：为了优化搜索，我创建了一个 grid （一个集合），其中包含一个步骤 n, k 我已经将每对坐标使得：

for i=-180 to 180 step n 
    for j = -90 to 90 step k
        grid.add(i,j)

然后我创建了一个字典，并为集合中的每一对找到对应的多边形

For each g in grid
    For each p in polygons
        If point_in_polygon(g,p) == True
            my_dict(g) = p

然后，当我收到 C1 时，我会在我的网格中寻找最近的坐标，假设是 g1。感谢my_dict，我可以快速获得p1 = my_dict(g1) 然后我计算 point_in_polygon(C1, p1) 这可能是真的。如果不是，我会找到最接近的 g 并分配给不同的多边形，然后重新测试。等等，直到我找到正确的多边形。

现在，问题是：创建网格的最佳 n、k 是多少？

这样我就可以用最少的步骤找到正确的多边形。我不希望它太低，因为搜索分配给不同多边形的最近 g 可能很昂贵。我也不希望它太高，因为那样我可能会丢失一些多边形，然后搜索永远不会收敛。

我的直觉是最小的多边形会给出台阶。

我不确定这是一个编程问题、一个数学问题，还是我可以根据经验找到的问题，这就是我在这里问的原因。

感谢任何意见！

Answer 1

让我建议对您的网格稍作修改。目前，您为每个单元格存储单元格中心所属的多边形。相反，存储与单元格重叠的所有多边形。然后，每当您看到一个单元只有一个重叠多边形时，您就不需要进行任何包含测试。可以通过保守 rasterization 的方法构建网格（请注意，参考文章不是关注保守而是一般光栅化）。

网格的效率与单个多边形单元格与总单元格的比率相关（因为这是不必执行多边形包含测试的概率）。存储本身非常便宜。您可以使用密集阵列并持续访问单元格。因此，从理论上讲，您应该拥有尽可能多的单元格（因为单元格越多，单多边形单元格的比率就会增加）。实际上，您可能会发现缓存和其他内存效应可能会使大型网格不切实际。但是，除了测试之外，没有什么好的方法可以知道。所以，只需在几台不同的机器上尝试几种尺寸，然后尝试找到合适的。

如果非要我猜的话，我会说你的单元格应该是方形的，并且面积大约是平均多边形面积的 1% - 5%。此外，与许多又长又细的多边形相比，可以更有效地处理更紧凑的多边形。

Answer 2

选择任意一点并从该点垂直向下画一条线。您击中的第一个多边形边告诉您该点位于哪个多边形中。

因此，如果您不想进行多边形测试，则不要将 space 划分为规则网格，而是先将其切成条带，垂直切割穿过所有多边形交点。

现在，在多边形边的每个条带内 none 交叉或结束，因此您可以从下到上制作所有这些边的有序列表。

如果要查找包含点的多边形，则使用 x 坐标进行二进制搜索以找到合适的条带。然后在跨越条带的边列表中，您可以使用 y 坐标进行二进制搜索以找到该点下方最近的边，并告诉您该点位于哪个多边形中。

Google 'trapezoidal decomposition' 查找有关类似技术的大量信息。

优化多边形搜索

Optimizing Polygon Search

python

algorithm

r

polygon