pd.if.org Git - hexagon/blob - lib/cantor.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 inversenatcantor(int cantor, int *x, int *y) {
   9         int w, t, py;
  10
  11         cantor -= 1;
  12
  13         w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0);
  14         t = (w * w + w)/2;
  15
  16         py = cantor - t;
  17
  18         if (y) *y = py;
  19         if (x) *x = w - py;
  20
  21         return cantor;
  22 }
  23
  24
  25 static int inversecantor(int cantor, int *x, int *y) {
  26         if (cantor < 0) {
  27                 inversenatcantor(-cantor, x, y);
  28                 if (x) {
  29                         if (*x % 2) {
  30                                 *x = -(*x+1)/2;
  31                         } else {
  32                                 *x = *x / 2;
  33                         }
  34                 }
  35                 if (y) {
  36                         if (*y % 2) {
  37                                 *y =  -(*y+1)/2;
  38                         } else {
  39                                 *y = *y/2;
  40                         }
  41                 }
  42         } else {
  43                 inversenatcantor(cantor, x, y);
  44         }
  45
  46         return cantor;
  47 }
  48 /*
  49  * map non negative integer pairs to their cantor pairing function
  50  * number, plus one.  We add one so that the result is never zero,
  51  * leaving zero to be "invalid" or "none" or what have you.
  52  */
  53
  54 static int natcantor(int x, int y) {
  55         return (x+y) * (x + y + 1) / 2 + y+1;
  56 }
  57
  58 /* See http://en.wikipedia.org/wiki/Cantor_pairing_function */
  59 /* see also http://szudzik.com/ElegantPairing.pdf */
  60 /*
  61  * if either coordinate is negative, map the integers onto the
  62  * whole numbers, and then return the negative of the adjusted
  63  * cantor number.  As for most grids negative coordinates will
  64  * be invalid, this will allow for a <= 0 test for invalid
  65  * or out of bounds (on the negative side anyway, you'll
  66  * still have to test for out of range on the positive side).
  67  *
  68  * TODO figure out what the maximum supported coordinates are
  69  * for given integer sizes.
  70  */
  71 int HL_cantor_xy(int x, int y) {
  72         if (x < 0 || y < 0) {
  73                 x = abs(2 * x) - (x < 0);
  74                 y = abs(2 * y) - (y < 0);
  75                 return -natcantor(x, y);
  76         }
  77         return natcantor(x,y);
  78 }
  79
  80 int HL_cantor(struct HL_hex h) {
  81         int x, y;
  82
  83         x = h.x;
  84         y = h.y;
  85
  86         if (x < 0 || y < 0) {
  87                 x = abs(2 * x) - (x < 0);
  88                 y = abs(2 * y) - (y < 0);
  89                 return -natcantor(x, y);
  90         }
  91         return natcantor(x,y);
  92 }
  93
  94 struct HL_hex HL_uncantor(int cantor) {
  95         struct HL_hex h;
  96
  97         inversecantor(cantor, &h.x, &h.y);
  98
  99         return h;
 100 }