栅格化 2D 多边形
我需要从表示为点列表的闭合二维多边形创建二进制位图。您能否向我指出高效且足够简单的算法来实现这一点，或者更好的是一些 C++ 代码？
多谢！
PS：我想避免向我的项目添加依赖项。但是，如果您建议一个开源库，我可以随时查看代码，因此它也很有用。
I need to create a binary bitmap from a closed 2D polygon represented as a list of points. Could you please point me to efficient and sufficiently simple algorithms to do that, or, even better, some C++ code?
Thanks a lot!
PS: I would like to avoid adding a dependency to my project. However if you suggest an open-source library, I can always look at the code, so it can be useful too.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
你想要的神奇谷歌短语是“非零缠绕规则”或“偶奇多边形填充”。
请参阅维基百科条目：
两者都非常容易实现，并且对于大多数用途来说都足够快。通过一些技巧，它们也可以被抗锯齿。
The magic google phrase you want is either "non-zero winding rule" or "even odd polygon fill".
See the wikipedia entries for:
Both are very easy to implement and sufficiently fast for most purposes. With some cleverness, they can be made antialiased as well.
您可以查看 Pygame 中的多边形填充例程。看看
draw_fillpoly函数。该算法非常简单。它找到每个线段沿 Y 轴相交的所有位置。对这些交点进行排序，然后水平填充每对交点。
这将处理复杂且相交的形状，但显然您可以用大量的线段来破坏该算法。
You can check out the polygon fill routine in Pygame. Look at the
draw_fillpolyfunction.The algorithm is pretty simple. It finds all the positions that each segment intersects along the Y axis. These intersections are sorted, and then horizontally fills each pair of intersections.
This will handle complex and intersecting shapes, but obviously you could crush this algorithm with large amounts of segments.
有关“偶奇规则”的可靠实现，
请参阅< a href="http://alienryderflex.com/polygon_fill" rel="nofollow noreferrer">Darel Rex Finley 的高效多边形填充，或 Blender 的版本。
这是一种奇/偶填充方法，支持自相交线，不需要复杂的代码来检测这种情况，并且不依赖于缠绕（多边形可以反转并产生相同的结果）。
更新，我制作了 Darel Rex 方法的优化版本，避免循环遍历每个 y 像素的所有坐标。
独立实现：
虽然加速可能呈指数级增长，但从快速测试来看，在 2540x1600 区域上使用任意手绘涂鸦，速度提高了约 7.5 倍（移除
round调用时为 11 倍），YMMV。 EM>For a robust implimentation of the "even-odd rule"
See Darel Rex Finley's Efficient Polygon Fill, or Blender's version of it.
This is an odd/even filling method which supports self intersecting lines, without needing complex code to detect such situations, and doesn't depend on winding (the polygon can be reversed and yield the same results).
Update, I made an optimized version of Darel Rex's method that avoids looping over all coordinates for each y-pixel.
Stand alone implementations:
While speedup will likely be exponential, From a quick test, its around 7.5x faster (11x when removing
roundcall), using an arbitrary hand drawn scribble over a 2540x1600 region, YMMV.复杂度为 O（以像素为单位的面积）
Complexity is O(Area in pixels)
除了其他人提到的扫描线算法之外，论文 中描述了一种完全不同的方法J. Manson 和 S. Schaefer 的小波光栅化。
宽松地说，该算法将每条边缘映射到小波域上，然后采用小波逆变换来重建图像。
优点是该算法能够计算精确的覆盖范围（即抗锯齿），这是扫描线算法极难实现的。它还可以容忍破碎的多边形；即具有不连续轮廓的多边形。
In addition to scanline algorithms mentioned by others, there's a sufficiently different approach described in the paper Wavelet Rasterization by J. Manson and S. Schaefer.
Loosely speaking, the algorithm splats every edge onto the wavelet domain, then takes the inverse wavelet transform to reconstruct the image.
The advantage is that the algorithm is able to calculate exact coverage (i.e. anti-aliasing), which is extremely hard to achieve with scanline algorithms. It's also tolerant to broken polygons; i.e. polygons with a discontinuous contour.
如果您需要多边形抗锯齿，请查看 stb 中实现的光栅化器 字体文本光栅化器。作者有一篇文章解释了该算法。与其他答案中基于扫描线的算法不同，该算法要求您搜索相交节点并对每条扫描线进行排序，而该算法可以在一次传递中处理多边形的所有边，因此实际上是 O(N)。缺点是您需要创建一个与输出缓冲区大小相同的额外工作缓冲区。此外，它不处理自相交的多边形。
上面链接的文章应该很容易理解，所以我将总结其要点。假设填充多边形被定义为按顺时针顺序排列。对于任何向上的线段，其右侧将一直被填充，直到遇到向下的线段。在此算法中，给定一个向上的线段（终点高于起点），对于它相交的每个像素，剪裁到该像素的线段的 y 长度将添加到该像素右侧的像素工作缓冲区中的像素。剪裁段和像素右边界之间的区域被添加到输出缓冲区（根据斜率，该区域可以是矩形或梯形）。对于向下的线段，将减去这些值。
对所有边（以及所有多边形，如果有多个）完成此操作后，通过对缓冲区的每一行从左到右进行累积和来最终确定输出，并将总和添加到输出缓冲区经历它。这就是神奇发生的地方：从工作缓冲区具有正值的点开始的所有像素都将被填充，直到它遇到具有负值的像素，此时它将抵消，因此不再填充更多像素（直到下一个正值）值已找到）。
但您需要注意，如果这些值没有完全抵消，则可能会在图像上留下扫描线伪影。根据我的经验，使用双精度浮点数并没有那么糟糕，但是当您使用单精度浮点数时，它很容易变得很糟糕。
If you need to polygon to be anti-aliased, take a look at the rasterizer implemented in stb's font text rasterizer. There's a write up by the author explaining the algorithm. Unlike the scanline-based algorithm in the other answers that requires you to search for intersection nodes and sort them for each scanline, this one can process all edges of a polygon in a single pass, so it's effectively O(N). The drawback is that you need to create an extra working buffer with the same size as the output buffer. Also, it doesn't handle self-intersecting polygons.
The write up linked above should be easy enough to follow, so I'll summarise just the gist of it. Suppose a filled polygon is defined to be in clockwise order. For any segment pointing upwards, its right side will be filled all the way until it meets a segment pointing downwards. In this algorithm, given a segment that is pointing upwards (end point is higher than the start point), for each pixel it intersects, the y-length of the segment clipped to the pixel is added to the pixel on the right side of this pixel in the working buffer. The area between the clipped segment and the right border of the pixel is added to the output buffer (depending on the slope, this area could either be a rectangle or a trapezoid). For segments pointing downwards, the values are subtracted instead.
After this has been done for all edges (and all polygons, if there are more than one), the output is finalized by doing a cumulative sum from left to right for each row of the buffer, adding the sum to the output buffer as you go through it. This is where the magic happens: all pixels starting from the point where the working buffer has positive value will be filled until it meets the pixel with negative value, at which point it will cancel out so no more pixels are filled (until the next positive value is found).
You need to beware though that if the values don't cancel out cleanly, it may leave a scanline artifact across the image. In my experience, with double-precision float it is not so bad, but it easily becomes bad when you use single-precision.