About:

  1. "Rectangles" is a Computer Art Project.
  2. "Art", a noun, is, via the dictionary, with minor modification "the expression or application of human, or computer, creative skill and imagination, typically in a visual form such as painting or sculpture, producing works to be appreciated primarily for their beauty or emotional power."
  3. To create this art, a computer generates a "board" with randomly placed "obstacles". The computer then covers the board entirely, with colorful rectangles. The computer tries to do so using as few rectangles as possible.
  4. "Rectangles" is inspired by Code Combat's "Beat the Gridmancer" challenge.
  5. In their words: "In Gridmancer, you write an algorithm to cover the empty floor spaces in as few rectangles as possible. This is a real problem we had to solve in CodeCombat for both our pathfinding system and for our collision handling optimization system.".
  6. So, "Rectangles" is an art project that solves a real problem. Call it Applicable Computer Art Project then.
  7. Enjoy.

Notes:

  1. Implementation is in JavaScript with jQuery dependency for UI. It should work in all modern browsers. Annotated code is here. Note that computations are done when the page loads. By the time the interface says "Initializing...." everything was already solved. Sometimes better UX is slower UI.
  2. The "scanner" algorithm used here for finding the "fewest" rectangles to cover the board is fairly straightforward. It uses a three step process.
    • In the first step a "scanner" starts at the corner of the board. It finds an empty cell and then connects additional empty cells to that empty cell, thus forming a row of empty cells. It does so until it hits an obstacle. An obstacle can be one of the randomly placed ones, or a rectangle that has already been placed before. The "scanner" then tries to expand the created row adding additional rows below it, thus forming a rectangle. It does so until it hits an obstacle in that direction. Once an obstacle has been hit in both directions, the resulting rectangle is placed and the "scanner" looks for the next empty cell to cover.
    • In the second step the board is flipped, rotated, and both flipped and rotated. Step one "scan" is repeated for each new board position. This is equivalent to scanning from different directions.
    • The results yielded by the scans are evaluated and the one with the fewest number of rectangles is chosen for usage.
  3. In the Code Combat challenge blog post they discuss reducing the number of rectangles needed to cover their board from 33 to 29. These (as well as 30 and 31) are the results one would get using the algorithm described above for various board positions. To illustrate run this replica of the Gridmancer board.
  4. The term "fewest" used above is put in quotes. Why? Because while the algorithm can "scan" and find the "fewest" rectangles needed using different scan directions, the "scanner" method itself might miss a solution with fewer possible rectangles. To illustrate run this example where the "scanner" succeeds in finding the fewest rectangles, eight, to cover four T shaped open areas. Then, run this example where it fails to find the same solution for the same shaped areas, as they are placed differently related to each other.
  5. On StackOverflow there is a Computer Science discussion about designing an optimal algorithm for finding the fewest rectangles needed. It says: The idea is to find the maximum number of disjoint axis-parallel diagonals that have two concave vertices as endpoints, split along those, and then form one more split for each remaining concave vertex. To find the maximum number of disjoint axis-parallel diagonals, form the intersection graph of the diagonals; this graph is bipartite so its maximum independent set can be found in polynomial time by graph matching techniques.
  6. And that is sort of the difference between art and science :).
ver. 1.0, January 1st, 2014. By Yaron (Ron) Ilan. (@ronilan) MIT License