8 /* constructor function */
9 struct HL_hex HL_hex_xy(int x, int y) {
16 int HL_hex_cmp(struct HL_hex const *a, struct HL_hex const *b) {
18 return a->x > b->x ? 1 : -1;
21 return a->y > b->y ? 1 : -1;
26 int HL_hex_eq(struct HL_hex const *a, struct HL_hex const *b) {
27 return a->x == b->x && a->y == b->y;
31 * This file is written by Nathan Wagner and dedicated to the public
35 double HL_vertexv[12] = {
36 .577350269189625764509148780502, 0.0,
37 .288675134594812882254574390251, 0.5,
38 -.288675134594812882254574390251, 0.5,
39 -.577350269189625764509148780502, 0.0,
40 -.288675134594812882254574390251, -0.5,
41 .288675134594812882254574390251, -0.5};
43 double HL_fand[16] = {
45 .577350269189625764509148780502, 0.0,
46 .288675134594812882254574390251, 0.5,
47 -.288675134594812882254574390251, 0.5,
48 -.577350269189625764509148780502, 0.0,
49 -.288675134594812882254574390251, -0.5,
50 .288675134594812882254574390251, -0.5,
51 .577350269189625764509148780502, 0.0
54 double HL_hfand[16] = {
56 0.0, .577350269189625764509148780502,
57 0.5, .288675134594812882254574390251,
58 0.5, -.288675134594812882254574390251,
59 0.0, -.577350269189625764509148780502,
60 -0.5, -.288675134594812882254574390251,
61 -0.5, .288675134594812882254574390251,
62 0.0, .577350269189625764509148780502
67 .577350269189625764509148780502f, 0.0f,
68 .288675134594812882254574390251f, 0.5f,
69 -.288675134594812882254574390251f, 0.5f,
70 -.577350269189625764509148780502f, 0.0f,
71 -.288675134594812882254574390251f, -0.5f,
72 .288675134594812882254574390251f, -0.5f,
73 .577350269189625764509148780502f, 0.0f
76 float HL_hfanf[16] = {
78 0.0f, .577350269189625764509148780502f,
79 0.5f, .288675134594812882254574390251f,
80 0.5f, -.288675134594812882254574390251f,
81 0.0f, -.577350269189625764509148780502f,
82 -0.5f, -.288675134594812882254574390251f,
83 -0.5f, .288675134594812882254574390251f,
84 0.0f, .577350269189625764509148780502f
87 /* size of a square that will exactly fit in a hexagon */
88 /* 2.0/(1+sqrt(3.0)) */
89 double HL_square = .73205080756887729352;
91 /* these all are for a hex one unit across */
92 static double hexptvd[6][2] = {
93 {.577350269189625764509148780502, 0.0}, /* 1.0/sqrt3 */
94 {.288675134594812882254574390251, 0.5}, /* 0.5/sqrt3 */
95 {-.288675134594812882254574390251, 0.5},
96 {-.577350269189625764509148780502, 0.0},
97 {-.288675134594812882254574390251, -0.5},
98 {.288675134594812882254574390251, -0.5}
103 /* TODO how is this related? to the above? */
104 static double texptvd[6][2] = {
105 {1.154700538379251529018297561004, 0.5}, /* 2.0/sqrt3 */
106 {.866025403784438646763723170753, 1.0}, /* 1.5/sqrt3 */
107 {.288675134594812882254574390251, 1.0},
109 {.288675134594812882254574390251, 0.0},
110 {.866025403784438646763723170753, 0.0}
113 static double hexpthd[6][2] = {
114 {0.0, .577350269189625764509148780502},
115 {0.5, .288675134594812882254574390251},
116 {0.5, -.288675134594812882254574390251},
117 {0.0, -.577350269189625764509148780502},
118 {-0.5, -.288675134594812882254574390251},
119 {-0.5, .288675134594812882254574390251}
124 #define RD (180.0 / M_PI)
125 /* angle ranges from 0-6 */
126 /* distance is 0 at origin, 1.0 at the hex side */
154 /* return the polar distance */
155 struct HL_point HL_polar(double angle, double distance, double *d) {
168 c = 1 ; fixed, will scale later
169 B = 60 ; exterior angle of hextant
170 C = 180-B-A = 120-A ; sum of angles of a triangle
171 A = function argument ; the polar coordinate we are calculating
172 b = c * sin(B) / sin(C) ; law of sines
175 /* convert angle to radians */
176 angle = angle * M_PI / 3.0;
178 /* calculate the distance along the ray to the hex side */
180 A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */
186 /* scale for hex one unit from side to side, rather than
187 * one unit from center to vertex
189 /* b = b * sqrt(3.0) / 2.0 / 2.0; */
192 pt.x = distance * b * cos(angle);
193 pt.y = distance * b * sin(angle);
202 void HL_vertices(struct HL_hex hex, double *vc) {
205 struct HL_point center;
207 center = HL_hexcenter(hex);
211 for (i=0; i<6; i++) {
212 *vc++ = hexptvd[i][0] + xc;
213 *vc++ = hexptvd[i][1] + yc;
215 *vc++ = hexptvd[0][0] + xc;
216 *vc++ = hexptvd[0][1] + yc;
220 void HL_trianglefan(int cantor, double *vc) {
221 HL_hexcenter(cantor, vc, vc+1);
222 HL_vertices(cantor, vc+2);
226 struct HL_point HL_hexcenter(struct HL_hex hex) {
228 struct HL_point center;
231 double stride = 1.5/sqrt(3.0);
236 center.x = x * stride;
238 if (x >= 0) yc = y + ((x + 1) % 2) / 2.0 - 0.5;
239 if (x < 0) yc = y + ((-x + 1) % 2) / 2.0 - 0.5;
247 * This function assumes that the hexes are one unit across, and vertically
248 * oriented. If that is not the case, you will need to transform
249 * your input coordinates first.
251 struct HL_hex HL_bin(double x, double y) {
252 return HL_hexbin(1.0, x, y);
255 struct HL_isohex HL_xy2ijk(struct HL_hex hex) {
258 struct HL_isohex iso;
267 pj = pj + (-x + 1) / 2;
282 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
288 pj = pj + (-x + 1) / 2;
298 return HL_cantor_xy(x,y);
300 static int ijk2xy(int i, int j, int k, int *x, int *y) {
317 return HL_cantor_xy(px,py);
322 struct HL_hex HL_ijk2xy(struct HL_isohex iso) {
348 static void xy2ijkp(struct HL_hex h, int *ijk) {
349 struct HL_isohex iso;
357 int HL_distance(struct HL_hex from, struct HL_hex to) {
365 dist += abs(fc[i] - tc[i]);
371 int HL_hexes_within_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
376 return HL_hexes_at_range(hex, 0, list, size);
379 for (i=1;i<=range;i++) {
380 count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
385 int HL_hexes_at_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
386 int q; /* p and q are count/loop vars */
387 struct HL_isohex iso;
395 } else if (range < 0) {
399 /* TODO don't bother to collect if the list isn't big enough? */
400 /* i.e. if (!list || size < range * 6) */
401 if (!list || size < 1) return range * 6;
403 iso = HL_xy2ijk(hex);
406 iso.k = -iso.i - iso.j;
408 hex = HL_ijk2xy(iso);
410 for(q=0; q<size && q < range * 6; q++) {
412 hex = HL_adjhex(hex, q/range+2);
418 /* direction 0 is positive X , counter clockwise from there */
419 struct HL_hex HL_adjhex(struct HL_hex hex, int dir) {
421 struct HL_isohex iso;
423 iso = HL_xy2ijk(hex);
430 c[0]--; c[1]++; break;
432 c[1]++; c[2]--; break;
434 c[0]++; c[2]--; break;
436 c[0]++; c[1]--; break;
438 c[1]--; c[2]++; break;
440 c[0]--; ; c[2]++; break;
447 return HL_ijk2xy(iso);
450 int HL_adjhexp(struct HL_hex hex, int dir, struct HL_hex *adj) {
452 *adj = HL_adjhex(hex, dir);
457 /* Determine if a map with these dimensions will overflow */
458 int HL_map_bounds_ok(int xdim, int ydim) {
460 /* return (x+y) * (x + y + 1) / 2 + y+1; */
462 if (INT_MAX - xdim - 1 < ydim) return 0;
463 if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
464 if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
470 int HL_map_max_dimension(void) {
473 low = 1; high = INT_MAX/2;
475 while (low != high - 1) {
476 try = (low + high) / 2;
477 if (HL_map_bounds_ok(try,try)) {
492 /* y *must* be positive down as the xy /iso conversion assumes this */
493 static int hex_xy(struct hex *h) {
494 if (!h->iso) return 1;
496 h->y = -h->y - (h->x+1)/2;
498 /* need to round toward -inf, not toward zero, so x-1 */
499 h->y = -h->y - h->x/2;
508 static int hex_iso(struct hex *h) {
509 if (h->iso) return 1;
512 h->y = (-h->y - (h->x+1)/2);
514 /* need to round toward -inf, not toward zero, so x-1 */
515 h->y = (-h->y - (h->x)/2);
525 #define COS30 (.866025403784438646763723170752)
527 struct HL_hex HL_hexbin(double width, double x, double y) {
528 double z, rx, ry, rz;
529 double abs_dx, abs_dy, abs_dz;
534 /*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */
536 y = y - x / 2.0; /* adjustment for rotated X */
538 /* adjust for actual hexwidth */
544 ix = rx = floor(x + 0.5);
545 iy = ry = floor(y + 0.5);
546 iz = rz = floor(z + 0.5);
551 abs_dx = fabs(rx - x);
552 abs_dy = fabs(ry - y);
553 abs_dz = fabs(rz - z);
555 if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
557 } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {