计算多边形和栅格图像之间的交点

Question

如果我有一个二值图像和一个不规则的凸多边形，我该如何计算它们是否相互交叉？根据图像描述多边形的坐标。

我对此有几点想法，来自碰撞检测或填充算法的角度来看，但我不认为两者都是最优的。我确信有一个经过实践检验的方法，但不能想到关键字。

这里是我的意思的例子：

在这种情况下，它应该返回true。

Answer 1

我会推荐这下面的算法：

导线采用布氏算法每行的多边形的边界，并在每个像素，采样光栅。如果它是您接受可见的颜色，例如非零字母，请报告交叉点。

这样做的好处是只能处理多边形的边缘，所以不需要迭代多边形内的所有像素。