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

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