Scanline Fill Algorithm in Python/Numpy
image-processing, numpy, python
Solution
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.
Problem
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?