Domination is a small tool to create domino pictures.
Introduction
Domination creates a picture consisting of complete domino sets by looking for a best possible approximation using dominos of different grayscale values using mathematical programming.
Description
A domino picture is a picture that is formed by arranging domino pieces in a plane. We assume that all dominos have a white background and black dots from 0 to 9. Therefore a 9 appears very dark whereas as zero appears light. Domination uses k complete domino sets where a complete set is one containing each possible domino exactly once (i.e. one piece with (0,0), one with (0,1) ... one with (9,9); 55 pieces in total).
Domination formulates a MILP (mixed integer linear programming) model that looks for the best feasible arrangement of the dominos a n × m grid (where n·m must be a multiple of 110 so that the number of pixels corresponds to a certain number of complete domino sets). The constraints ensure that each pixel is covered by exactly one domino, no two dominos overlap. The objective function assigns a value to each possible possition and orientation of a domino such that the value correponds to the (quadratic) difference of the dominos two darkness values and the grayscale value of the source image.
A description of the approach and the used model can be found on this poster (in German).
Solution approach
The model is implemented and solved using the mixed integer programm solver Gurobi. Gurobi is access through the FreePascal package LPMod
User interface
The user interface is written in Lazarus/Free Pascal and accepts pictures by drag and drop and selecting a certain area from the picture to be converted. The user can then compute a domino picture and export the picture in pdf or svg format or print it directly.
Download
Latest release: domination-1.0.1.tar.gz
Latest development version: domination-trunk.tar.gz
Contact
Please send an email to frank2.fischer at tu-dortmund.de.