// 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_v2(IImageRegion region) extends AbstractBorderTracer {

  Rect bounds; // region bounds

  int x, y, dir;

  Iterator<Pt> it;

  byte[] reachedInDirections; // bits 0 to 3

  bool tracing;

  int nTrace; // 1 for outline, 2+ for hole

  // directions (0 = right, 1 = down, 2 = left, 3 = up)

  static Pt[] directions = {

    pt(1, 0), pt(0, 1), pt(-1, 0), pt(0, -1) // r, d, l, u

  };

  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)) != 0) {

      traceDone();

      tracing = false;

      ret includeHoles;

    }

    reachedInDirections[posInBounds] |= (byte) 1 << dir;

    foundPoint(x, y);

    for (int turn = 3; turn <= 6; turn++) { // try left, straight, right, back

      int newDir = (dir+turn) & 3;

      Pt d = directions[newDir];

      int x2 = x+d.x, y2 = y+d.y;

      bool b = region.contains(x2, y2);

      ifdef RegionBorder_innerPoints_debug

        printVars(+x, +y, +dir, +turn, +newDir, +x2, +y2, +b);

      endifdef

      if (b) {

        x = x2; y = y2; dir = newDir;

        true;

      }

    }

    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(0);

    // if pixel on the left is empty, walk upwards

    if (!region.contains(x-1, y))

      ret true with startTrace(3);

    // if pixel on the right is empty, walk downwards

    if (!region.contains(x+1, y))

      ret true with startTrace(1);

    // if pixel below is empty, walk left

    if (!region.contains(x, y+1))

      ret true with startTrace(2);

    // 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) (15 & ~(1 << dir));

    set tracing;

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

}