我需要从表示为点的列表封闭2D多边形创建一个二进制位。 能否请你点我高效，足够简单的算法来做到这一点，或者，甚至更好，一些C ++代码吗？
非常感谢！
PS：我想避免添加依赖我的项目。 但是，如果你认为一个开放源码库，我可以随时看代码，因此它可以是有用的。
Answer 1:
你想要魔谷歌的短语或者是“非零缠绕规则”或“偶奇多边形填充”。
参见维基百科条目：
- 非零缠绕规则
- 偶奇多边形填充
两者都非常容易实现，而且足够快于大多数的目的。 对于一些小聪明，他们可以进行抗锯齿以及。
Answer 2:
您可以检查出在Pygame的多边形填充程序。 看看draw_fillpoly功能。
该算法是非常简单的。 它发现所有每段沿Y轴相交的位置。 这些交叉点进行排序，然后水平地填充每一对交叉点的。
这将处理复杂的和交叉的形状，但很明显，你可以用大量段粉碎这一算法。
Answer 3:
- 三角您多边形
- 光栅每个三角形（如果你使用的是GPU，然后它可以为你做到这一点，相反，它是GPU的原始操作）
- 如果三角形不具有链段的平行于x轴，则打破它成两个三角形与线平行于x轴，并通过它与中位数-γ点变为
- 现在剩下的任务是绘制，其具有段平行于x轴的三角形。 这样的三角形有一左侧部分和右侧部分
- 迭代三角形的扫描线（最小 - y以最大-Y）。 对于每个y在与扫描线计算左和右段的点。 填充扫描线段这两个点（一个简单的memset）。
复杂度为O（像素区）
Answer 4:
对于一个强大的执行力度“奇偶规则”
见DAREL雷克斯芬利的高效多边形填充 ，或者Blender的版本的它。
这是支持自相交线，而不需要复杂的代码来检测这种情况奇数/偶数充填方法，并且不依赖于绕组（多边形可以颠倒并产生相同的结果）。
更新，我做了DAREL雷克斯的方法的优化版本，避免遍历每个Y型像素的所有坐标 。
单机实现：
- C99 。
- 拉斯特 （含测试）。
尽管增速将可能是指数，从快速测试，其周围7.5倍更快（11倍拆卸时round通话），使用在2540x1600的区域，情况因人而异任意手绘涂鸦。
文章来源: Rasterizing a 2D polygon
