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; }
}