How to draw and fill a polygon on a grid array using pure Numpy functions?

Question

Here goes a difficult one for the expert Numpyer!

Does someone know or can come up with a way to use pure Numpy arrays and functions to draw as well as fill colored polygons on top of a numpy array grid?

This I think would take two steps:

1. The ability to fill the grid array with color values so that the polygon filling could be written in one color, and the outline in another one. What would be ideal and fastest for such a system, eg tuples of rgb values, color name strings, etc?
2. The ability to draw and fill the inside of a polygon based on an array of its pixel coordinates. Drawing the outline of it I think should be pretty easy by just using the coordinates as indexes to the grid array and setting them to the outline color values. More difficult would be to fill the polygon. One way would be to iterate through all pixel cell coordinates (or better yet only for the neighboring cells of each polygon coordinate point) and test if its coordinates are within the polygon pixel coordinates. I know there are some simple inside-outside/biggerthan-smallerthan algorithms to test for point in poly using regular Python, but for my purpose this would be too slow and I am wondering if someone has the numpy skills to set up such an advanced linked code using only the speed of the numpy builtin functions to return True if a numpy pixel coordinate is inside a polygon.
3. Lastly, if someone would know how to draw a line between two pixel/grid/array coordinates by filling in all the cells in between two pixels with a True or color value?

I know this is a tall order, but I was just curious to see if anyone would know. If so, then this could make for a pretty powerful and fast Numpy-based drawing library. In the end I would like to save the grid array as an image which is easy by passing it to PIL.

I am aware that PIL and Aggdraw can do the polygon drawings and that this has been suggested in many similar posts, but they are not very effective when receiving a numpy array of xy polygon/line coordinates. The assumption here is that my polygon coordinates are already in a numpy array format and I want to avoid the overhead of having to copy them into lists for every drawing (when we're talking about thousands of polygons frequently). So the difference in this post is about how to fill a polygon using pure Numpy.

Answer 1

In this case the point to achieve speed is more the used algorithms than the language of choice. Drawing and filling poligons rasterized over a grid of pixel falls into the domain of image processing algorithms and for sure AggDraw is using algorithms from that field.

The idea is that if you evaluate for each points a function that considers the vectorial nature of the polygon you need to do a number of operations that is at least O(2*p*A) where:

• A = image area
• p = average number of points in the perimeter of the polygons.

Conversely if you use image processing algorithms for each point you can consider to have a fixed and low number of operations. For example if you consider the FloodFill algorithm it is O(A) and I can say it is less than 30*A (about 30 operations per pixel).

So basically since the GADM polygons has many vertex is better to eliminate the vectorial nature of the problem as soon as possible and go with something like this:

1. construct the pixel map of the boundary
2. find one internal pixel
3. use the Floodfill algorithm that will work without any need to know about polygons as vectorial entities

The same algorithms can for sure be implemented in Numpy but before going for a Numpy graphical lib I would suggest to do the following:

• measure the time spent in your code for the various steps:
  • Numpy array to AggDraw lists/sequences conversion
  • time taken by AggDraw
• try to decimate the vertex of the polygons removing the ones that stay in the same pixel based on the current Zoom level and see if an how the times will be reduced