/* Voronoi diagram generator, using jumping flood algorithm.
   https://en.wikipedia.org/wiki/Jump_flooding_algorithm

   ./voronoi <width> <height> > output.pgm
                                                             */
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#ifdef _WIN32
   #include<fcntl.h>
   #include<io.h>
#endif

#define POINT_COUNT     25

#define COLOR(index)    (((index) + 1) * 255 / POINT_COUNT)


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 width, height, step, x, y, px, py, i, j, c_current, c_neighbor;
   int point[POINT_COUNT][2], d_current, d_neighbor;
   unsigned char *pixels;

   assert(POINT_COUNT > 0);
   assert(POINT_COUNT <= 254);

   if( argc != 3 ||
       (width = atoi(argv[1])) <= 0 ||
       (height = atoi(argv[2])) <= 0 )
   {
      return printf("%s <width> <height>\n", *argv);
   }
   if( width >= 0x8000 || height >= 0x8000 )
      return !puts("Output size too large.");

   if( (pixels = (unsigned char*)calloc(width * height, 1)) == NULL )
      return !puts("Not enough memory");

   #ifdef _WIN32
      setmode(STDOUT_FILENO, O_BINARY);
   #endif

   srand(time(NULL));

   /* Generate random points locations and also mark seed positions. */
   for(i = 0; i < POINT_COUNT; i++)
   {
      /* We would like all seed locations to be unique, but there is some
         chance that we can't pick all unique locations if output area is
         too small, so we give up after finite number of attempts.        */
      for(j = 0; j < 128; j++)
      {
         x = (int)((double)rand() / (RAND_MAX + 1u) * width);
         y = (int)((double)rand() / (RAND_MAX + 1u) * height);
         if( pixels[y * width + x] == 0 )
            break;
      }

      pixels[y * width + x] = i + 1;
      point[i][0] = x;
      point[i][1] = y;
   }

   /* Set initial step size to be largest power of 2 that is
      half of the long edge length.                          */
   for(step = 1; step * 2 < width && step * 2 < height; step *= 2);

   /* Apply jump flooding. */
   for(; step >= 1; step /= 2)
   {
      for(y = 0; y < height; y++)
      {
         for(x = 0; x < width; x++)
         {
            /* Skip current pixel if it's not colored yet. */
            c_current = pixels[y * width + x];
            if( c_current == 0 )
               continue;

            for(i = -step; i <= step; i += step)
            {
               py = y + i;
               if( py < 0 || py >= height )
                  continue;
               for(j = -step; j <= step; j += step)
               {
                  px = x + j;
                  if( px < 0 || px >= width || (i == 0 && j == 0) )
                     continue;
                  c_neighbor = pixels[py * width + px];
                  if( c_neighbor == 0 )
                  {
                     /* Neighbor pixel is not colored yet, propagate
                        color of current pixel there.                */
                     pixels[py * width + px] = c_current;
                  }
                  else
                  {
                     /* Neighbor pixel is already colored.  If neighbor
                        pixel is closer to the seed pixel of current
                        pixel, use current pixel color.                 */
                     d_neighbor = DistanceSquared(
                        px, py,
                        point[c_neighbor - 1][0], point[c_neighbor - 1][1]);
                     d_current = DistanceSquared(
                        px, py,
                        point[c_current - 1][0], point[c_current - 1][1]);
                     if( d_neighbor > d_current )
                        pixels[py * width + px] = c_current;
                  }
               }
            }
         }
      }
   }

   /* Write pixels. */
   printf("P5\n%d %d\n255\n", width, height);
   for(i = 0; i < width * height; i++)
      fputc(COLOR(pixels[i]), stdout);
   free(pixels);
   return 0;
}