Composition à la Mondrian
An extended comment follows. Mondrian, in the late work referenced by the OP and characterized by primary colored rectangles separated by black lines, employed an extraordinarily sophisticated understanding of perception, color, and light.
As background to understand what Mondrian does, I recommend The Interaction on Color, by Joseph Albers and Alfred C. Barnes's, The Art in Painting.
The Albers book shows how one color affects another color. For instance, place two equally sized rectangles of two primary colors (red and blue) on a white page and the red will appear to come forward and the blue to recede. Varying the size, hue, saturation, and placement of the two rectangles relative to each other and to their position on the page can change an observer's perception of the relationship of the illusion. One can even make the red recede!
You can play with this bit of code to try it:
Row[{
Graphics[{Red, Rectangle[{0, -1}, {2, 1}]}, ImageSize -> 200],
" ",
Graphics[{Darker[Darker[Blue]], Rectangle[{0, -1}, {2, 1}]},
ImageSize -> 200]}]
The Albers book does a much better job of illustrating the point.
The Barnes book and even his collection displayed at the Barnes Foundation in Philadelphia, presents his deep thinking on the ideas that Albers illustrates. Barnes identifies a long tradition in painting that has has long explored these questions. (Note that the Barnes collection precedes Albers's work by a couple of generations).
Painters from Georgione followed by his student Titian followed by his student El Greco, followed in Spain by Velazquez, followed by Goya, followed by Renoir and the impressionists they influenced explored these ideas and communicated them in an unbroken line from the 1400s to the present day. A handful of painters, like Rembrandt, made their own contributions to this dialogue when they discovered these painters, paintings, and their line of inquiry and discovery.
All of this affects our perception of the world. What we see, indeed what our vision equips us to see, can often - if not always - contradict what we know of the world from moving through it. Painters and Mondrian himself endeavored to understand these paradoxes and employ what they learned in their work.
Titian used this to supply an observer of one of his paintings with the equivalent of what they would observe in nature. A kind of primary presentation of the visual data facts, which an observer's brain would recognize as equivalent to what they might see in the real world so that their brain would process the information in the same or a similar way as observing the real world. Look closely at a Titian and one will often see odd contradictions such as something that one know sits behind something physically painted on top of it.
Response to @belisarius's comment. I didn't have an image readily available from Titian, but I think this one from Velazquez (a great lover of Titian's work, he traveled to Italy to study them) illustrates the idea:
In the middle of the 3 images of the portrait, I've outlined two areas where Velazquez has actually painted the background physically on top (a top layer of paint) over the foreground image. In the left representation, I've circled a bravura red/pink brush stroke, which Velazquez added as likely his very last stroke on the painting. That warm reddish color pulls the entire left side of the picture forward to balance the prominence of the central figure. In this Velazquez has made precisely the same kinds of choices based on the interaction and relationship of color that Mondrian does. Without these "contradictions" to what we know of the world from moving through it, the figure would appear lost in a vacuum. Among other things Velazquez has managed to convey the volume of space between the observer and the observed. Velazquez (and Mondrian) sees all as light. Background and foreground all in the eye at once. For him material has/is light/color. One can see this Portrait of Juan de Pareja in person at NY's Metropolitan Museum of Art.
Lesser painters who don't understand these ideas render what they think they know rather than the unfiltered data. Their paintings will often appear cartoonish or just dead when compared to those of painters who have thought about all of this.
In his late work, Mondrian, like any good scientist or mathematician reduces these ideas to a model, an abstraction in which he can explore and better understand them.
Consider this sequence of paintings that span his entire career...
One can see Mondrian reducing his model - abstracting his understanding of perception.
Look closely at an actual painting and one can see how Mondrian has labored to adjust the size and color of all of the different rectangles. Each of these paintings took months to create. In almost all of these late works, Mondrian balances each element of the pictures so that they all hover perceptually on the same plane (something which color in the real world does irrespective of what we "know" about the location of the objects it defines.)
It is truly brilliant work in both the realm of art and science.
All of this goes to thinking about what one really needs to understand to create an algorithm that might produce a Mondrian that Mondrian didn't get around to painting.
One last thing maybe worth illustrating, offered without further comment:
Piet Mondrian: Composition in grey and brown with overlay.
A couple more last things - links to journal articles about Mondrian that may prove interesting:
Divisions of the Plane by Computer: Another Way of Looking at Mondrian's Nonfigurative Compositions, by L. M. G. Feijs
and
Mondrian's Search for Geometric Purity: Creativity and Fixation, by Bennet Simon.
20 June 2016 (NOT 2015;-) Update ...
In New York, the Metropolitan Museum of Art's new Breuer location at 74th & Madison Ave. has an exhibition based on the idea of "unfinished" paintings.
The show displayed 2 very interesting late Mondrian works:
The paintings show early stages of the kinds of paintings that inspired the OP's questions. I find the first particularly interesting as Mondrian, begins the "painting" with masking tape thumb tacked to the canvass. Mondrian's equivalent of a Manipulate model to explore possibilities.
This is a similar idea to ybeltukov's, iteratively splitting rectangles into two smaller rectangles. I've used an integer grid to avoid getting small offsets between adjacent blocks, and a weighted random choice to decide whether to split horizontally or vertically or do nothing. The idea is that long thin rectangles should preferentially be split along the long axis.
splitx[Rectangle[{x0_, y0_}, {x1_, y1_}]] :=
Module[{a = RandomInteger[{x0 + 1, x1 - 1}]},
{Rectangle[{x0, y0}, {a, y1}], Rectangle[{a, y0}, {x1, y1}]}]
splity[Rectangle[{x0_, y0_}, {x1_, y1_}]] :=
Module[{a = RandomInteger[{y0 + 1, y1 - 1}]},
{Rectangle[{x0, y0}, {x1, a}], Rectangle[{x0, a}, {x1, y1}]}]
f = ReplaceAll[
r : Rectangle[{x0_, y0_}, {x1_, y1_}] :>
RandomChoice[{(x1 - x0)^2, (y1 - y0)^2, 5} -> {splitx, splity, Identity}] @ r];
cols = MapThread[Darker,
{{Black, White, Yellow, Red, Blue}, {0, 0.1, 0.1, 0.15, 0.3}}];
Graphics[{EdgeForm @ Thickness[0.012], {FaceForm @ RandomChoice @ cols, #} & /@
Flatten @ Nest[f, Rectangle[{0, 0}, {20, 20}], 6]},
AspectRatio -> 0.7]
Here is my attempt to be Piet Mondrian
colors = {RGBColor[0.9, 0.9, 0.9], RGBColor[0.05, 0.05, 0.05],
RGBColor[0.8, 0.1, 0.1], RGBColor[0.1, 0.1, 0.5], RGBColor[0.9, 0.7, 0.1]};
split = # /. d : Rectangle[{x1_, y1_}, {x2_, y2_}] :>
With[{t = RandomReal@BetaDistribution[10, 10], r = Random[]}, Which[
r < 0.3 (x2 - x1)/(y2 - y1),
{Rectangle[{x1, y1}, {x1 + (x2 - x1) t, y2}],
Rectangle[{x1 + (x2 - x1) t, y1}, {x2, y2}]},
1 - r < 0.5 (y2 - y1)/(x2 - x1),
{Rectangle[{x1, y1}, {x2, y1 + (y2 - y1) t}],
Rectangle[{x1, y1 + (y2 - y1) t}, {x2, y2}]},
True, d]] &;
Nest[split, #, 7] &@ Graphics[{EdgeForm@{Thickness[1/150], RGBColor[0.05, 0.05, 0.05]},
Rectangle[{0., 0.}, {1.4, 1.}]}, ImageSize -> 700] /.
r_Rectangle :> {RandomChoice@colors, r} /. x_Real :> Round[x, 0.05]
Here is some tweaks with random numbers to obtain more uniform splitting. Then one can easily rasterize the result. By default antialiasing is disabled and lines will be perfectly aligned to pixels like in the above image.
Update: nice Rahul Narain's colors and aligning boundaries by rounding of the coordinates.