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

Question

可能重复:
栅格化2D多边形

我需要栅格包含其内部区域的多边形(确定位于多边形内的网格的所有图块).目前我通过使用一个简单的Bresenham来确定边界区块,但到目前为止我还没有有效的方法来对多边形的"内部"进行栅格化(也可能是凹形的).到目前为止,我的方法是将图块范围限制为包括多边形的矩形,然后使用多边形缠绕算法确定每个图块中心是位于内部还是外部.这样做效率很低,因为它涉及检查每个图块的每个多边形边界线段.从第一个角度来看,肯定应该有一个更快的方法,例如...... 比如使用光栅边界缠绕.是否有一个标准算法可以解决这个问题,甚至可能是C++中的库实现？

Answer 1

网上有相当多的资源,例如:

• C代码样本的高效多边形填充算法 ;