大量积分的点多边形

问题描述：

我想知道什么可能是确定大量积分（O（100万）是集合内部还是外部（O（10））的最有效方式？）的多边形？后者不一定是凸的，但它们没有孔，此时我通过比较它们的位置与边界框来修剪点的数量，然后在其余点上使用this穿越数方法。有没有更快的方法？大量积分的点多边形

应该值得将多边形预处理成（可能更长的）凸多边形列表。一方面，它会使你的边界框更有效。 – 2011-05-13 23:01:09

如果您可以定位生成的凸多边形的边缘（例如全部为顺时针），则可以使用更快的方法（方法3 [此处]（http://paulbourke.net/geometry/insidepoly/））。 – 9000 2011-05-13 23:34:03

答

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

当平面的面积远大于多边形的面积并且多边形相当紧凑时（即不会很长且很薄，这可能会导致很多误报），性能会更好。

答

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

每次查找都是O（log n），这将会尽可能快地得到。对于标记为“包含边缘”的四叉树单元格内的点，则必须执行传统的点中多边形测试。

答

这里有一个高效的matplotlib函数：matplotlib.nxutils.points_inside_poly()。算法记录在this page上。