python - 优化多边形搜索

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%。此外，与许多又长又细的多边形相比，可以更有效地处理更紧凑的多边形。