Tweetable mathematical art: Voronoi diagrams

My second participation to the challenge Tweetable mathematical art.

Random Voronoi diagram generator anyone?

OK, this one gave me a hard time. I think it’s pretty nice though, even if the results are not so arty as some others. That’s the deal with randomness. Maybe some intermediate images look better, but I really wanted to have a fully working algorithm with voronoi diagrams.

Edit:

This is one example of the final algorithm. The image is basically the superposition of three voronoi diagram, one for each color component (red, green, blue).

Code

ungolfed, commented version at the end

unsigned short red_fn(int i, int j){
int t[64],k=0,l,e,d=2e7;srand(time(0));while(k<64){t[k]=rand()%DIM;if((e=_sq(i-t[k])+_sq(j-t[42&k++]))<d)d=e,l=k;}return t[l];
}

unsigned short green_fn(int i, int j){
static int t[64];int k=0,l,e,d=2e7;while(k<64){if(!t[k])t[k]=rand()%DIM;if((e=_sq(i-t[k])+_sq(j-t[42&k++]))<d)d=e,l=k;}return t[l];
}

unsigned short blue_fn(int i, int j){
static int t[64];int k=0,l,e,d=2e7;while(k<64){if(!t[k])t[k]=rand()%DIM;if((e=_sq(i-t[k])+_sq(j-t[42&k++]))<d)d=e,l=k;}return t[l];
}

It took me a lot of efforts, so I feel like sharing the results at different stages, and there are nice (incorrect) ones to show.

First step: have some points placed randomly, with x=y

I have converted it to jpeg because the original png was too heavy for upload (>2MB), I bet that’s way more than 50 shades of grey!

Second: have a better y coordinate

I couldn’t afford to have another table of coordinates randomly generated for the y axis, so I needed a simple way to get “ random “ ones in as few characters as possible. I went for using the x coordinate of another point in the table, by doing a bitwise AND on the index of the point.

3rd: I don’t remember but it’s getting nice

But at this time I was way over 140 chars, so I needed to golf it down quite a bit.

4th: scanlines

Just kidding, this is not wanted but kind of cool, methinks.

Still working on reducing the size of the algorithm, I am proud to present:

StarFox edition

Voronoi instagram

5th: increase the number of points

I have now a working piece of code, so let’s go from 25 to 60 points.

That’s hard to see from only one image, but the points are nearly all located in the same y range. Of course, I didn’t change the bitwise operation, &42 is much better:

And here we are, at the same point as the very first image from this post. Let’s now explain the code for the rare ones that would be interested.

Ungolfed and explained code

unsigned short red_fn(int i, int j)
{
    int t[64],          // table of 64 points's x coordinate
        k = 0,          // used for loops
        l,              // retains the index of the nearest point
        e,              // for intermediary results
        d = 2e7;        // d is the minimum distance to the (i,j) pixel encoutnered so far
        // it is initially set to 2e7=2'000'000 to be greater than the maximum distance 1024²

    srand(time(0));     // seed for random based on time of run
    // if the run overlaps two seconds, a split will be observed on the red diagram but that is
    // the better compromise I found

    while(k < 64)       // for every point
    {
        t[k] = rand() % DIM;        // assign it a random x coordinate in [0, 1023] range
        // this is done at each call unfortunately because static keyword and srand(...)
        // were mutually exclusive, lenght-wise

        if (
            (e=                         // assign the distance between pixel (i,j) and point of index k
                _sq(i - t[k])           // first part of the euclidian distance
                +
                _sq(j - t[42 & k++])    // second part, but this is the trick to have "" random "" y coordinates
                // instead of having another table to generate and look at, this uses the x coordinate of another point
                // 42 is 101010 in binary, which is a better pattern to apply a & on; it doesn't use all the table
                // I could have used 42^k to have a bijection k <-> 42^k but this creates a very visible pattern splitting the image at the diagonal
                // this also post-increments k for the while loop
            ) < d                       // chekcs if the distance we just calculated is lower than the minimal one we knew
        )
        // {                            // if that is the case
            d=e,                        // update the minimal distance
            l=k;                        // retain the index of the point for this distance
            // the comma ',' here is a trick to have multiple expressions in a single statement
            // and therefore avoiding the curly braces for the if
        // }
    }

    return t[l];        // finally, return the x coordinate of the nearest point
    // wait, what ? well, the different areas around points need to have a
    // "" random "" color too, and this does the trick without adding any variables
}

// The general idea is the same so I will only comment the differences from green_fn
unsigned short green_fn(int i, int j)
{
    static int t[64];       // we don't need to bother a srand() call, so we can have these points
    // static and generate their coordinates only once without adding too much characters
    // in C++, objects with static storage are initialized to 0
    // the table is therefore filled with 60 zeros
    // see http://stackoverflow.com/a/201116/1119972

    int k = 0, l, e, d = 2e7;

    while(k<64)
    {
        if( !t[k] )                 // this checks if the value at index k is equal to 0 or not
        // the negation of 0 will cast to true, and any other number to false
            t[k] = rand() % DIM;    // assign it a random x coordinate

        // the following is identical to red_fn
        if((e=_sq(i-t[k])+_sq(j-t[42&k++]))<d)
            d=e,l=k;
    }

    return t[l];
}