/* Generate voronoi diagrams */
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define HEIGHT 1024
#define WIDTH 1024
#define COLOR_MAX 255
#define COLOR_VAR 64
#define SEED_COUNT 64
#define SEED_MARKER 4

#define CHUNK_SIZE (16 * (WIDTH * HEIGHT) / (SEED_COUNT * SEED_COUNT))

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))

#ifndef d
#define d euclid
#endif

typedef struct {
  uint8_t r;
  uint8_t g;
  uint8_t b;
} Color;

typedef struct {
  size_t x;
  size_t y;
} Point;

static const Color SEED_COLOR = {0x30, 0x30, 0x30};

static const Color PALETTE[] = {
    {0x7f, 0xc9, 0x7f},
    {0xbe, 0xae, 0xd4},
    {0xfd, 0xc0, 0x86},
    {0x38, 0x6c, 0xb0},
};
#define PALETTE_COUNT (sizeof(PALETTE) / sizeof(PALETTE[0]))

static int ppm(FILE *f, const Color img[HEIGHT][WIDTH]) {
  if (!f) {
    perror("failed to create ppm");
    return -1;
  }

  fprintf(f, "P6 %d %d %d\n", WIDTH, HEIGHT, COLOR_MAX);
  if (fwrite(img, sizeof(Color), HEIGHT * WIDTH, f) != HEIGHT * WIDTH) {
    perror("failed to write file");
    return -1;
  };
  return 0;
}

/* Squared Euclidean */
static int euclid(Point p1, Point p2) {
  int dx = p1.x - p2.x;
  int dy = p1.y - p2.y;
  return dx * dx + dy * dy;
}

/* Manhattan */
static int manhattan(Point p1, Point p2) {
  int dx = p1.x - p2.x;
  int dy = p1.y - p2.y;
  return abs(dx) + abs(dy);
}

/* Chebyshev */
static int chebyshev(Point p1, Point p2) {
  int dx = p1.x - p2.x;
  int dy = p1.y - p2.y;
  return MAX(abs(dx), abs(dy));
}

static void rand_seeds(Point s[SEED_COUNT]) {
  for (size_t i = 0; i < SEED_COUNT; ++i) {
    s[i].x = rand() % WIDTH;
    s[i].y = rand() % HEIGHT;
  }
}

static void draw_marker(Point p, Color img[HEIGHT][WIDTH]) {
  for (size_t y = MAX(0, p.y - SEED_MARKER); y < MIN(p.y + SEED_MARKER, HEIGHT);
       ++y) {
    for (size_t x = MAX(0, p.x - SEED_MARKER);
         x < MIN(p.x + SEED_MARKER, WIDTH); ++x) {
      Point i = {x, y};
      img[y][x] = SEED_COLOR;
    }
  }
}

Color tint(Color c, Point p) {
  return (Color){
      .r = c.r + ((p.x + p.y) % COLOR_VAR - (COLOR_VAR / 2)) % COLOR_MAX,
      .g = c.g + ((p.x + p.y) % COLOR_VAR - (COLOR_VAR / 2)) % COLOR_MAX,
      .b = c.b + ((p.x + p.y) % COLOR_VAR - (COLOR_VAR / 2)) % COLOR_MAX,
  };
}

static void voronoi_brute(const Point seeds[SEED_COUNT],
                          Color img[HEIGHT][WIDTH]) {
  for (size_t y = 0; y < HEIGHT; ++y) {
    for (size_t x = 0; x < WIDTH; ++x) {
      size_t m = 0;
      Point p = {x, y};
      for (size_t s = 1; s < SEED_COUNT; ++s) {
        if (d(seeds[s], p) < d(seeds[m], p)) {
          m = s;
        }
      }
      img[y][x] = tint(PALETTE[m % PALETTE_COUNT], seeds[m]);
    }
  }
}

static void voronoi_depth(const Point seeds[SEED_COUNT],
                          Color img[HEIGHT][WIDTH]) {
  static int depth[HEIGHT][WIDTH];
  static Color tints[SEED_COUNT];
  for (size_t i = 0; i < SEED_COUNT; ++i) {
    tints[i] = tint(PALETTE[i % PALETTE_COUNT], seeds[i]);
  }

  for (size_t y = 0; y < HEIGHT; ++y) {
    for (size_t x = 0; x < WIDTH; ++x) {
      depth[y][x] = INT_MAX;
    }
  }

  for (size_t i = 0; i < SEED_COUNT; ++i) {
    Point s = seeds[i];
    for (size_t y = 0; y < HEIGHT; ++y) {
      for (size_t x = 0; x < WIDTH; ++x) {
        Point p = {x, y};
        int dd = d(p, s);
        if (dd < depth[y][x]) {
          depth[y][x] = dd;
          img[y][x] = tints[i];
        }
      }
    }
  }
}

static void voronoi_depth_chunked(const Point seeds[SEED_COUNT],
                                  Color img[HEIGHT][WIDTH]) {
  static int depth[HEIGHT][WIDTH];
  static Color tints[SEED_COUNT];
  for (size_t i = 0; i < SEED_COUNT; ++i) {
    tints[i] = tint(PALETTE[i % PALETTE_COUNT], seeds[i]);
  }

  for (size_t y = 0; y < HEIGHT; ++y) {
    for (size_t x = 0; x < WIDTH; ++x) {
      depth[y][x] = INT_MAX;
    }
  }

  for (size_t i = 0; i < SEED_COUNT; ++i) {
    Point s = seeds[i];
    for (size_t y = MAX(0, (int)s.y - CHUNK_SIZE);
         y < MIN(HEIGHT, s.y + CHUNK_SIZE); ++y) {
      for (size_t x = MAX(0, (int)s.x - CHUNK_SIZE);
           x < MIN(WIDTH, s.x + CHUNK_SIZE); ++x) {
        Point p = {x, y};
        int dd = d(p, s);
        if (dd < depth[y][x]) {
          depth[y][x] = dd;
          img[y][x] = tints[i];
        }
      }
    }
  }
}

int main(void) {
  srand(time(NULL));
  static Color data[HEIGHT][WIDTH];
  Point seeds[SEED_COUNT];
  rand_seeds(seeds);

  /* voronoi_brute(seeds, data); */
  /* voronoi_depth(seeds, data); */
  voronoi_depth_chunked(seeds, data);

  for (size_t s = 0; s < SEED_COUNT; ++s) {
    draw_marker(seeds[s], data);
  }

  if (ppm(stdout, data) != 0) {
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}