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