pd.if.org Git - hexagon/blob - hexagon.c

   1 #include "hexagon.h"
   2
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <limits.h>
   7
   8 static int inversecantor(int cantor, int *x, int *y);
   9
  10 /*
  11  * This file is written by Nathan Wagner and dedicated to the public
  12  * domain
  13  */
  14
  15 double HL_vertexv[12] = {
  16         .577350269189625764509148780502, 0.0,
  17         .288675134594812882254574390251, 0.5,
  18         -.288675134594812882254574390251, 0.5,
  19         -.577350269189625764509148780502, 0.0,
  20         -.288675134594812882254574390251, -0.5,
  21         .288675134594812882254574390251, -0.5};
  22
  23 double HL_fand[16] = {
  24         0.0, 0.0,
  25         .577350269189625764509148780502, 0.0,
  26         .288675134594812882254574390251, 0.5,
  27         -.288675134594812882254574390251, 0.5,
  28         -.577350269189625764509148780502, 0.0,
  29         -.288675134594812882254574390251, -0.5,
  30         .288675134594812882254574390251, -0.5,
  31         .577350269189625764509148780502, 0.0
  32 };
  33
  34 double HL_hfand[16] = {
  35         0.0, 0.0,
  36         0.0, .577350269189625764509148780502,
  37         0.5, .288675134594812882254574390251,
  38         0.5, -.288675134594812882254574390251,
  39         0.0, -.577350269189625764509148780502,
  40         -0.5, -.288675134594812882254574390251,
  41         -0.5, .288675134594812882254574390251,
  42         0.0, .577350269189625764509148780502
  43 };
  44
  45 float HL_fanf[16] = {
  46         0.0f, 0.0f,
  47         .577350269189625764509148780502f, 0.0f,
  48         .288675134594812882254574390251f, 0.5f,
  49         -.288675134594812882254574390251f, 0.5f,
  50         -.577350269189625764509148780502f, 0.0f,
  51         -.288675134594812882254574390251f, -0.5f,
  52         .288675134594812882254574390251f, -0.5f,
  53         .577350269189625764509148780502f, 0.0f
  54 };
  55
  56 float HL_hfanf[16] = {
  57         0.0f, 0.0f,
  58         0.0f, .577350269189625764509148780502f,
  59         0.5f, .288675134594812882254574390251f,
  60         0.5f, -.288675134594812882254574390251f,
  61         0.0f, -.577350269189625764509148780502f,
  62         -0.5f, -.288675134594812882254574390251f,
  63         -0.5f, .288675134594812882254574390251f,
  64         0.0f, .577350269189625764509148780502f
  65 };
  66
  67 /* size of a square that will exactly fit in a hexagon */
  68 /* 2.0/(1+sqrt(3.0)) */
  69 double HL_square = .73205080756887729352;
  70
  71 /* these all are for a hex one unit across */
  72 static double          hexptvd[6][2] = {
  73         {.577350269189625764509148780502, 0.0}, /* 1.0/sqrt3 */
  74         {.288675134594812882254574390251, 0.5}, /* 0.5/sqrt3 */
  75         {-.288675134594812882254574390251, 0.5},
  76         {-.577350269189625764509148780502, 0.0},
  77         {-.288675134594812882254574390251, -0.5},
  78         {.288675134594812882254574390251, -0.5}
  79 };
  80
  81 #if 0
  82
  83 /* TODO how is this related? to the above? */
  84 static double          texptvd[6][2] = {
  85         {1.154700538379251529018297561004, 0.5},        /* 2.0/sqrt3 */
  86         {.866025403784438646763723170753, 1.0}, /* 1.5/sqrt3 */
  87         {.288675134594812882254574390251, 1.0},
  88         {0.0, 0.5},
  89         {.288675134594812882254574390251, 0.0},
  90         {.866025403784438646763723170753, 0.0}
  91 };
  92
  93 static double          hexpthd[6][2] = {
  94         {0.0, .577350269189625764509148780502},
  95         {0.5, .288675134594812882254574390251},
  96         {0.5, -.288675134594812882254574390251},
  97         {0.0, -.577350269189625764509148780502},
  98         {-0.5, -.288675134594812882254574390251},
  99         {-0.5, .288675134594812882254574390251}
 100 };
 101
 102 #endif
 103
 104 void HL_vertices(int cantor, double *vc) {
 105         int i;
 106         double xc, yc;
 107
 108         HL_hexcenter(cantor, &xc, &yc);
 109
 110         for (i=0; i<6; i++) {
 111                 *vc++ = hexptvd[i][0] + xc;
 112                 *vc++ = hexptvd[i][1] + yc;
 113         }
 114         *vc++ = hexptvd[0][0] + xc;
 115         *vc++ = hexptvd[0][1] + yc;
 116 }
 117
 118 void HL_trianglefan(int cantor, double *vc) {
 119         HL_hexcenter(cantor, vc, vc+1);
 120         HL_vertices(cantor, vc+2);
 121 }
 122
 123 double HL_center_x(int cantor) {
 124         double x;
 125
 126         HL_hexcenter(cantor, &x, 0);
 127         return x;
 128 }
 129
 130 double HL_center_y(int cantor) {
 131         double y;
 132
 133         HL_hexcenter(cantor, 0, &y);
 134         return y;
 135 }
 136
 137 int HL_hexcenter(int cantor, double *xc, double *yc) {
 138         int x, y;
 139         double stride = 1.5/sqrt(3.0);
 140
 141         inversecantor(cantor, &x, &y);
 142
 143         if (xc) *xc = x * stride;
 144         if (yc && x >= 0) *yc = y + ((x + 1) % 2) / 2.0 - 0.5;
 145         if (yc && x < 0) *yc = y + ((-x + 1) % 2) / 2.0 - 0.5;
 146
 147         return cantor;
 148 }
 149
 150 /*
 151  * This function assumes that the hexes are one unit across, and vertically
 152  * oriented.  If that is not the case, you will need to transform
 153  * your input coordinates first.
 154  */
 155 int HL_cantor_bin(double x, double y) {
 156         return HL_hexbin(1.0, x, y, 0, 0);
 157 }
 158
 159 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
 160         int pi, pj, pk;
 161
 162         pi = x;
 163         pj = -y;
 164         if (x < 0) {
 165                 pj = pj + (-x + 1) / 2;
 166         } else {
 167                 pj = pj - x/2;
 168         }
 169         pk = -pi - pj;
 170
 171         if (i) *i = pi;
 172         if (j) *j = pj;
 173         if (k) *k = pk;
 174
 175         return HL_cantor_xy(x,y);
 176 }
 177
 178 static int ijk2xy(int i, int j, int k, int *x, int *y) {
 179         int px, py;
 180
 181         px = i;
 182
 183         /* py = -j - i/2; */
 184         py = -j;
 185
 186         if (i < 0) {
 187                 py += (-i + 1)/2;
 188         } else {
 189                 py -= i/2;
 190         }
 191
 192         if (x) *x = px;
 193         if (y) *y = py;
 194
 195         return HL_cantor_xy(px,py);
 196 }
 197
 198 int HL_cantor_ijk(int i, int j, int k) {
 199         return ijk2xy(i,j,k,0,0);
 200 }
 201
 202 int HL_distance(int from, int to) {
 203         int dist = 0, i;;
 204         int fc[3], tc[3];
 205
 206         HL_cantor_arrays(from, 0, fc);
 207         HL_cantor_arrays(to, 0, tc);
 208
 209         for (i=0;i<=2;i++) {
 210                 dist += abs(fc[i] - tc[i]);
 211         }
 212
 213         return dist / 2;
 214 }
 215
 216 int HL_hexes_within_range(int hex, int range, int *list, int size) {
 217         int count = 0;
 218         int i;
 219
 220         if (range == 0) {
 221                 return HL_hexes_at_range(hex, 0, list, size);
 222         }
 223
 224         for (i=1;i<=range;i++) {
 225                 count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
 226         }
 227         return count;
 228 }
 229
 230 int HL_hexes_at_range(int hex, int range, int *list, int size) {
 231         int q; /* p and q are count/loop vars */
 232         int c[3]; /* ijk coord array */
 233
 234         if (range == 0) {
 235                 if (list) {
 236                         list[0] = hex;
 237                 }
 238                 return 1;
 239         } else if (range < 0) {
 240                 return 0;
 241         }
 242
 243         /* TODO don't bother to collect if the list isn't big enough? */
 244         /* i.e. if (!list || size < range * 6) */
 245         if (!list || size < 1) return range * 6;
 246
 247         HL_cantor_arrays(hex, 0, c);
 248         c[0] += range;
 249         c[2] = -c[0] - c[1];
 250         hex = HL_cantor_ijkp(c);
 251
 252         for(q=0; q<size && q < range * 6; q++) {
 253                 list[q] = hex;
 254                 hex = HL_adjhex(hex, q/range+2);
 255         }
 256
 257         return range * 6;
 258 }
 259
 260 int HL_adjacent_hex(int start, int dir) {
 261         if (dir < 0 || dir > 5) return 0;
 262
 263         return HL_adjhex(start, dir);
 264 }
 265
 266 /* direction 0 is positive X , counter clockwise from there */
 267 int HL_adjhex(int start, int dir) {
 268         int c[3];
 269
 270         HL_cantor_arrays(start, 0, c);
 271
 272         switch (dir%6) {
 273                 case 2:
 274                         c[0]--; c[1]++; break;
 275                 case 1:
 276                                 c[1]++; c[2]--; break;
 277                 case 0:
 278                         c[0]++;         c[2]--; break;
 279                 case 5:
 280                         c[0]++; c[1]--; break;
 281                 case 4:
 282                                 c[1]--; c[2]++; break;
 283                 case 3:
 284                         c[0]--;       ; c[2]++; break;
 285         }
 286
 287         return HL_cantor_ijkp(c);
 288 }
 289
 290 int HL_cantor_xyp(int *xy) {
 291         return HL_cantor_xy(xy[0], xy[1]);
 292 }
 293
 294 int HL_cantor_ijkp(int *ijk) {
 295         return HL_cantor_ijk(ijk[0], ijk[1], ijk[2]);
 296 }
 297
 298 int HL_cantor_arrays(int can, int *xy, int *ijk) {
 299         return HL_cantor_decode(can, xy, xy ? xy+1 : 0,
 300                         ijk, ijk ? ijk+1 : 0, ijk ? ijk+2 : 0);
 301 }
 302
 303 int HL_cantor_decode(int can, int *x, int *y, int *i, int *j, int *k) {
 304         int px, py;
 305
 306         inversecantor(can, &px, &py);
 307         if (x) *x = px;
 308         if (y) *y = py;
 309
 310         xy2ijk(px, py, i, j, k);
 311
 312         return can;
 313 }
 314
 315 int HL_cantor_i(int cantor) {
 316         int i;
 317
 318         HL_cantor_decode(cantor, 0,0, &i,0,0);
 319         return i;
 320 }
 321
 322 int HL_cantor_j(int cantor) {
 323         int j;
 324
 325         HL_cantor_decode(cantor, 0,0, 0,&j,0);
 326         return j;
 327 }
 328
 329 int HL_cantor_k(int cantor) {
 330         int k;
 331
 332         HL_cantor_decode(cantor, 0,0, 0,0,&k);
 333         return k;
 334 }
 335
 336 int HL_cantor_x(int cantor) {
 337         int x;
 338         inversecantor(cantor, &x, 0);
 339         return x;
 340 }
 341
 342 int HL_cantor_y(int cantor) {
 343         int y;
 344         inversecantor(cantor, 0, &y);
 345         return y;
 346 }
 347
 348 /* Determine if a map with these dimensions will overflow */
 349 int HL_map_bounds_ok(int xdim, int ydim) {
 350
 351         /* return (x+y) * (x + y + 1) / 2 + y+1; */
 352
 353         if (INT_MAX - xdim - 1 < ydim) return 0;
 354         if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
 355         if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
 356                 return 0;
 357
 358         return 1;
 359 }
 360
 361 int HL_map_max_dimension(void) {
 362         int low, high, try;
 363
 364         low = 1; high = INT_MAX/2;
 365
 366         while (low != high - 1) {
 367                 try = (low + high) / 2;
 368                 if (HL_map_bounds_ok(try,try)) {
 369                         low = try;
 370                 } else {
 371                         high = try;
 372                 }
 373         }
 374
 375         return low;
 376 }
 377
 378 static int inversenatcantor(int cantor, int *x, int *y) {
 379         int w, t, py;
 380
 381         cantor -= 1;
 382
 383         w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0);
 384         t = (w * w + w)/2;
 385
 386         py = cantor - t;
 387
 388         if (y) *y = py;
 389         if (x) *x = w - py;
 390
 391         return cantor;
 392 }
 393
 394 /*
 395  * map non negative integer pairs to their cantor pairing function
 396  * number, plus one.  We add one so that the result is never zero,
 397  * leaving zero to be "invalid" or "none" or what have you.
 398  */
 399
 400 static int natcantor(int x, int y) {
 401         return (x+y) * (x + y + 1) / 2 + y+1;
 402 }
 403
 404 /* See http://en.wikipedia.org/wiki/Cantor_pairing_function */
 405 /* see also http://szudzik.com/ElegantPairing.pdf */
 406 /*
 407  * if either coordinate is negative, map the integers onto the
 408  * whole numbers, and then return the negative of the adjusted
 409  * cantor number.  As for most grids negative coordinates will
 410  * be invalid, this will allow for a <= 0 test for invalid
 411  * or out of bounds (on the negative side anyway, you'll
 412  * still have to test for out of range on the positive side).
 413  *
 414  * TODO figure out what the maximum supported coordinates are
 415  * for given integer sizes.
 416  */
 417 int HL_cantor_xy(int x, int y) {
 418         if (x < 0 || y < 0) {
 419                 x = abs(2 * x) - (x < 0);
 420                 y = abs(2 * y) - (y < 0);
 421                 return -natcantor(x, y);
 422         }
 423         return natcantor(x,y);
 424 }
 425
 426 static int inversecantor(int cantor, int *x, int *y) {
 427         if (cantor < 0) {
 428                 inversenatcantor(-cantor, x, y);
 429                 if (x) {
 430                         if (*x % 2) {
 431                                 *x = -(*x+1)/2;
 432                         } else {
 433                                 *x = *x / 2;
 434                         }
 435                 }
 436                 if (y) {
 437                         if (*y % 2) {
 438                                 *y =  -(*y+1)/2;
 439                         } else {
 440                                 *y = *y/2;
 441                         }
 442                 }
 443         } else {
 444                 inversenatcantor(cantor, x, y);
 445         }
 446
 447         return cantor;
 448 }
 449
 450 struct hex {
 451         int iso;
 452         int x, y, z;
 453 };
 454
 455 /* y *must* be positive down as the xy /iso conversion assumes this */
 456 static int hex_xy(struct hex *h) {
 457         if (!h->iso) return 1;
 458         if (h->x >= 0) {
 459                 h->y = -h->y - (h->x+1)/2;
 460         } else {
 461                 /* need to round toward -inf, not toward zero, so x-1 */
 462                 h->y = -h->y - h->x/2;
 463         }
 464         h->iso = 0;
 465
 466         return 1;
 467 }
 468
 469 #if 0
 470
 471 static int hex_iso(struct hex *h) {
 472         if (h->iso) return 1;
 473
 474         if (h->x >= 0) {
 475                 h->y = (-h->y - (h->x+1)/2);
 476         } else {
 477                 /* need to round toward -inf, not toward zero, so x-1 */
 478                 h->y = (-h->y - (h->x)/2);
 479         }
 480
 481         h->z = -h->x - h->y;
 482         h->iso = 1;
 483         return 1;
 484 }
 485
 486 #endif
 487
 488 #define COS30 (.866025403784438646763723170752)
 489
 490 int HL_hexbin(double width, double x, double y, int *i, int *j) {
 491         double z, rx, ry, rz;
 492         double abs_dx, abs_dy, abs_dz;
 493         int ix, iy, iz, s;
 494         struct hex h;
 495
 496         /*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */
 497         x = x / COS30;
 498         y = y - x / 2.0; /* adjustment for rotated X */
 499
 500         /* adjust for actual hexwidth */
 501         x /= width;
 502         y /= width;
 503
 504         z = -x - y;
 505
 506         ix = rx = floor(x + 0.5);
 507         iy = ry = floor(y + 0.5);
 508         iz = rz = floor(z + 0.5);
 509
 510         s = ix + iy + iz;
 511
 512         if (s) {
 513                 abs_dx = fabs(rx - x);
 514                 abs_dy = fabs(ry - y);
 515                 abs_dz = fabs(rz - z);
 516
 517                 if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
 518                         ix -= s;
 519                 } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {
 520                         iy -= s;
 521                 } else {
 522                         iz -= s;
 523                 }
 524         }
 525         h.x = ix;
 526         h.y = iy;
 527         h.z = iz;
 528         h.iso = 1;
 529
 530         hex_xy(&h);
 531         if (i) *i = h.x;
 532         if (j) *j = h.y;
 533         return HL_cantor_xy(h.x, h.y);
 534 }