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

}