X-Git-Url: https://pd.if.org/git/?p=hexagon;a=blobdiff_plain;f=lib%2Fhexagon.c;fp=lib%2Fhexagon.c;h=155a5d2f1bd4676797c0dbb9c226d6d21391e34c;hp=0000000000000000000000000000000000000000;hb=d74b76176b43b9eae3b584c231b077d3a3f0f92b;hpb=06868ef42497f1cbc480831029f5f69b395dfdd2 diff --git a/lib/hexagon.c b/lib/hexagon.c new file mode 100644 index 0000000..155a5d2 --- /dev/null +++ b/lib/hexagon.c @@ -0,0 +1,574 @@ +#include "hexagon.h" + +#include +#include +#include +#include + +/* constructor function */ +struct HL_hex HL_hex_xy(int x, int y) { + struct HL_hex h; + h.x = x; + h.y = y; + return h; +} + +int HL_hex_cmp(struct HL_hex const *a, struct HL_hex const *b) { + if (a->x != b->x) { + return a->x > b->x ? 1 : -1; + } + if (a->y != b->y) { + return a->y > b->y ? 1 : -1; + } + return 0; +} + +int HL_hex_eq(struct HL_hex const *a, struct HL_hex const *b) { + return a->x == b->x && a->y == b->y; +} + +/* + * This file is written by Nathan Wagner and dedicated to the public + * domain + */ + +double HL_vertexv[12] = { + .577350269189625764509148780502, 0.0, + .288675134594812882254574390251, 0.5, + -.288675134594812882254574390251, 0.5, + -.577350269189625764509148780502, 0.0, + -.288675134594812882254574390251, -0.5, + .288675134594812882254574390251, -0.5}; + +double HL_fand[16] = { + 0.0, 0.0, + .577350269189625764509148780502, 0.0, + .288675134594812882254574390251, 0.5, + -.288675134594812882254574390251, 0.5, + -.577350269189625764509148780502, 0.0, + -.288675134594812882254574390251, -0.5, + .288675134594812882254574390251, -0.5, + .577350269189625764509148780502, 0.0 +}; + +double HL_hfand[16] = { + 0.0, 0.0, + 0.0, .577350269189625764509148780502, + 0.5, .288675134594812882254574390251, + 0.5, -.288675134594812882254574390251, + 0.0, -.577350269189625764509148780502, + -0.5, -.288675134594812882254574390251, + -0.5, .288675134594812882254574390251, + 0.0, .577350269189625764509148780502 +}; + +float HL_fanf[16] = { + 0.0f, 0.0f, + .577350269189625764509148780502f, 0.0f, + .288675134594812882254574390251f, 0.5f, + -.288675134594812882254574390251f, 0.5f, + -.577350269189625764509148780502f, 0.0f, + -.288675134594812882254574390251f, -0.5f, + .288675134594812882254574390251f, -0.5f, + .577350269189625764509148780502f, 0.0f +}; + +float HL_hfanf[16] = { + 0.0f, 0.0f, + 0.0f, .577350269189625764509148780502f, + 0.5f, .288675134594812882254574390251f, + 0.5f, -.288675134594812882254574390251f, + 0.0f, -.577350269189625764509148780502f, + -0.5f, -.288675134594812882254574390251f, + -0.5f, .288675134594812882254574390251f, + 0.0f, .577350269189625764509148780502f +}; + +/* size of a square that will exactly fit in a hexagon */ +/* 2.0/(1+sqrt(3.0)) */ +double HL_square = .73205080756887729352; + +/* these all are for a hex one unit across */ +static double hexptvd[6][2] = { + {.577350269189625764509148780502, 0.0}, /* 1.0/sqrt3 */ + {.288675134594812882254574390251, 0.5}, /* 0.5/sqrt3 */ + {-.288675134594812882254574390251, 0.5}, + {-.577350269189625764509148780502, 0.0}, + {-.288675134594812882254574390251, -0.5}, + {.288675134594812882254574390251, -0.5} +}; + +#if 0 + +/* TODO how is this related? to the above? */ +static double texptvd[6][2] = { + {1.154700538379251529018297561004, 0.5}, /* 2.0/sqrt3 */ + {.866025403784438646763723170753, 1.0}, /* 1.5/sqrt3 */ + {.288675134594812882254574390251, 1.0}, + {0.0, 0.5}, + {.288675134594812882254574390251, 0.0}, + {.866025403784438646763723170753, 0.0} +}; + +static double hexpthd[6][2] = { + {0.0, .577350269189625764509148780502}, + {0.5, .288675134594812882254574390251}, + {0.5, -.288675134594812882254574390251}, + {0.0, -.577350269189625764509148780502}, + {-0.5, -.288675134594812882254574390251}, + {-0.5, .288675134594812882254574390251} +}; + +#endif + +#define RD (180.0 / M_PI) +/* angle ranges from 0-6 */ +/* distance is 0 at origin, 1.0 at the hex side */ + +#if 0 + double sqrt3; + + sqrt3 = sqrt(3.0); + + 1 + /---\ + 2/ \0 + / \ + \ / + 3\ /5 + \---/ + 4 + + /\ + 0/ \5 + / \ + | | + 1| |4 + | | + \ / + 2\ /3 + \/ + +#endif + +/* return the polar distance */ +struct HL_point HL_polar(double angle, double distance, double *d) { + double A, B, C, b; + struct HL_point pt; + +#if 0 + C + /\ + b / \ a + / \ + / \ + A -------- B + c + + c = 1 ; fixed, will scale later + B = 60 ; exterior angle of hextant + C = 180-B-A = 120-A ; sum of angles of a triangle + A = function argument ; the polar coordinate we are calculating + b = c * sin(B) / sin(C) ; law of sines + +#endif + /* convert angle to radians */ + angle = angle * M_PI / 3.0; + + /* calculate the distance along the ray to the hex side */ + + A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */ + B = M_PI / 3.0; + C = M_PI - B - A; + + b = sin(B) / sin(C); + + /* scale for hex one unit from side to side, rather than + * one unit from center to vertex + */ +/* b = b * sqrt(3.0) / 2.0 / 2.0; */ + b = b / sqrt(3); + + pt.x = distance * b * cos(angle); + pt.y = distance * b * sin(angle); + + if (d) { + *d = distance * b; + } + + return pt; +} + +void HL_vertices(struct HL_hex hex, double *vc) { + int i; + double xc, yc; + struct HL_point center; + + center = HL_hexcenter(hex); + xc = center.x; + yc = center.y; + + for (i=0; i<6; i++) { + *vc++ = hexptvd[i][0] + xc; + *vc++ = hexptvd[i][1] + yc; + } + *vc++ = hexptvd[0][0] + xc; + *vc++ = hexptvd[0][1] + yc; +} + +#if 0 +void HL_trianglefan(int cantor, double *vc) { + HL_hexcenter(cantor, vc, vc+1); + HL_vertices(cantor, vc+2); +} +#endif + +struct HL_point HL_hexcenter(struct HL_hex hex) { + int x, y; + struct HL_point center; + double yc; + + double stride = 1.5/sqrt(3.0); + + x = hex.x; + y = hex.y; + + center.x = x * stride; + + if (x >= 0) yc = y + ((x + 1) % 2) / 2.0 - 0.5; + if (x < 0) yc = y + ((-x + 1) % 2) / 2.0 - 0.5; + + center.y = yc; + + return center; +} + +/* + * This function assumes that the hexes are one unit across, and vertically + * oriented. If that is not the case, you will need to transform + * your input coordinates first. + */ +struct HL_hex HL_bin(double x, double y) { + return HL_hexbin(1.0, x, y); +} + +struct HL_isohex HL_xy2ijk(struct HL_hex hex) { + int pi, pj, pk; + int x, y; + struct HL_isohex iso; + + x = hex.x; + y = hex.y; + + pi = x; + pj = -y; + + if (x < 0) { + pj = pj + (-x + 1) / 2; + } else { + pj = pj - x/2; + } + pk = -pi - pj; + + iso.i = pi; + iso.j = pj; + iso.k = pk; + + return iso; +} + +#if 0 + +static int xy2ijk(int x, int y, int *i, int *j, int *k) { + int pi, pj, pk; + + pi = x; + pj = -y; + if (x < 0) { + pj = pj + (-x + 1) / 2; + } else { + pj = pj - x/2; + } + pk = -pi - pj; + + if (i) *i = pi; + if (j) *j = pj; + if (k) *k = pk; + + return HL_cantor_xy(x,y); +} +static int ijk2xy(int i, int j, int k, int *x, int *y) { + int px, py; + + px = i; + + /* py = -j - i/2; */ + py = -j; + + if (i < 0) { + py += (-i + 1)/2; + } else { + py -= i/2; + } + + if (x) *x = px; + if (y) *y = py; + + return HL_cantor_xy(px,py); +} + +#endif + +struct HL_hex HL_ijk2xy(struct HL_isohex iso) { + int px, py; + struct HL_hex xy; + int i,j; + + i = iso.i; + j = iso.j; + + px = i; + + /* py = -j - i/2; */ + py = -j; + + if (i < 0) { + py += (-i + 1)/2; + } else { + py -= i/2; + } + + xy.x = px; + xy.y = py; + + return xy; +} + + +static void xy2ijkp(struct HL_hex h, int *ijk) { + struct HL_isohex iso; + + iso = HL_xy2ijk(h); + ijk[0] = iso.i; + ijk[1] = iso.j; + ijk[2] = iso.k; +} + +int HL_distance(struct HL_hex from, struct HL_hex to) { + int dist = 0, i;; + int fc[3], tc[3]; + + xy2ijkp(from, fc); + xy2ijkp(to, tc); + + for (i=0;i<=2;i++) { + dist += abs(fc[i] - tc[i]); + } + + return dist / 2; +} + +int HL_hexes_within_range(struct HL_hex hex, int range, struct HL_hex *list, int size) { + int count = 0; + int i; + + if (range == 0) { + return HL_hexes_at_range(hex, 0, list, size); + } + + for (i=1;i<=range;i++) { + count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count); + } + return count; +} + +int HL_hexes_at_range(struct HL_hex hex, int range, struct HL_hex *list, int size) { + int q; /* p and q are count/loop vars */ + struct HL_isohex iso; + + + if (range == 0) { + if (list) { + list[0] = hex; + } + return 1; + } else if (range < 0) { + return 0; + } + + /* TODO don't bother to collect if the list isn't big enough? */ + /* i.e. if (!list || size < range * 6) */ + if (!list || size < 1) return range * 6; + + iso = HL_xy2ijk(hex); + + iso.i += range; + iso.k = -iso.i - iso.j; + + hex = HL_ijk2xy(iso); + + for(q=0; q INT_MAX - ydim - 1) + return 0; + + return 1; +} + +int HL_map_max_dimension(void) { + int low, high, try; + + low = 1; high = INT_MAX/2; + + while (low != high - 1) { + try = (low + high) / 2; + if (HL_map_bounds_ok(try,try)) { + low = try; + } else { + high = try; + } + } + + return low; +} + +struct hex { + int iso; + int x, y, z; +}; + +/* y *must* be positive down as the xy /iso conversion assumes this */ +static int hex_xy(struct hex *h) { + if (!h->iso) return 1; + if (h->x >= 0) { + h->y = -h->y - (h->x+1)/2; + } else { + /* need to round toward -inf, not toward zero, so x-1 */ + h->y = -h->y - h->x/2; + } + h->iso = 0; + + return 1; +} + +#if 0 + +static int hex_iso(struct hex *h) { + if (h->iso) return 1; + + if (h->x >= 0) { + h->y = (-h->y - (h->x+1)/2); + } else { + /* need to round toward -inf, not toward zero, so x-1 */ + h->y = (-h->y - (h->x)/2); + } + + h->z = -h->x - h->y; + h->iso = 1; + return 1; +} + +#endif + +#define COS30 (.866025403784438646763723170752) + +struct HL_hex HL_hexbin(double width, double x, double y) { + double z, rx, ry, rz; + double abs_dx, abs_dy, abs_dz; + int ix, iy, iz, s; + struct hex h; + struct HL_hex hex; + + /*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */ + x = x / COS30; + y = y - x / 2.0; /* adjustment for rotated X */ + + /* adjust for actual hexwidth */ + x /= width; + y /= width; + + z = -x - y; + + ix = rx = floor(x + 0.5); + iy = ry = floor(y + 0.5); + iz = rz = floor(z + 0.5); + + s = ix + iy + iz; + + if (s) { + abs_dx = fabs(rx - x); + abs_dy = fabs(ry - y); + abs_dz = fabs(rz - z); + + if (abs_dx >= abs_dy && abs_dx >= abs_dz) { + ix -= s; + } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) { + iy -= s; + } else { + iz -= s; + } + } + h.x = ix; + h.y = iy; + h.z = iz; + h.iso = 1; + + hex_xy(&h); + + hex.x = h.x; + hex.y = h.y; + + return hex; +}