1

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

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

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

在此处输入图像描述

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

4

1 回答 1

2

我会推荐以下算法:

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

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

于 2012-03-09T16:38:30.887 回答