Transpiled version (8195L) is out of date.
// 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<Img extends WidthAndHeight>(IImageRegion<Img> region) extends G22Mesh is Steppable { settable bool debug; settable bool debugDroppingUnnecessaryAnchors; settable bool autoSimplify = true; // TEMPORARY DATA ItIt<Pt> regionIterator; new L<WorkItem> queue; new PtSet pointsSeen; // p is a point in 3x3 neighborhood of anchor srecord noeq WorkItem(Anchor anchor, Pt p) {} public bool step() { // first, initialize iterator if (regionIterator == null) regionIterator = region.pixelIterator(); // 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 = anchorMap.get(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); 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 = new(l(anchorMap)+1, p); anchorMap.put(p, anchor); //anchors.add(anchor); // 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(curves); for (Curve curve : cloneList(curves)) { if (curve.start != curve.end) continue; if (curve.length() > 3) continue; if (debug) print("Removing short loop: " + curve); removeCurve(curve); } ret l(curves) < n; } // returns true if anything changed bool dropLengthOneCurves() { int n = l(anchorMap); for (Curve curve : cloneList(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) mergeAnchor(curve.end, curve.start); else mergeAnchor(curve.start, curve.end); } ret l(anchorMap) < n; } void removeCurve(Curve curve) { curves.remove(curve); curve.start.outgoingCurves.remove(curve); curve.end.incomingCurves.remove(curve); } // moves a1's connections to a2, deletes a1 void mergeAnchor(Anchor a1, Anchor a2) { if (debug) printVarsInMultipleLines("mergeAnchor", +a1, +a2); for (Curve curve : a1.outgoingCurves) { // first step is now going from a2 to a1 curve.path.insertStep(0, ptMinus(a1.pt, a2.pt)); curve.path.origin(a2.pt); curve.start = a2; a2.outgoingCurves.add(curve); } for (Curve curve : a1.incomingCurves) { // last step is now going from a1 to a2 curve.path.addStep(ptMinus(a2.pt, a1.pt)); curve.end = a2; a2.incomingCurves.add(curve); } anchorMap.remove(a1.pt); } // returns true if anything changed bool dropUnnecessaryAnchors() { int n = l(anchorMap); for (Anchor anchor : cloneValues(anchorMap)) { 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); // Find the endpoints of the new curve (either 1 or 2 anchors) Set<Anchor> anchors = concatMapToSet(curves, c -> c.anchors()); anchors.remove(this); if (debugDroppingUnnecessaryAnchors) printVarsInMultipleLines(+curves, +anchors); // 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(anchorMap.get(first(points))); Anchor anchor2 = assertNotNull(anchorMap.get(last(points))); if (debugDroppingUnnecessaryAnchors) printVarsInMultipleLines(+anchor, +anchor1, +anchor2); anchorMap.remove(anchor.pt); addCurve(new Curve(anchor1, anchor2, points)); } ret l(anchorMap) < n; } void addCurve(Curve curve) { curves.add(curve); } }
Began life as a copy of #1034998
download show line numbers debug dex old transpilations
Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
Snippet ID: | #1035010 |
Snippet name: | G22SkeletonToMesh [old, superceded by G22SkeletonToMesh_v2] |
Eternal ID of this version: | #1035010/63 |
Text MD5: | e2d240043f868cc84b1c0f11d4dcafed |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2022-05-07 02:49:08 |
Source code size: | 7547 bytes / 241 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 231 / 588 |
Version history: | 62 change(s) |
Referenced in: | [show references] |