Алгоритм заливки Scanline в Python/Numpy

Question

У меня есть тысячи полигонов с учетом их четырех угловых координат (quadrilaterals) и хотели бы преобразовать их в растровое представление в виде массива numpy 2d. Существует множество алгоритмов грида, таких как популярное сканирование в графике. (см. http://www.cs.rit.edu/~icss571/filling/how_to.html или http://cs.uvm.edu/~rsnapp/teaching/cs274/lectures/scanlinefill.pdf)

Октав реализует это в функции poly2mask (например, http://octave.sourceforge.net/image/function/poly2mask.html).

Есть ли аналогичная функция также в Numpy? Я до сих пор не понимаю, как эти алгоритмы работают подробно, и, таким образом, я был бы очень благодарен, если бы вы могли дать мне несколько советов о том, как эффективно реализовать его в Python/Numpy.

Или было бы лучше закодировать его в CPython (с которым я тоже не знаком) по причинам скорости?

Answer 1

Есть несколько различных функций для этого в SciPy экосистемы (не в порядке):

1) Наиболее широко доступный вариант заключается в использовании Matplotlib-х points_inside_poly. Тем не менее, он очень субоптимален для заполнения регулярной сетки (т. Е. Это явная точка в полигоне, а не подходом «scanline»).

2) mahotas реализует fill_polygon функцию, которая довольно эффективно: http://mahotas.readthedocs.org/en/latest/polygon.html#drawing

3) skimage (scikits-изображение) реализует 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 проект также имеет полигональную функцию заливки: cv2.fillPoly