python - 大量点的多边形中的点

Question

我想知道确定大量点（O（100万）是否在多边形集合（O（10））内部或外部的最有效方法是什么？后者不一定是凸的，但不是他们有洞。目前我通过将它们的位置与边界框进行比较来修剪点的数量，然后在剩余的点上使用这种交叉数方法。但是也许有更快的方法？

Answer 1

有一个有效的 matplotlib 函数：matplotlib.nxutils.points_inside_poly()。该算法记录在此页面上。

Answer 2

假设您有轴对齐的边界框，您可以按 x 坐标对点列表进行排序，通过二分搜索找到列表点上的位置在边界框的内部或外部，并可能一次丢弃大量点。重复 y 坐标。然后像以前一样继续剩下的点。您可以执行多边形三角剖分以加快边界框内的测试。

当平面的面积远大于多边形的面积并且多边形相当紧凑（即不长也不薄，这可能会给您带来很多误报）时，效果最好。

Answer 3

我可能会使用四叉树对“我在多边形内部还是外部”进行快速粗略测试，以达到您在生成四叉树时确定的某种精度。

每次查找都是 O(log n)，这将是您可以获得的最快速度。对于位于标记为“包含边缘”的四叉树单元格内的点，您必须进行传统的多边形点测试。