针对大量点的多边形点

Question

我想知道什么是最有效的方法来确定是否有大量的点(O(100万)在多边形的集合(O(10))内部或外部？后者不一定是凸的,但不是它们有洞.目前我通过比较它们的位置和边界框来修剪点数,然后在剩下的点上使用这种交叉数法.但是,是否有更快的方法？

Answer 1

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

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