// both the outer outline and the outline of a hole are called a "trace"
// should return outer outline first and then outline of holes

// seems to return first point again at the end sometimes

srecord noeq RegionBorder_innerPoints_withDiagonals(IImageRegion region) extends AbstractBorderTracer {
  Rect bounds; // region bounds
  int x, y;
  int dir; // current direction (1 to 8)
  Iterator<Pt> it;
  byte[] reachedInDirections; // bits 0 to 7
  bool tracing;
  int nTrace; // 1 for outline, 2+ for hole

  void init {
    bounds = region.bounds();
    reachedInDirections = new byte[area(bounds)];
    it = region.pixelIterator();
  }

  public bool step() {
    if (reachedInDirections == null) init();
    
    if (tracing)
      ret walkOnePixel();
    else
      ret findFirstPixel();
  }
  
  bool walkOnePixel() {
    int posInBounds = (y-bounds.y)*bounds.w+x-bounds.x;
    if ((reachedInDirections[posInBounds] & (1 << (dir-1))) != 0) {
      traceDone();
      tracing = false;
      ret includeHoles;
    }
    
    reachedInDirections[posInBounds] |= (byte) 1 << (dir-1);
    printVars ifdef RegionBorder_innerPoints_debug("foundPoint", +x, +y);
    foundPoint(x, y);
      
    // try left, half left, straight, half right, right, back
    for (int turn = -2; turn <= 4; turn++) {
      int newDir = modRange_incl(dir+turn, 1, 8);
      Pt d = onePathDirection(newDir);
      int x2 = x+d.x, y2 = y+d.y;
      bool b = region.contains(x2, y2);
      if (b) {
        printVars ifdef RegionBorder_innerPoints_debug(+x, +y, +dir, +turn, +newDir, +d, +x2, +y2, +b);
        x = x2; y = y2; dir = newDir;
        true;
      }
    }
    
    print ifdef RegionBorder_innerPoints_debug("fall through");
    true; // no black pixels found in any direction - region must be a single pixel
  }
    
  bool findFirstPixel() {
    // search for first border pixel
    
    if (!it.hasNext()) false; // done
    Pt p = it.next();
    x = p.x; y = p.y;
      
    int posInBounds = (y-bounds.y)*bounds.w+x-bounds.x;
    if (reachedInDirections[posInBounds] != 0) true; // seen pixel before
    
    // if pixel above is empty, walk to the right
    if (!region.contains(x, y-1))
      ret true with startTrace(4);
      
    // if pixel on the left is empty, walk upwards
    if (!region.contains(x-1, y))
      ret true with startTrace(2);
    
    // if pixel on the right is empty, walk downwards
    if (!region.contains(x+1, y))
      ret true with startTrace(6);
    
    // if pixel below is empty, walk left
    if (!region.contains(x, y+1))
      ret true with startTrace(8);
  
    // not a border pixel, continue search
    true;
  }
  
  void startTrace(int dir) {
    this.dir = dir;
    
    // mark point reached from all directions in next step
    int posInBounds = (y-bounds.y)*bounds.w+x-bounds.x;
    reachedInDirections[posInBounds] = (byte) ~(1 << (dir-1));
      
    set tracing;
    printVars ifdef RegionBorder_innerPoints_debug("startTrace", +dir, +x, +y);
    newTrace(++nTrace > 1);
  }
  
  void foundPoint(int x, int y) { foundPoint(pt(x, y)); }
  
  // get all points as list
  
  simplyCached L<Pt> allPoints() {
    new PtBuffer l;
    onFoundPoint(p -> l.add(p));
    run();
    ret l;
  }
  
  // get outline as OnePath
  
  simplyCached OnePath onePath() {
    includeHoles(false);
    ret new OnePath(allPoints(), true);
  }
  
  // or as OnePathWithOrigin
  
  simplyCached OnePathWithOrigin onePathWithOrigin() {
    includeHoles(false);
    ret new OnePathWithOrigin(allPoints(), true);
  }

  // for debugging 
  void runAndPrint {
    onNewTrace(hole -> print(!hole ? "new outline" : "new hole"));
    onTraceDone(-> print("traceDone"));
    onFoundPoint(p -> print("foundPoint " + p));
    stepMaxWithStats(this, 10000);
  }
  
  bool tracingHole() { ret nTrace > 1; }
}