language-agnostic - 计算多边形和光栅图像是否相交

Question

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

从碰撞检测或填充算法的角度来看，我对此有一些想法，但我认为两者都不是最佳的。我确信有一种经过试验和测试的方法，但想不出关键字。

这是我的意思的一个例子：

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

Answer 1

我会推荐以下算法：

对每条线使用 Bresenham 算法遍历多边形的边界，并在每个像素处对栅格进行采样。如果它是您接受可见的颜色，例如非零 alpha，则报告交集。

这具有仅在多边形的边缘上工作的优点，因此您不需要遍历多边形内的所有像素。