#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<png.h>

#define REGION_COUNT 50

static int DistanceSquared(int ax, int ay, int bx, int by)
{
   int dx = bx - ax;
   int dy = by - ay;
   return dx * dx + dy * dy;
}

int main(int argc, char **argv)
{
   int seed_point[REGION_COUNT][2];
   png_image image;
   png_bytep buffer1, buffer2;
   int s, i, j, x, y, px, py, offset, step, c_current, c_neighbor, *pixel;

   if( argc != 4 )
      return printf("%s <input.png> <output1.png> <output2.png>\n", *argv);

   memset(&image, 0, sizeof(image));
   image.version = PNG_IMAGE_VERSION;
   if( !png_image_begin_read_from_file(&image, argv[1]) )
      return printf("Error reading %s\n", argv[1]);

   image.format = PNG_FORMAT_RGBA;
   s = image.width * image.height;
   buffer1 = (png_bytep)malloc(s * 4);
   buffer2 = (png_bytep)calloc(s, 4);
   if( buffer1 == NULL || buffer2 == NULL )
      return puts("Out of memory");
   if( !png_image_finish_read(&image, NULL, buffer1, 0, NULL) )
      return printf("Error loading %s\n", argv[1]);

   srand(time(NULL));

   /* Initialize seed points. */
   pixel = (int*)buffer2;
   for(i = 0; i < REGION_COUNT; i++)
   {
      /* Prefer points that are distinct, but give up after finite number
         of tries.                                                        */
      for(j = 0; j < 99; j++)
      {
         x = (int)((double)rand() / (RAND_MAX + 1u) * image.width);
         y = (int)((double)rand() / (RAND_MAX + 1u) * image.height);
         if( pixel[offset = y * image.width + x] == 0 )
            break;
      }
      pixel[offset] = i + 1;
      seed_point[i][0] = x;
      seed_point[i][1] = y;
   }

   /* Generate voronoi coloring using jumping flood algorithm.
      https://en.wikipedia.org/wiki/Jump_flooding_algorithm    */
   for(step = 1;
       step * 2 < (int)image.width && step * 2 < (int)image.height; step *= 2);
   for(; step >= 1; step /= 2)
   {
      for(y = offset = 0; y < (int)image.height; y++)
      {
         for(x = 0; x < (int)image.width; x++, offset++)
         {
            /* Skip uncolored pixel. */
            c_current = pixel[offset];
            if( c_current == 0 )
               continue;

            for(i = -step; i <= step; i += step)
            {
               py = y + i;
               if( py < 0 || py >= (int)image.height )
                  continue;
               for(j = -step; j <= step; j += step)
               {
                  px = x + j;
                  if( px < 0 || px >= (int)image.width )
                     continue;

                  c_neighbor = pixel[py * image.width + px];
                  if( c_neighbor == 0 )
                  {
                     /* Neighbor pixel is not colored yet, propagate
                        color of current pixel.                      */
                     pixel[py * image.width + px] = c_current;
                  }
                  else
                  {
                     /* Neighbor pixel is already colored, overwrite
                        with current pixel color if current seed pixel
                        is closer.                                     */
                     if( DistanceSquared(px,
                                         py,
                                         seed_point[c_neighbor - 1][0],
                                         seed_point[c_neighbor - 1][1]) >
                         DistanceSquared(px,
                                         py,
                                         seed_point[c_current - 1][0],
                                         seed_point[c_current - 1][1]) )
                     {
                        pixel[py * image.width + px] = c_current;
                     }
                  }
               }
            }
         }
      }
   }

   /* Move pixels. */
   for(i = 0; i < s; i++)
   {
      if( (double)rand() / RAND_MAX * REGION_COUNT > pixel[i] )
      {
         memcpy(buffer2 + (i * 4), buffer1 + (i * 4), 4);
         memset(buffer1 + (i * 4), 0, 4);
      }
   }

   if( !png_image_write_to_file(&image, argv[2], 0, buffer1, 0, NULL) )
      return printf("Error writing %s\n", argv[2]);
   if( !png_image_write_to_file(&image, argv[3], 0, buffer2, 0, NULL) )
      return printf("Error writing %s\n", argv[3]);

   return 0;
}