Scanline Fill Algorithm in Python/Numpy

Question

I have thousands of polygons given their 4 corner coordinates (quadrilaterals) and would like to convert them to a raster representation as a numpy 2d array. A lot of gridding algorithms exist like the popular scanline fill in graphics. (see http://www.cs.rit.edu/~icss571/filling/how_to.html or http://cs.uvm.edu/~rsnapp/teaching/cs274/lectures/scanlinefill.pdf )

Octave implements this in the poly2mask function (e.g. http://octave.sourceforge.net/image/function/poly2mask.html).

Is there a similar function also in Numpy? I still don't get how this algorithms works in detail and, thus, I would be very grateful if you can give me some hints on how to implement it in Python/Numpy efficiently.

Or would it be better to code it in CPython (which I am not familiar with either) for speed reasons?

Answer 1

There are a few different functions for this in the scipy ecosystem (in no order):

1) The most widely-available option is to use matplotlib's points_inside_poly. However, it's very suboptimal for filling a regular grid (i.e. it's an explicit point in polygon test, rather than a "scanline" approach).

2) mahotas implements a fill_polygon function that's quite efficient: http://mahotas.readthedocs.org/en/latest/polygon.html#drawing

3) skimage (scikits-image) implements a draw.polygon function that should be at least as efficient, if not more so: http://scikit-image.org/docs/dev/api/skimage.draw.html#skimage.draw.polygon

4) Finally, you can also use PIL for this and convert the image to a numpy array. Have a look at the ImageDraw module: http://effbot.org/imagingbook/imagedraw.htm

Overally, I'd reccommend installing skimage and using it. It's a very useful library. However, if you can't install scikits image for some reason, the other options should help.