Challenge II: Great patron of Art - Deadline 28.11. 9:00 AM

Being a great patron of art, PhD Luukkainen has also several famous painting exhibitions all over Finland. The El Prado Museum in Madrid has made a request to PhD Luukkainen for one of his exhibitions to be shown in their galleries, and Luukkainen was happy to oblige. Of course, the originals will be kept safely in Finland, and a set of digitalized copies will be sent to Spain instead. To accommodate El Prado's other highlights, PhD Luukkainen has asked you to produce an algorithm to "picassofy" the paintings first.

The objective is to "triangulate" the images given below, by creating an image file that looks like the original (to a certain extent), but is completely made out of semi-transparent triangles.

Here's an example triangulation that uses 30 triangles. Left hand side: original stolen by PhD Luukkainen, right hand side: picassofied.

Each painting will have a distinct number of triangles you are allowed to use, and the quality of your painting is calculated by the distance of the pixels between the original and yours using the following formula:

e.g. distance(picassofied, original) = sum over all pixels (euclidean distance of pixel n in images picassofied and original)

We will support you with source code to calculate the distance.  The pixel coordinates of the picture are positive integers (though it is possible to assign negative values to the points, which then are painted outside of the picture), with left bottom corner being the origo.

File format

The file format returned is the listing of used triangles. First two lines consists of preamble:

W H
N

where W is the width of the picture (in pixels), H is the height od the picture (in pixels) and N is the number of triangles listed below. After the preamble comes the list of triangles in the following format:

1stdot_x 1stdot_y 2nddot_x 2nddot_y 3rddotx_3rddot_y R G B alpha

where the dot_x and dot_y represent the x and y coordinates of one of the points in the triangle, R, G and B the color-value of the triangle (255,255,255 for white
etc.) and alpha the opacity of the triangle as integer (255 for 100%, 0 for 0% etc). Each field is separated by space, each triangle by line break. The alpha blending is done using the following formula:

Example of triangle format:

100 100
1
10 10 46 10 28 41 255 255 0 255

Draws an approximately even-sided yellow triangle starting from x10 y10, pointing upwards:

Your answer should include the source code and the produced picture in the format described above.

Sample code

Example code with which you can transform and rasterize triangle format pictures in C++:
http://www.cs.helsinki.fi/u/pjmikkol/aicha.tar.gz

Same code ported to Java:
http://www.cs.helsinki.fi/u/avihavai/aicha/challenge-2.zip

In this task we give reference code to Java and C++, but of course you are free to use any language you want. If you want to use some different language the
options are:
1) Port one of the given tools to the language of your choice
2) Use given tools as an external programs for rasterization and scoring
3) Roll your own tools
If choosing an option 3, remember to validate that your programs rasterize the pictures exactly in the same way as the reference implementations since it affects to the scoring. Note that if you want to use C it is almost enough to just compile your code with supported tools using C++-compiler.

Material

Book: Clever Algorithms (there's a free PDF!)
Buzzwords: Greedy Algorithm, Simulated Annealing, Genetic Algorithm

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Data

You have to triangulate the following images:

http://www.cs.helsinki.fi/u/avihavai/aicha/exactum.tga (40) -- reference score: 9012828
http://www.cs.helsinki.fi/u/avihavai/aicha/lenna.tga (50) -- reference score: 9108126
http://www.cs.helsinki.fi/u/avihavai/aicha/luukkainen.tga (20) -- reference score: 844761
http://www.cs.helsinki.fi/u/avihavai/aicha/michelangelo.tga (70) -- reference score: 9618550
http://www.cs.helsinki.fi/u/avihavai/aicha/ronsu.tga (60) -- reference score: 10326042
http://www.cs.helsinki.fi/u/avihavai/aicha/tux.tga (30) -- reference score: 3055625

Task

Implement an algorithm that creates triangle based estimations of an image, and outputs the estimation in the triangle data format. There are 6 images you need to estimate. For each image, you need to provide a version with the given triangle count. In addition, you need to provide a version for each with 100 triangles.

You should be able to beat the reference scores with your approach. If not, you can still proceed to the next challenge if you provide a good enough explanation of your tried approaches.

Submission

The submissions are done using triangle-format files, and sent to the submission service. When submitting triangle files, attach your solution source code as well as the description of the approach.

Additional notes

• The background color for the image is always white in the beginning.
• Triangles can be set larger than the image (this means that you can paint a background with a single image).
• Produced pictures (or triangle format files) must have the same dimensions as the original pictures (e.g. width and height must be the same).
• Function getAvgColorAsRgba in the sample code returns the average color of all the pixels covered by the triangle.
• Function for calculating distance can be found in the Picture-class.