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