I’ve refined image approximations with rectangles and triangles. Let’s try with splitting regions into two with a straight line, and filling each part with the average color that they’re covering.
This is the same basic idea as the rectangles, except that now the line can be at any angle, rather than just vertical or horizontal. It tries to find the position and angle of the line that minimizes the error. I got this working before I had read Binary Space Patritioning, by Hayder Radha, but he got there first and did it rigorously!
As he notes in his paper, it’s expensive to check every possible line, so we’ll feed it to a function minimizer, which will apply some magic and spit out a good guess of the optimal line. Then we check the new error levels, and split the new polygons if necessary. Repeat until convergence! Here’s an animation:
And examples of different error levels:
Compared to the rectangles, it uses about 2x the number of shapes to get to the same error level for this image. The triangles use 4x the number of shapes, so this is a nice intermediate.
Have some more examples:
Three angles 
Four angles 
Mollusk angles 
Works well for angular images