X-Git-Url: https://pd.if.org/git/?p=hexagon;a=blobdiff_plain;f=hexagon.c;fp=hexagon.c;h=155a5d2f1bd4676797c0dbb9c226d6d21391e34c;hp=2dd1f3a3e5e6094b5633e8ebc93e08d0a6ba8d14;hb=06868ef42497f1cbc480831029f5f69b395dfdd2;hpb=c5a7aa5029146b2bcea5daae53c6aa3e5e33ed04 diff --git a/hexagon.c b/hexagon.c index 2dd1f3a..155a5d2 100644 --- a/hexagon.c +++ b/hexagon.c @@ -5,7 +5,27 @@ #include #include -static int inversecantor(int cantor, int *x, int *y); +/* 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 @@ -101,53 +121,57 @@ static double hexpthd[6][2] = { #endif -/* -c = 1.0 = distance from center to vertex -b = distance to hex side -a = distance along hex side - -A = angle at point center, this is the polar coord angle -B = angle from vertex, this is 60 degrees -C = Other angle, which is 180 - 60 - A = 120 - A - -sin B = sin 60 = sqrt(3) / 2 -cos B = cos 60 = 1/2 - -b = c * sin B / ( sin A cos B + sin B cos A) - -c * sin B / ( sin A cos B + sin B cos A) - -0.5 * sqrt3 -------------- -sinA 0.5 + sqrt3 * 0.5 cosA - -sqrt3 -------------- -sinA + sqrt3 cosA - -b= -3 -------------- -cosA + sqrt3 sinA - -x = b cosA -y = b sinA -*/ - #define RD (180.0 / M_PI) /* angle ranges from 0-6 */ /* distance is 0 at origin, 1.0 at the hex side */ -/* return the polar distance ? */ -double HL_polar(double angle, double distance, double *x, double *y) { - double A, B, C, b, c; - double sinB, sinC; #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; @@ -155,36 +179,34 @@ double HL_polar(double angle, double distance, double *x, double *y) { A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */ B = M_PI / 3.0; - C = M_PI - A - B; + C = M_PI - B - A; - sinB = sin(B); - sinC = sin(C); + b = sin(B) / sin(C); - c = 1.0; - c = HL_vertexv[0]; -#if 0 - /* provided for completeness, but we don't use the value */ - sinA = sin(A); - a = c * sinA / sinC; -#endif - b = c * sinB / sinC; + /* 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); - if (x) { - *x = b * cos(angle); - } + pt.x = distance * b * cos(angle); + pt.y = distance * b * sin(angle); - if (y) { - *y = b * sin(angle); + if (d) { + *d = distance * b; } - return b; + return pt; } -void HL_vertices(int cantor, double *vc) { +void HL_vertices(struct HL_hex hex, double *vc) { int i; double xc, yc; + struct HL_point center; - HL_hexcenter(cantor, &xc, &yc); + center = HL_hexcenter(hex); + xc = center.x; + yc = center.y; for (i=0; i<6; i++) { *vc++ = hexptvd[i][0] + xc; @@ -194,36 +216,31 @@ void HL_vertices(int cantor, double *vc) { *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 -double HL_center_x(int cantor) { - double x; - - HL_hexcenter(cantor, &x, 0); - return x; -} +struct HL_point HL_hexcenter(struct HL_hex hex) { + int x, y; + struct HL_point center; + double yc; -double HL_center_y(int cantor) { - double y; + double stride = 1.5/sqrt(3.0); - HL_hexcenter(cantor, 0, &y); - return y; -} + x = hex.x; + y = hex.y; -int HL_hexcenter(int cantor, double *xc, double *yc) { - int x, y; - double stride = 1.5/sqrt(3.0); + center.x = x * stride; - inversecantor(cantor, &x, &y); + if (x >= 0) yc = y + ((x + 1) % 2) / 2.0 - 0.5; + if (x < 0) yc = y + ((-x + 1) % 2) / 2.0 - 0.5; - if (xc) *xc = x * stride; - if (yc && x >= 0) *yc = y + ((x + 1) % 2) / 2.0 - 0.5; - if (yc && x < 0) *yc = y + ((-x + 1) % 2) / 2.0 - 0.5; + center.y = yc; - return cantor; + return center; } /* @@ -231,10 +248,37 @@ int HL_hexcenter(int cantor, double *xc, double *yc) { * oriented. If that is not the case, you will need to transform * your input coordinates first. */ -int HL_cantor_bin(double x, double y) { - return HL_hexbin(1.0, x, y, 0, 0); +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; @@ -253,7 +297,6 @@ static int xy2ijk(int x, int y, int *i, int *j, int *k) { return HL_cantor_xy(x,y); } - static int ijk2xy(int i, int j, int k, int *x, int *y) { int px, py; @@ -274,16 +317,49 @@ static int ijk2xy(int i, int j, int k, int *x, int *y) { return HL_cantor_xy(px,py); } -int HL_cantor_ijk(int i, int j, int k) { - return ijk2xy(i,j,k,0,0); +#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; } -int HL_distance(int from, int to) { + +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]; - HL_cantor_arrays(from, 0, fc); - HL_cantor_arrays(to, 0, tc); + xy2ijkp(from, fc); + xy2ijkp(to, tc); for (i=0;i<=2;i++) { dist += abs(fc[i] - tc[i]); @@ -292,7 +368,7 @@ int HL_distance(int from, int to) { return dist / 2; } -int HL_hexes_within_range(int hex, int range, int *list, int size) { +int HL_hexes_within_range(struct HL_hex hex, int range, struct HL_hex *list, int size) { int count = 0; int i; @@ -306,9 +382,10 @@ int HL_hexes_within_range(int hex, int range, int *list, int size) { return count; } -int HL_hexes_at_range(int hex, int range, int *list, int size) { +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 */ - int c[3]; /* ijk coord array */ + struct HL_isohex iso; + if (range == 0) { if (list) { @@ -323,10 +400,12 @@ int HL_hexes_at_range(int hex, int range, int *list, int size) { /* i.e. if (!list || size < range * 6) */ if (!list || size < 1) return range * 6; - HL_cantor_arrays(hex, 0, c); - c[0] += range; - c[2] = -c[0] - c[1]; - hex = HL_cantor_ijkp(c); + iso = HL_xy2ijk(hex); + + iso.i += range; + iso.k = -iso.i - iso.j; + + hex = HL_ijk2xy(iso); for(q=0; q 5) return 0; - - return HL_adjhex(start, dir); -} - /* direction 0 is positive X , counter clockwise from there */ -int HL_adjhex(int start, int dir) { +struct HL_hex HL_adjhex(struct HL_hex hex, int dir) { int c[3]; + struct HL_isohex iso; - HL_cantor_arrays(start, 0, c); + iso = HL_xy2ijk(hex); + c[0] = iso.i; + c[1] = iso.j; + c[2] = iso.k; switch (dir%6) { case 2: @@ -363,65 +440,18 @@ int HL_adjhex(int start, int dir) { c[0]--; ; c[2]++; break; } - return HL_cantor_ijkp(c); -} - -int HL_cantor_xyp(int *xy) { - return HL_cantor_xy(xy[0], xy[1]); -} - -int HL_cantor_ijkp(int *ijk) { - return HL_cantor_ijk(ijk[0], ijk[1], ijk[2]); -} - -int HL_cantor_arrays(int can, int *xy, int *ijk) { - return HL_cantor_decode(can, xy, xy ? xy+1 : 0, - ijk, ijk ? ijk+1 : 0, ijk ? ijk+2 : 0); -} - -int HL_cantor_decode(int can, int *x, int *y, int *i, int *j, int *k) { - int px, py; - - inversecantor(can, &px, &py); - if (x) *x = px; - if (y) *y = py; - - xy2ijk(px, py, i, j, k); - - return can; -} - -int HL_cantor_i(int cantor) { - int i; - - HL_cantor_decode(cantor, 0,0, &i,0,0); - return i; -} - -int HL_cantor_j(int cantor) { - int j; + iso.i = c[0]; + iso.j = c[1]; + iso.k = c[2]; - HL_cantor_decode(cantor, 0,0, 0,&j,0); - return j; + return HL_ijk2xy(iso); } -int HL_cantor_k(int cantor) { - int k; - - HL_cantor_decode(cantor, 0,0, 0,0,&k); - return k; -} - -int HL_cantor_x(int cantor) { - int x; - inversecantor(cantor, &x, 0); - return x; -} - -int HL_cantor_y(int cantor) { - int y; - inversecantor(cantor, 0, &y); - return y; +int HL_adjhexp(struct HL_hex hex, int dir, struct HL_hex *adj) { + if (adj) { + *adj = HL_adjhex(hex, dir); + } + return dir; } /* Determine if a map with these dimensions will overflow */ @@ -454,78 +484,6 @@ int HL_map_max_dimension(void) { return low; } -static int inversenatcantor(int cantor, int *x, int *y) { - int w, t, py; - - cantor -= 1; - - w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0); - t = (w * w + w)/2; - - py = cantor - t; - - if (y) *y = py; - if (x) *x = w - py; - - return cantor; -} - -/* - * map non negative integer pairs to their cantor pairing function - * number, plus one. We add one so that the result is never zero, - * leaving zero to be "invalid" or "none" or what have you. - */ - -static int natcantor(int x, int y) { - return (x+y) * (x + y + 1) / 2 + y+1; -} - -/* See http://en.wikipedia.org/wiki/Cantor_pairing_function */ -/* see also http://szudzik.com/ElegantPairing.pdf */ -/* - * if either coordinate is negative, map the integers onto the - * whole numbers, and then return the negative of the adjusted - * cantor number. As for most grids negative coordinates will - * be invalid, this will allow for a <= 0 test for invalid - * or out of bounds (on the negative side anyway, you'll - * still have to test for out of range on the positive side). - * - * TODO figure out what the maximum supported coordinates are - * for given integer sizes. - */ -int HL_cantor_xy(int x, int y) { - if (x < 0 || y < 0) { - x = abs(2 * x) - (x < 0); - y = abs(2 * y) - (y < 0); - return -natcantor(x, y); - } - return natcantor(x,y); -} - -static int inversecantor(int cantor, int *x, int *y) { - if (cantor < 0) { - inversenatcantor(-cantor, x, y); - if (x) { - if (*x % 2) { - *x = -(*x+1)/2; - } else { - *x = *x / 2; - } - } - if (y) { - if (*y % 2) { - *y = -(*y+1)/2; - } else { - *y = *y/2; - } - } - } else { - inversenatcantor(cantor, x, y); - } - - return cantor; -} - struct hex { int iso; int x, y, z; @@ -566,11 +524,12 @@ static int hex_iso(struct hex *h) { #define COS30 (.866025403784438646763723170752) -int HL_hexbin(double width, double x, double y, int *i, int *j) { +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; @@ -607,7 +566,9 @@ int HL_hexbin(double width, double x, double y, int *i, int *j) { h.iso = 1; hex_xy(&h); - if (i) *i = h.x; - if (j) *j = h.y; - return HL_cantor_xy(h.x, h.y); + + hex.x = h.x; + hex.y = h.y; + + return hex; }