Assume I have a RGB bitmap image I. I want to get the average color of a number of random triangles with vertices A, B, and C. A, B, and C are all guaranteed to be within the bounds of image I, but are not guaranteed to be integer values. How do I get the average color of the triangular area? A dead simple way to get a rough estimate is to get the bounding box of the triangle, then iterate over each row, keeping a running tally of number of colored pixels and the total sums of each channel, then dividing at the end. (This also has the advantage of letting you precompute the sums of individual rows, which is useful with you have a very large number of triangles T to calculate.) However, this is most accurate for very large triangles; the smaller the triangles are, and the smaller the smallest angle in the triangle is, the more issues arise when pixels that are only partially within the triangle are undercounted or overcounted. A less simple way is to take that same bounding box; then for each pixel in the bounding box, calculate the area of each pixel that is also contained with the triangle; then, add the area of the pixel and the average color multiplied by the area of the pixel to the running total. However, creating a polygon for each and every pixel is impractically slow. While I am specifically looking for Pythonic answers and libraries that might have ways to implement it, about 90% of this will be finding the right algorithm, 10% will be implementing it. EDIT: Here is an illustration of some degenerate cases, involving small triangles straddling the boundaries of two areas of distinct colors, to illustrate the issues with the simple methods. For the sake of illustration, I have created an image which only uses two colors, magenta and blue, on a field 6 pixels tall and 16 pixels wide. Each one illustrates errors that come up with various sorts of approximations. If we simply count pixels whose center points are in the triangle, triangle A has an area of 12 (8 magenta, 4 blue), triangle B has an area of 2 (2 magenta), and triangle C has an area of 4 (3 magenta, 1 blue). This is obviously an incorrect estimation of both the total area of each triangle, as well as the proportion of magenta color to blue color in each triangle. If we count any portion of the pixel as being "in" the triangle, triangle A has an area of 19 (10 magenta pixels and 9 blue pixels), triangle B has an area of 8 (4 magenta pixels and 4 blue pixels), and triangle C also has an area of 8 (4 magenta pixels and 4 blue pixels). Despite triangles B and C having the same "area" when counting all pixels partially clipped by the triangle, the proportions of their areas are visibly distinct, and ought not have the same average color. If we count only pixels that are wholly contained within the triangle, triangle A has an area of 3 (2 magenta pixels and 4 blue pixels), and triangles B and C have an area of 0. This is grossly incorrect. There has to be a way to get the average color, even in cases such as these. Continue reading...
