Ratio between surface area on either side of a line's own supercover Let's say we have a line on a raster that goes from any position on any edge to any other edge:

And take its supercover:

We now have a polygon that is cut in 2 by a line, intuitively it seems that it should be possible to find the surface area on either side of the line in constant time but I can't seem to figure it out, using linear time I can of course just consider each cell.
Can anybody point me in the right direction?
 A: It looks difficult, if not impossible, to do in constant time.
I think it can be done in linear time by number of rows (or by number of columns if that is smaller) rather than number of cells though. I'll describe the procedure rather than give actual formulas.
Look at the smallest rectangle containing the supercover. In the example, this has $2$ rows and $6$ columns. Start by calculating the area inside it on one side of the line. Depending on the location of the $2$ endpoints, this area will be one of:


*
 
*a triangle
 
*a triangle and one rectangular strip
 
*a triangle and two rectangular strips.


In your example, the lower side is Type 1 and the upper side is Type 3.
From this value you need to subtract the area of some number of whole cells. Iterate through each row or column (whichever way gives the least number of loops) and calculate the number of cells to remove in that row/column, then subtract that from the total area. In your example, for the lower side, there should be $2$ iterations (because we have $2$ rows) removing $2$ cells; for the upper side: $2$ iterations removing $3$ cells.
In doing these calculations, it might help to firstly re-orient the line (rotating $90^o$ or $180^o$ or $270^o$ or reflecting it, etc.), to convert rows to columns and to have the line always sloping up rather than down. Then you can always iterate along the $y$-axis from bottom to top, for example (or whichever way you prefer it).
