// G22SkeletonToMesh converts a skeleton (thinned image region)
// to a mesh.

// A "mesh" is a set of points ("anchors") connected through curves.
// More docs at G22Mesh

srecord noeq G22SkeletonToMesh_v2<Img extends WidthAndHeight>(IImageRegion<Img> region) is Steppable {
  settable bool debug;
  settable bool debugDroppingUnnecessaryAnchors;
  settable bool autoSimplify = true;

  // the generated mesh
  
  gettable G22Mesh mesh;
  
  // TEMPORARY DATA
  
  ItIt<Pt> regionIterator;
  new L<WorkItem> queue;
  new PtSet pointsSeen;
  
  delegate Anchor, Curve to G22Mesh.
  delegate getAnchor, addCurve, removeAnchor, removeCurve,
    mergeAnchorInto to mesh.
  
  // p is a point in 3x3 neighborhood of anchor
  srecord noeq WorkItem(Anchor anchor, Pt p) {}
  
  G22Mesh get() { if (mesh == null) run(); ret mesh; }
  
  void run { stepAll(this); }

  public bool step() {
    // first, initialize iterator & mesh
    if (mesh == null) {
      regionIterator = region.pixelIterator();
      mesh = new G22Mesh;
      setMetaSrc(mesh, this);
    }
    
    // then check queue for work
    if (nempty(queue)) {
      WorkItem work = popLast(queue);
      
      Pt p = work.p;
      
      new PtBuffer curvePoints;
      curvePoints.add(work.anchor.pt); // add anchor to path
      Anchor endAnchor = null;

      if (debug) print("Exploring from " + work.anchor.pt + " / " + p);
      
      while ping (true) {
        if (debug) print("Curve point " + p);
        curvePoints.add(p);
        
        // did we hit another anchor?
        endAnchor = getAnchor(p);
        if (endAnchor != null) {
          if (debug) print("Hit anchor " + endAnchor);
          break;
        }

        // check if we visited this point already
        if (!pointsSeen.add(p)) {
          if (l(curvePoints) == 2)
            true; // It's a 1-pixel curve anyway, just forget it
          else
            // If this is an actual thing, we should make a proper anchor here (splitting existing curves).
            // I don't think it's actually a thing though
            warn("Surprising seen point (" + curvePoints + "). Adding as anchor");
          break;
        }
        
        PtBuffer branches = unexploredPointsAround(p);
        
        // line ends or branches - same thing for us, it means our curve ends and we create a new anchor here
        if (l(branches) != 1) {
          if (debug) print("Branch count: " + l(branches));
          break;
        } else
          p = first(branches); // curve continues
      }

      if (endAnchor == null)
        endAnchor = newAnchor(p);
        
      mesh.addCurve(new Curve(work.anchor, endAnchor, curvePoints));
      true;
    }
    
    // finally look for next point in region
    if (regionIterator.hasNext()) {
      Pt p = regionIterator.next();
      
      // check if point already seen, otherwise mark as seen
      if (!pointsSeen.add(p)) true;
      
      // new point - save as anchor
      newAnchor(p);
      true;
    }
    
    // last step, simplify
      
    if (autoSimplify) simplify();
    false;
  }

  Anchor newAnchor(Pt p) {  
    Anchor anchor = mesh.newAnchor(p);

    // explore in all directions
    for (Pt p2 : unexploredPointsAround(p))
      queue.add(new WorkItem(anchor, p2));
      
    ret anchor;
  }
  
  PtBuffer unexploredPointsAround(Pt p) {
    new PtBuffer out;
    for (int dir = 1; dir <= 8; dir++) {
      Pt p2 = onePathDirection(p, dir);
      if (region.contains(p2) && !pointsSeen.contains(p2))
        out.add(p2);
    }
    ret out;
  }
  
  bool simplify() {
    ret 0 != stepAll(combineSteppables_dontDropEnded(
      l0 dropLengthOneCurves,
      l0 dropShortLoops,
      l0 dropUnnecessaryAnchors));
  }
  
  // drops very short curves connecting a node to itself
  // returns true if anything changed
  bool dropShortLoops() {
    int n = l(mesh.curves());
    for (Curve curve : cloneList(mesh.curves())) {
      if (curve.start != curve.end) continue;
      if (curve.length() > 3) continue;
      
      if (debug) print("Removing short loop: " + curve);
      removeCurve(curve);
    }
    
    ret l(mesh.curves()) < n;
  }
      
  // returns true if anything changed
  bool dropLengthOneCurves() {
    int n = l(mesh.anchors());
    for (Curve curve : cloneList(mesh.curves())) {
      if (curve.length() != 1) continue;
      
      // Decide which anchor to keep
      bool keepStartAnchor = curve.start.arity() >= curve.end.arity();
      
      // Forget curve
      removeCurve(curve);
      
      // Merge the less important (defined as: less connected) anchor into the other one
      if (keepStartAnchor)
        mergeAnchorInto(curve.end, curve.start);
      else
        mergeAnchorInto(curve.start, curve.end);
    }
    ret l(mesh.anchors()) < n;
  }
  
  // returns true if anything changed
  bool dropUnnecessaryAnchors() {
    int n = l(mesh.anchors());
    for (Anchor anchor : cloneList(mesh.anchors())) {
      if (anchor.arity() != 2) continue;
      if (anchor.isRingAnchor()) continue;
      
      // It's a non-branching anchor sitting on a curve - we can drop it.
      if (debugDroppingUnnecessaryAnchors) print("Dropping " + anchor);
      
      // This list will have length 2
      L<Curve> curves = concatLists(anchor.incomingCurves, anchor.outgoingCurves);
      
      if (debugDroppingUnnecessaryAnchors) printVars(+curves);
      
      // Collect points for merged curve
      
      // Process curve 1, optionally reverse it so it does NOT start at the middle anchor 
      Curve curve1 = first(curves);
      removeCurve(curve1);
      L<Pt> points1 = curve1.path.pointList();
      if (eq(first(points1), anchor.pt)) reverseInPlace(points1);
      
      // Process curve 2, optionally reverse it so it DOES start at the middle anchor 
      Curve curve2 = second(curves);
      removeCurve(curve2);
      L<Pt> points2 = curve2.path.pointList();
      if (!eq(first(points2), anchor.pt)) reverseInPlace(points2);
      
      // Drop overlapping point, append points2 to points1
      assertEquals(anchor.pt, popLast(points1));
      L<Pt> points = points1;
      addAll(points, points2);
      
      Anchor anchor1 = assertNotNull(getAnchor(first(points)));
      Anchor anchor2 = assertNotNull(getAnchor(last(points)));
      
      if (debugDroppingUnnecessaryAnchors) printVarsInMultipleLines(+anchor, +anchor1, +anchor2);
      
      removeAnchor(anchor);
      addCurve(new Curve(anchor1, anchor2, points));
    }
    
    ret l(mesh.anchors()) < n;
  }
}

Began life as a copy of #1035010