栅格化2D多边形

Question

我需要从一个封闭的2D多边形创建一个二进制位图，表示为点列表。你能否指点我一些有效率和足够简单的算法来做到这一点，或者更好一些C++代码？

非常感谢！ PS：我想避免添加一个依赖项到我的项目中。但是，如果您建议使用开放源代码库，则始终可以查看代码，因此它也可能很有用。

Answer 1

你想要的神奇的谷歌短语是“非零蜿蜒规则”或“甚至奇怪的多边形填充”。

参见维基百科的条目：

• non-zero winding rule
• even odd polygon fill

两者都非常容易实现，而且足够快于大多数的目的。随着一些聪明，他们也可以被制成antialiased。

Answer 2

• Triangulate your polygon
• 光栅的每个三角形的（如果你使用的是GPU，然后它可以为你做到这一点，相反，它是GPU的原始操作）
  • 如果三角形没有一个平行于x轴的线段，然后将其分成两个三角形，线条平行于x轴并穿过它的中点y。现在剩下的任务是绘制一个三角形，该三角形具有一段平行于x轴的线段。这样一个三角形有一个左侧和一个右侧的线段
  • 迭代三角形的扫描线（min-y到max-y）。对于每个y，计算该扫描线中的左侧和右侧线段的点。将扫描线段填入这两点（一个简单的memset）。

复杂度为O（像素区）

Answer 3

可以在Pygame中检查出的多边形填充程序。看看draw_fillpoly函数。

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

这将处理复杂和相交的形状，但显然你可以粉碎这个算法与大量的段。

Answer 4

对于的"even-odd rule"

鲁棒执行力度参见Darel Rex Finley's Efficient Polygon Fill，或它的Blender's version。

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

---

更新，我做了DAREL雷克斯的方法的优化版本，避免遍历所有坐标对于每个y像素。

独立实现：

• C99。
• Rust（带测试）。

虽然增速将可能是指数，从快速测试，其周围7.5倍更快（11X去除round呼叫时），利用绘制涂鸦在2540x1600的区域，情况因人而异任意手。