]> pd.if.org Git - hexagon/blob - hexagon.c
61bb47b0fd80429ddd49e57df1e72ebb450cfc12
[hexagon] / 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[] = {
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 }