用最少数量的矩形填充多边形
我正在尝试渲染多边形，但它们只能使用轴对齐的矩形来渲染。因此，我正在寻找一种基本上可以使用最少可能数量的矩形填充多边形的算法。如果有助于减少数量，则允许矩形彼此重叠。
我已经实现了这种填充算法，基本上就足够了。缺点是它限制了每个像素行的矩形。我最终想尽可能减少矩形的数量。
I'm trying to render polygons, but they can only be rendered using axis-aligned rectangles. So, I' looking for an algorithm that can basically fill in a polygon using the least possible amount of rectangles. If it helps reduce the amount, the rectangles are allowed to overlap each other.
I've already implemented this fill algorithm, which mostly suffices. The downfall is that it restricts rectangles to each pixel row. I ultimately want to reduce the amount of rectangles as much as possible.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
多边形的像素表示与直线多边形相同，您可以非常快速地对其进行分区。查看此问题的答案。
Pixel representation of polygon is same as rectilinear polygon and you can partition it quite fast. See answer to this question.
当多边形由大矩形组成时，消除该限制（每个矩形的高度为一个像素）在某些特殊情况下会有所帮助，但在一般情况下则完全没有帮助。
怎么样：使用该算法，但尽可能向上和向下延伸每个矩形，当所有矩形都就位时，消除多余的矩形。
仍然有一点改进的空间，因为在一些非常罕见的情况下，消除冗余矩形的顺序可能很重要，但说实话，我认为对于实际应用来说不值得担心解决方案。
Removing that restriction (that each rectangle have a height of one pixel) helps in some special cases when the polygon is made of big rectangles, but not at all in the general case.
How about this: use that algorithm, but extend each rectangle upward and downward as much as you can, and when all of the rectangles are in place, eliminate redundant ones.
There is still a little bit of room for improvement, in that the order in which you eliminate redundant rectangles might matter in some very rare cases, but honestly I don't think it's worth worrying about for a practical solution.