我想找到一种最好的方法,因为所有坐标都是整数值,而多边形只包含水平和垂直线。我认为可能有一种简单而快速的方法来做到这一点。
从渐近复杂的角度来看,直线多边形的处理并不比一般多边形更简单:没有预处理的O(N),O(N Log N)预处理后的O(Log N)(但是使用复杂的程序) 。
对于没有预处理的情况,程序很简单:依次考虑每个垂直边并计算从给定点穿过水平半线的那些(向上+1,向下-1)。如果最终计数非零,则该点在内部。
轮廓上的点的状态取决于应用程序。
对于没有太大整数坐标的直线poygons,你可以通过“压缩”它们来做得更好一点。通过X和Y上的两个独立排序,您可以获得从X(或Y)到范围[0,N]中的整数索引的映射。这给出了缩小的多边形,大小为NxN。
现在,您可以将多边形嵌入到图像中并进行预处理,以将像素标记为内部/外部(通过种子填充)。在填充两个用于坐标转换的查找表之后,您可以获得恒定时间O(1)中任何点的状态。
这将需要O(N²+ M)预处理时间和存储,其中M是X和Y值的范围。