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