transient sclass HexagonalBWIntegralImage {

  final int w, h;

  // data[0] is the sharp edge, data[1] the blunt edge

  final int[][] data = new int[2][];

  // the column sums in three directions

  // north, north west, north east

  final int[][] columnSums = new int[3][];

  int offset1;

  final static double slant = sqrtAThird();

  *(BufferedImage img) { this(BWImage(img)); }

  *(BWImage img) {

    w = img.w();

    h = img.h();

    for i to 2:

      data[0] = new int[w*h];

    columnSums[0] = new int[h];

    int i = 0;

    int lastShift = 0;

    for y to h: {

      int sum = 0;

      int shift = iround(y*slant);

      int inc = shift-lastShift;

      for x to w: {

        // grab pixels

        int pixel = img.getInt(x, y);

        sum += pixel;

        // calc wedges

        data[0][i] = data[1][i] = sum;

        if (y != 0) {

          if (x >= inc)

            data[0][i] += data[0][i-w-inc];

          if (x+inc < w)

            data[1][i] += data[1][i-w+inc];

        }

        i++;

      }

      columnSums[0][y] = sum;

    }

    offset1 = iceil(h*slant);

    columnSums[1] = new int[offset1+w];

    columnSums[2] = new int[w+offset1];

    int sum = 0;

    for (int x = w-1; x >= -offset1; x--) {

      int y = 0;

      double xfrac = x;

      while true {

        int x2 = iround(xfrac);

        if (x2 >= w)

          break;

        sum += img.getInt(x2, y);

        y++;

        xfrac += slant;

      }

      columnSums[1][x-offset1] = sum;

    }

    sum = 0;

    for (int x = 0; x < w+offset1; x++) {

      int y = 0;

      double xfrac = x;

      while true {

        int x2 = iround(xfrac);

        if (x2 < 0)

          break;

        sum += img.getInt(x2, y);

        y++;

        xfrac -= slant;

      }

      columnSums[2][x] = sum;

    }

  }

  int getData(int x, int y, int type) {

    if (x <= 0 || y <= 0) ret 0;

    ret data[type][y*w+x];

  }

  int upPointingTriangleSum(int x1, int x2, int y2) {

    // formula:

    // north west wedge from bottom right corner

    // - left wedge from top corner

    // + bottom left wedge from bottom left corner

    int xMid = (x1+x2)/2, y1 = iround(y2-(x2-x1)*sqrt3());

    ret topLeftWedge(x2, y2)

      -leftWedge(xMid, y1)

      -bottomLeftWedge(x1, y2);

  }

  int downPointingTriangleSum(int x1, int x2, int y1) {

    // formula:

    // top wedge from bottom corner

    // - big wedge from top right corner

    // + top left wedge from top left corner

    int xMid = (x1+x2)/2, y2 = iround(y1+(x2-x1)*sqrt3());

    ret topWedge(xMid, y2)

      -bigWedge(x2, y1)

      -topLeftWedge(x1, y1);

  }

  int topLeftWedge(int x, int y) {

    ret getData(x, y, 0);

  }

  int smallWedge(int x, int y) {

    ret getData(x, y, 0);

  }

  int bigWedge(int x, int y) {

    ret getData(x, y, 1);

  }

  // big wedge minus small wedge

  int topWedge(int x, int y) {

    ret bigWedge(x, y)-smallWedge(x, y);

  }

  int leftWedge(int x, int y) {

    ret columnSum(x, y, 1)-topWedge(x, y);

  }

  int bottomLeftWedge(int x, int y) {

    ret columnSum(x, y, 1)-bigWedge(x, y);

  }

  int columnSum(int x, int y, int direction) {

    if (direction == 0) ret columnSums[0][y*w+x];

    else if (direction == 1) ret columnSums[1][y*w+x+iround(y*slant)];

    else ret columnSums[2][y*w-x-iround(y*slant)];

  }

  public int getWidth() { ret w; }

  public int getHeight() { ret h; }

  int w() { ret w; }

  int h() { ret h; }

}