大量点的点在多边形内检测
我在想，怎么才能更有效率地判断很多点（大约一百万个）是在一组多边形（大约十个）里面还是外面呢？这些多边形不一定是凸的，但里面没有洞。目前，我是先通过比较点的位置和边界框来减少需要检查的点的数量，然后对剩下的点使用这种交叉数的方法。不过，是否有更快的方法呢？
3 个回答
1
我可能会使用一种叫做四叉树的结构，来快速粗略地判断“我是在多边形内部还是外部”，这个判断的精度可以在你生成四叉树的时候自己决定。
每次查找的时间复杂度是O(log n)，这已经是相当快的了。对于那些位于四叉树某个标记为“包含边”的单元格中的点，你就需要进行传统的点是否在多边形内的测试了。
2
假设你有一些轴对齐的边界框（就是那种矩形框），你可以先把这些点按照它们的x坐标进行排序。然后，通过一种叫做二分查找的方法，找出哪些点是在边界框里面，哪些是在外面，这样你就可以一次性丢掉很多不需要的点。接着再对y坐标做同样的事情。然后，继续用剩下的点进行后续操作。为了加快在边界框内的测试，你还可以进行多边形三角剖分。
这种方法在平面区域大大超过多边形区域时效果最好，而且多边形的形状要相对紧凑（也就是说，不要太长太细，这样可能会导致很多错误的判断）。
3
有一个很实用的 matplotlib 函数可以做到这一点：matplotlib.nxutils.points_inside_poly()。这个算法的详细说明可以在这个页面找到。