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 /*
 105 c = 1.0 = distance from center to vertex
 106 b = distance to hex side
 107 a = distance along hex side
 108
 109 A = angle at point center, this is the polar coord angle
 110 B = angle from vertex, this is 60 degrees
 111 C = Other angle, which is 180 - 60 - A = 120 - A
 112
 113 sin B = sin 60 = sqrt(3) / 2
 114 cos B = cos 60 = 1/2
 115
 116 b = c * sin B / ( sin A cos B + sin B cos A)
 117
 118 c * sin B / ( sin A cos B + sin B cos A)
 119
 120 0.5 * sqrt3
 121 -------------
 122 sinA 0.5 + sqrt3 * 0.5 cosA
 123
 124 sqrt3
 125 -------------
 126 sinA + sqrt3 cosA
 127
 128 b=
 129 3
 130 -------------
 131 cosA + sqrt3 sinA
 132
 133 x = b cosA
 134 y = b sinA
 135 */
 136
 137 #define RD (180.0 / M_PI)
 138 /* angle ranges from 0-6 */
 139 /* distance is 0 at origin, 1.0 at the hex side */
 140
 141 /* return the polar distance ? */
 142 double HL_polar(double angle, double distance, double *x, double *y) {
 143         double A, B, C, b, c;
 144         double sinB, sinC;
 145 #if 0
 146         double sqrt3;
 147
 148         sqrt3 = sqrt(3.0);
 149 #endif
 150
 151         /* convert angle to radians */
 152         angle = angle * M_PI / 3.0;
 153
 154         /* calculate the distance along the ray to the hex side */
 155
 156         A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */
 157         B = M_PI / 3.0;
 158         C = M_PI - A - B;
 159
 160         sinB = sin(B);
 161         sinC = sin(C);
 162
 163         c = 1.0;
 164         c = HL_vertexv[0];
 165 #if 0
 166         /* provided for completeness, but we don't use the value */
 167         sinA = sin(A);
 168         a = c * sinA / sinC;
 169 #endif
 170         b = c * sinB / sinC;
 171
 172         if (x) {
 173                 *x = b * cos(angle);
 174         }
 175
 176         if (y) {
 177                 *y = b * sin(angle);
 178         }
 179
 180         return b;
 181 }
 182
 183 void HL_vertices(int cantor, double *vc) {
 184         int i;
 185         double xc, yc;
 186
 187         HL_hexcenter(cantor, &xc, &yc);
 188
 189         for (i=0; i<6; i++) {
 190                 *vc++ = hexptvd[i][0] + xc;
 191                 *vc++ = hexptvd[i][1] + yc;
 192         }
 193         *vc++ = hexptvd[0][0] + xc;
 194         *vc++ = hexptvd[0][1] + yc;
 195 }
 196
 197 void HL_trianglefan(int cantor, double *vc) {
 198         HL_hexcenter(cantor, vc, vc+1);
 199         HL_vertices(cantor, vc+2);
 200 }
 201
 202 double HL_center_x(int cantor) {
 203         double x;
 204
 205         HL_hexcenter(cantor, &x, 0);
 206         return x;
 207 }
 208
 209 double HL_center_y(int cantor) {
 210         double y;
 211
 212         HL_hexcenter(cantor, 0, &y);
 213         return y;
 214 }
 215
 216 int HL_hexcenter(int cantor, double *xc, double *yc) {
 217         int x, y;
 218         double stride = 1.5/sqrt(3.0);
 219
 220         inversecantor(cantor, &x, &y);
 221
 222         if (xc) *xc = x * stride;
 223         if (yc && x >= 0) *yc = y + ((x + 1) % 2) / 2.0 - 0.5;
 224         if (yc && x < 0) *yc = y + ((-x + 1) % 2) / 2.0 - 0.5;
 225
 226         return cantor;
 227 }
 228
 229 /*
 230  * This function assumes that the hexes are one unit across, and vertically
 231  * oriented.  If that is not the case, you will need to transform
 232  * your input coordinates first.
 233  */
 234 int HL_cantor_bin(double x, double y) {
 235         return HL_hexbin(1.0, x, y, 0, 0);
 236 }
 237
 238 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
 239         int pi, pj, pk;
 240
 241         pi = x;
 242         pj = -y;
 243         if (x < 0) {
 244                 pj = pj + (-x + 1) / 2;
 245         } else {
 246                 pj = pj - x/2;
 247         }
 248         pk = -pi - pj;
 249
 250         if (i) *i = pi;
 251         if (j) *j = pj;
 252         if (k) *k = pk;
 253
 254         return HL_cantor_xy(x,y);
 255 }
 256
 257 static int ijk2xy(int i, int j, int k, int *x, int *y) {
 258         int px, py;
 259
 260         px = i;
 261
 262         /* py = -j - i/2; */
 263         py = -j;
 264
 265         if (i < 0) {
 266                 py += (-i + 1)/2;
 267         } else {
 268                 py -= i/2;
 269         }
 270
 271         if (x) *x = px;
 272         if (y) *y = py;
 273
 274         return HL_cantor_xy(px,py);
 275 }
 276
 277 int HL_cantor_ijk(int i, int j, int k) {
 278         return ijk2xy(i,j,k,0,0);
 279 }
 280
 281 int HL_distance(int from, int to) {
 282         int dist = 0, i;;
 283         int fc[3], tc[3];
 284
 285         HL_cantor_arrays(from, 0, fc);
 286         HL_cantor_arrays(to, 0, tc);
 287
 288         for (i=0;i<=2;i++) {
 289                 dist += abs(fc[i] - tc[i]);
 290         }
 291
 292         return dist / 2;
 293 }
 294
 295 int HL_hexes_within_range(int hex, int range, int *list, int size) {
 296         int count = 0;
 297         int i;
 298
 299         if (range == 0) {
 300                 return HL_hexes_at_range(hex, 0, list, size);
 301         }
 302
 303         for (i=1;i<=range;i++) {
 304                 count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
 305         }
 306         return count;
 307 }
 308
 309 int HL_hexes_at_range(int hex, int range, int *list, int size) {
 310         int q; /* p and q are count/loop vars */
 311         int c[3]; /* ijk coord array */
 312
 313         if (range == 0) {
 314                 if (list) {
 315                         list[0] = hex;
 316                 }
 317                 return 1;
 318         } else if (range < 0) {
 319                 return 0;
 320         }
 321
 322         /* TODO don't bother to collect if the list isn't big enough? */
 323         /* i.e. if (!list || size < range * 6) */
 324         if (!list || size < 1) return range * 6;
 325
 326         HL_cantor_arrays(hex, 0, c);
 327         c[0] += range;
 328         c[2] = -c[0] - c[1];
 329         hex = HL_cantor_ijkp(c);
 330
 331         for(q=0; q<size && q < range * 6; q++) {
 332                 list[q] = hex;
 333                 hex = HL_adjhex(hex, q/range+2);
 334         }
 335
 336         return range * 6;
 337 }
 338
 339 int HL_adjacent_hex(int start, int dir) {
 340         if (dir < 0 || dir > 5) return 0;
 341
 342         return HL_adjhex(start, dir);
 343 }
 344
 345 /* direction 0 is positive X , counter clockwise from there */
 346 int HL_adjhex(int start, int dir) {
 347         int c[3];
 348
 349         HL_cantor_arrays(start, 0, c);
 350
 351         switch (dir%6) {
 352                 case 2:
 353                         c[0]--; c[1]++; break;
 354                 case 1:
 355                                 c[1]++; c[2]--; break;
 356                 case 0:
 357                         c[0]++;         c[2]--; break;
 358                 case 5:
 359                         c[0]++; c[1]--; break;
 360                 case 4:
 361                                 c[1]--; c[2]++; break;
 362                 case 3:
 363                         c[0]--;       ; c[2]++; break;
 364         }
 365
 366         return HL_cantor_ijkp(c);
 367 }
 368
 369 int HL_cantor_xyp(int *xy) {
 370         return HL_cantor_xy(xy[0], xy[1]);
 371 }
 372
 373 int HL_cantor_ijkp(int *ijk) {
 374         return HL_cantor_ijk(ijk[0], ijk[1], ijk[2]);
 375 }
 376
 377 int HL_cantor_arrays(int can, int *xy, int *ijk) {
 378         return HL_cantor_decode(can, xy, xy ? xy+1 : 0,
 379                         ijk, ijk ? ijk+1 : 0, ijk ? ijk+2 : 0);
 380 }
 381
 382 int HL_cantor_decode(int can, int *x, int *y, int *i, int *j, int *k) {
 383         int px, py;
 384
 385         inversecantor(can, &px, &py);
 386         if (x) *x = px;
 387         if (y) *y = py;
 388
 389         xy2ijk(px, py, i, j, k);
 390
 391         return can;
 392 }
 393
 394 int HL_cantor_i(int cantor) {
 395         int i;
 396
 397         HL_cantor_decode(cantor, 0,0, &i,0,0);
 398         return i;
 399 }
 400
 401 int HL_cantor_j(int cantor) {
 402         int j;
 403
 404         HL_cantor_decode(cantor, 0,0, 0,&j,0);
 405         return j;
 406 }
 407
 408 int HL_cantor_k(int cantor) {
 409         int k;
 410
 411         HL_cantor_decode(cantor, 0,0, 0,0,&k);
 412         return k;
 413 }
 414
 415 int HL_cantor_x(int cantor) {
 416         int x;
 417         inversecantor(cantor, &x, 0);
 418         return x;
 419 }
 420
 421 int HL_cantor_y(int cantor) {
 422         int y;
 423         inversecantor(cantor, 0, &y);
 424         return y;
 425 }
 426
 427 /* Determine if a map with these dimensions will overflow */
 428 int HL_map_bounds_ok(int xdim, int ydim) {
 429
 430         /* return (x+y) * (x + y + 1) / 2 + y+1; */
 431
 432         if (INT_MAX - xdim - 1 < ydim) return 0;
 433         if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
 434         if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
 435                 return 0;
 436
 437         return 1;
 438 }
 439
 440 int HL_map_max_dimension(void) {
 441         int low, high, try;
 442
 443         low = 1; high = INT_MAX/2;
 444
 445         while (low != high - 1) {
 446                 try = (low + high) / 2;
 447                 if (HL_map_bounds_ok(try,try)) {
 448                         low = try;
 449                 } else {
 450                         high = try;
 451                 }
 452         }
 453
 454         return low;
 455 }
 456
 457 static int inversenatcantor(int cantor, int *x, int *y) {
 458         int w, t, py;
 459
 460         cantor -= 1;
 461
 462         w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0);
 463         t = (w * w + w)/2;
 464
 465         py = cantor - t;
 466
 467         if (y) *y = py;
 468         if (x) *x = w - py;
 469
 470         return cantor;
 471 }
 472
 473 /*
 474  * map non negative integer pairs to their cantor pairing function
 475  * number, plus one.  We add one so that the result is never zero,
 476  * leaving zero to be "invalid" or "none" or what have you.
 477  */
 478
 479 static int natcantor(int x, int y) {
 480         return (x+y) * (x + y + 1) / 2 + y+1;
 481 }
 482
 483 /* See http://en.wikipedia.org/wiki/Cantor_pairing_function */
 484 /* see also http://szudzik.com/ElegantPairing.pdf */
 485 /*
 486  * if either coordinate is negative, map the integers onto the
 487  * whole numbers, and then return the negative of the adjusted
 488  * cantor number.  As for most grids negative coordinates will
 489  * be invalid, this will allow for a <= 0 test for invalid
 490  * or out of bounds (on the negative side anyway, you'll
 491  * still have to test for out of range on the positive side).
 492  *
 493  * TODO figure out what the maximum supported coordinates are
 494  * for given integer sizes.
 495  */
 496 int HL_cantor_xy(int x, int y) {
 497         if (x < 0 || y < 0) {
 498                 x = abs(2 * x) - (x < 0);
 499                 y = abs(2 * y) - (y < 0);
 500                 return -natcantor(x, y);
 501         }
 502         return natcantor(x,y);
 503 }
 504
 505 static int inversecantor(int cantor, int *x, int *y) {
 506         if (cantor < 0) {
 507                 inversenatcantor(-cantor, x, y);
 508                 if (x) {
 509                         if (*x % 2) {
 510                                 *x = -(*x+1)/2;
 511                         } else {
 512                                 *x = *x / 2;
 513                         }
 514                 }
 515                 if (y) {
 516                         if (*y % 2) {
 517                                 *y =  -(*y+1)/2;
 518                         } else {
 519                                 *y = *y/2;
 520                         }
 521                 }
 522         } else {
 523                 inversenatcantor(cantor, x, y);
 524         }
 525
 526         return cantor;
 527 }
 528
 529 struct hex {
 530         int iso;
 531         int x, y, z;
 532 };
 533
 534 /* y *must* be positive down as the xy /iso conversion assumes this */
 535 static int hex_xy(struct hex *h) {
 536         if (!h->iso) return 1;
 537         if (h->x >= 0) {
 538                 h->y = -h->y - (h->x+1)/2;
 539         } else {
 540                 /* need to round toward -inf, not toward zero, so x-1 */
 541                 h->y = -h->y - h->x/2;
 542         }
 543         h->iso = 0;
 544
 545         return 1;
 546 }
 547
 548 #if 0
 549
 550 static int hex_iso(struct hex *h) {
 551         if (h->iso) return 1;
 552
 553         if (h->x >= 0) {
 554                 h->y = (-h->y - (h->x+1)/2);
 555         } else {
 556                 /* need to round toward -inf, not toward zero, so x-1 */
 557                 h->y = (-h->y - (h->x)/2);
 558         }
 559
 560         h->z = -h->x - h->y;
 561         h->iso = 1;
 562         return 1;
 563 }
 564
 565 #endif
 566
 567 #define COS30 (.866025403784438646763723170752)
 568
 569 int HL_hexbin(double width, double x, double y, int *i, int *j) {
 570         double z, rx, ry, rz;
 571         double abs_dx, abs_dy, abs_dz;
 572         int ix, iy, iz, s;
 573         struct hex h;
 574
 575         /*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */
 576         x = x / COS30;
 577         y = y - x / 2.0; /* adjustment for rotated X */
 578
 579         /* adjust for actual hexwidth */
 580         x /= width;
 581         y /= width;
 582
 583         z = -x - y;
 584
 585         ix = rx = floor(x + 0.5);
 586         iy = ry = floor(y + 0.5);
 587         iz = rz = floor(z + 0.5);
 588
 589         s = ix + iy + iz;
 590
 591         if (s) {
 592                 abs_dx = fabs(rx - x);
 593                 abs_dy = fabs(ry - y);
 594                 abs_dz = fabs(rz - z);
 595
 596                 if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
 597                         ix -= s;
 598                 } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {
 599                         iy -= s;
 600                 } else {
 601                         iz -= s;
 602                 }
 603         }
 604         h.x = ix;
 605         h.y = iy;
 606         h.z = iz;
 607         h.iso = 1;
 608
 609         hex_xy(&h);
 610         if (i) *i = h.x;
 611         if (j) *j = h.y;
 612         return HL_cantor_xy(h.x, h.y);
 613 }