栅格化2D多边形

Question

我需要从一个封闭的2D多边形创建一个二进制位图,表示为一个点列表.能否请您指出有效且足够简单的算法,或者甚至更好的一些C++代码？

非常感谢!

PS:我想避免在我的项目中添加依赖项.但是,如果您建议使用开源库,我总是可以查看代码,因此它也很有用.

Answer 1

你想要的神奇谷歌短语是"非零缠绕规则"或"甚至奇数多边形填充".

查看维基百科条目:

• 非零缠绕规则
• 甚至奇数多边形填充

两者都非常容易实现,并且对于大多数目的来说足够快.有一些聪明,他们也可以做反抗锯齿.

Answer 2

您可以在Pygame中签出多边形填充例程。看一下draw_fillpoly功能。

该算法非常简单。它找到每个线段沿Y轴相交的所有位置。对这些交叉点进行排序，然后水平填充每对交叉点。

这将处理复杂且相交的形状，但是显然您可以使用大量线段来粉碎此算法。

Answer 3

为了强有力地实现“奇偶规则”

请参阅Darel Rex Finley 的 Efficient Polygon Fill，或Blender 的版本。

这是一种奇/偶填充方法，支持自相交线，不需要复杂的代码来检测这种情况，并且不依赖于缠绕（多边形可以反转并产生相同的结果）。

更新，我制作了 Darel Rex 方法的优化版本，避免循环遍历每个 y 像素的所有坐标。

独立实现：

• C99。
• Rust（带测试）。

虽然加速可能是指数级的，但从快速测试来看，round在 2540x1600 区域上使用任意手绘涂鸦，速度提高了约 7.5 倍（删除调用时为 11 倍），YMMV。