Python/Numpy中的扫描线填充算法

Question

我有数以千计的多边形给他们的4角坐标（四边形），并想把他们转换成一个光栅表示作为一个numpy二维阵列。 在网格填充算法中，存在着许多流行的网格填充算法。（见http://www.cs.rit.edu/~icss571/filling/how_to.html或http://cs.uvm.edu/~rsnapp/teaching/cs274/lectures/scanlinefill.pdf）

Octave在poly2mask函数中实现了这一点（例如http://octave.sourceforge.net/image/function/poly2mask.html）。在

Numpy中也有类似的功能吗？ 我仍然不知道这些算法是如何工作的，因此，如果您能给我一些提示，告诉我如何在Python/Numpy中高效地实现它，我将非常感激。在

或者，出于速度原因，用CPython（我也不熟悉）编写它会更好吗？在

Answer 1

在scipy生态系统中，有一些不同的功能（没有顺序）：

1）最常见的选择是使用matplotlib的^{}。然而，对于填充规则网格来说，这是非常不理想的（即，它是多边形测试中的一个显式点，而不是“扫描线”方法）。在

2）mahotas实现了一个非常高效的fill_polygon函数：http://mahotas.readthedocs.org/en/latest/polygon.html#drawing

3）skimage（scikits image）实现了一个draw.polygon函数，如果不是更有效的话：http://scikit-image.org/docs/dev/api/skimage.draw.html#skimage.draw.polygon

4）最后，您还可以使用PIL来实现这一点，并将图像转换为numpy数组。看看ImageDraw模块：http://effbot.org/imagingbook/imagedraw.htm

总的来说，我建议安装skimage并使用它。这是一个非常有用的图书馆。但是，如果由于某种原因无法安装scikits映像，其他选项应该会有所帮助。在

Answer 2

OpenCV项目还具有多边形填充功能：^{}