优化多边形搜索

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

让我建议对您的网格稍作修改。目前，您为每个单元存储单元中心所属的多边形。相反，存储与单元格重叠的所有多边形。然后，每当您看到一个单元格只有一个重叠的多边形时，您就不需要进行任何包含测试。网格可以通过保守光栅化的方法构建（请注意，引用的文章不是针对保守的，而是针对一般光栅化的）。网格的效率与单个多边形单元格和总单元格的比率相关（因为这是不必执行多边形包含测试的概率）。存储本身非常便宜。您可以使用密集数组并持续访问单元格。因此，从理论的角度来看，您应该拥有尽可能多的单元格（因为单元数越多，单多边形单元格比率就会增加）。在实践中，您可能会发现缓存和其他内存效应可能会使大型网格变得不切实际。但是，除了测试之外，没有其他好的方法可以知道。因此，只需在几台不同的机器上尝试几种尺寸并尝试找到合适的尺寸即可。如果我不得不猜测，我会说您的单元格应该是方形的，并且面积约为平均多边形面积的 1% - 5%。此外，与许多细长多边形相比，可以更有效地处理更紧凑的多边形。

Answer 2

选择任意点并从该点笔直向下画一条线。您命中的第一个多边形边会告诉您该点所在的多边形。因此，如果您不想进行多边形测试，那么与其将空间划分为规则网格，不如先将其切割成垂直切割的条带，这些条带穿过所有多边形交叉点。现在，在每个条带内，没有多边形边交叉或结束，因此您可以从下到上制作所有这些边的有序列表。如果要查找包含点的多边形，请使用 x 坐标进行二分搜索以找到合适的条带。然后在跨越条带的边列表中，您可以使用 y 坐标进行二分搜索以找到该点下方最近的一条，并告诉您该点所在的多边形。谷歌“梯形分解”可以找到很多关于类似技术的信息。