你想要的神奇谷歌短语是“非零缠绕规则”或“偶数奇数多边形填充”。
查看维基百科条目：

• non-zero winding rule
• even odd polygon fill

两者都非常容易实现，并且对于大多数目的来说都足够快。用一些聪明的方法，它们也可以进行抗锯齿处理。

您可以在Pygame中查看多边形填充例程。看看draw_fillpoly函数。
这个算法非常简单。它查找每个线段沿着Y轴相交的所有位置。对这些交点进行排序，然后水平填充每对交点。
这将处理复杂和相交的形状，但显然，您可以用大量的线段来破坏该算法。

对于"even-odd rule"的稳健实施
参见Darel Rex Finley's Efficient Polygon Fill，或Blender的版本。
这是一种奇/偶填充方法，支持自相交线，不需要复杂的代码来检测这种情况，并且不依赖于缠绕 （多边形可以反转并产生相同的结果）。
更新，我做了一个Darel雷克斯方法的优化版本，避免了为每个y像素循环所有坐标。
独立实现：

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

• 三角化多边形
• 光栅每个三角形（如果你使用的是GPU，那么它可以替你做，这是GPU的一个基本操作）
• 如果三角形没有平行于x轴的线段，那么用一条平行于x轴的直线将其分成两个三角形，并以中点y通过三角形的点
• 现在剩下的任务是画一个三角形，它有一条平行于x轴的线段。这样的三角形有一个左边线段和一个右边线段
• 迭代三角形的扫描线（min-y到max-y）。对于每个y，计算该扫描线中的左段和右段的点。填充扫描线段的这两个点（一个简单的memset）。

复杂度为O（面积以像素为单位）

除了其他人提到的扫描线算法之外，在论文Wavelet Rasterization by J. Manson and S. Schaefer中描述了一种完全不同的方法。
该算法将图像的每一条边缘Map到小波域上，然后进行小波逆变换重构图像。
优点是该算法能够计算精确的覆盖率（即，抗锯齿），这是用扫描线算法极难实现的。它也能容忍破碎的多边形;即具有不连续轮廓的多边形。