c++ - 是否有一种有效的标准算法来栅格包括其内部区域的多边形-6ren

c++ - 是否有一种有效的标准算法来栅格包括其内部区域的多边形

转载作者：塔克拉玛干更新时间：2023-11-02 23:28:06

<分区>

Possible Duplicate:
Rasterizing a 2D polygon

我需要光栅化一个多边形，包括它的内部区域(确定位于多边形内部的网格的所有图 block )。目前，我通过使用简单的 Bresenham 来确定边界图 block ，但到目前为止我还没有有效的方法来栅格化多边形的“内部”(也可能是凹面)。到目前为止，我的方法是将图 block 范围限制为包含多边形的矩形，然后使用多边形缠绕算法确定每个图 block 中心是位于内部还是外部。这是非常低效的，因为它涉及检查每个图 block 的每个多边形边界段。从第一眼来看，肯定应该有一种更快的方法，例如……就像使用光栅边界缠绕一样。是否有解决此问题的标准算法，甚至可能是 C++ 中的库实现？