README.md

approx_draw

Web app that recreates an image using rectangles.

This uses a very simple hill-climbing algorithm to randomly place rectangles on a canvas, in a way which iteratively builds up an approximation of an image.

Algorithm

current approximation = empty canvas
for NUM_ITERATIONS
  for NUM_RECTANGLES_PER_ITERATION
    Generate a random_rectangle.
    Calculate the score of (current approximation + random_rectangle).
    if score is better than current best score from this iteration:
      best_score = score
      best_rectangle = random_rectangle
  current approximation += best rectangle.
display current approximation

The score is calculated like so:

score(approximate_img, target_img):
  score = 0
  for pixel, target_pixel in approximate_img, target_img
    score += abs(target_pixel.r - pixel.r)
    score += abs(target_pixel.g - pixel.g)
    score += abs(target_pixel.b - pixel.b)
  return score

Its performance is O(IRP), where I is iterations, R is rectangles per iteration, and P is pixels in the image. This suggests that if you want a good render, try downscaling your image first! I've gotten good results with images under 200x200 pixels.

Demo

To-do

• Make GIFs that show the images being built up, rectangle by rectangle
• Optimise the server code - why is the JS version twice as fast as the Go version?
• Resize large images