option to avoid small bridge stitches

[stephanschulz]

I am not sure if "bridges" is the right term; but it would be awesome to enable an option for which small bridge-stitches are replaced with repeating an already existing path. When doing outline work it can become a lot of work manually cutting all the little bridges between the different continuous runs. I think sometimes it would be fine to run over an already exiting path and as a result have a slightly thicker looking stitch instead of having these jumps.

I know the main focus of this library is not to turn images in to stitchings but rather create generative works, but that's just how my family rolls right now ;)

[LingDong-]

This is an interesting algorithmic problem, basically all the joining points can be viewed as nodes in a graph, and the polylines connecting them are the edges. The problem can be reduced to a depth first search that tries to visit all the edges. Upon visiting a node, it tries to recursively visit one outgoing branch at a time, and when it hits a fully visited node, it comes back in the exact same path as it went out. It then visits the next outgoing edge of the node, and so on. It's a bit like maze solving, except that it doesn't stop when finding a "solution", but instead deplete all the roads.

[LingDong-]

Hi @stephanschulz (cc @golanlevin),

I added a new example that showcases the described algorithm! 66f01a29087608dd5c1efad1e4328b8b30bddabf

examples/PEmbroider_oneliner

Implementation is pretty straightforward:

public class OneLinerGraph{
  public class Node{
    public int x;
    public int y;
    public ArrayList<Edge> edges;
    public boolean visited;
  }
  public class Edge{
    public Node left;
    public Node right;
    public int pid;
    public boolean visited;
  }
  public class EdgeVisit{
    public boolean reversed;
    public Edge edge;
  }
  public ArrayList<Node> nodes;
  public ArrayList<Edge> edges;
  public ArrayList<ArrayList<int[]>> polylines;

  public OneLinerGraph (ArrayList<ArrayList<int[]>> _polylines){
    if (nodes != null){
      nodes.clear();
    }else{
      nodes = new ArrayList<Node>();
    }
    if (edges != null){
      edges.clear();
    }else{
      edges = new ArrayList<Edge>();
    }

    polylines = _polylines;
    for (int i = 0; i < polylines.size(); i++){
      if (polylines.get(i).size() < 2){
        continue;
      }
      int[] head = polylines.get(i).get(0);
      int[] tail = polylines.get(i).get(polylines.get(i).size()-1);

      Node hn = gewNode(head[0],head[1]);
      Node tn = gewNode(tail[0],tail[1]);

      Edge e = new Edge();
      e.left = hn;
      e.right = tn;
      e.pid = i;

      hn.edges.add(e);
      tn.edges.add(e);
      edges.add(e);

    }
  }

  Node gewNode(int x, int y){
    for (int j = 0; j < nodes.size(); j++){
      if (Math.abs(nodes.get(j).x - x)<1 && Math.abs(nodes.get(j).y - y)<1){
        return nodes.get(j);
      }
    }
    Node n = new Node();
    n.x = x;
    n.y = y;
    n.edges = new ArrayList<Edge>();
    n.visited = false;
    nodes.add(n);
    return n;
  }

  ArrayList<EdgeVisit> visitNode(Node node){
    ArrayList<EdgeVisit> path = new ArrayList<EdgeVisit>();
    if (node.visited){
      return path;
    }
    node.visited = true;
    for (int i = 0; i < node.edges.size(); i++){
      Edge e = node.edges.get(i);
      boolean dir = e.right == node;

      Node nxt = e.left == node ? e.right : e.left;
      if (!nxt.visited || !e.visited){
        e.visited = true;
        EdgeVisit ev = new EdgeVisit();
        ev.reversed = dir;
        ev.edge = e;
        path.add(ev);

        path.addAll(visitNode(nxt));

        EdgeVisit rev = new EdgeVisit();
        rev.reversed = !ev.reversed;
        rev.edge = ev.edge;
        path.add(rev);
      }
    }
    return path;
  }

  public ArrayList<int[]> solve(){
    ArrayList<int[]> path = new ArrayList<int[]>();
    Integer start = null;
    for (int i = 0; i < nodes.size(); i++){
      if (!nodes.get(i).visited){
        start = i;
        break;
      }
    }
    if (start == null){
      return null;
    }
    ArrayList<EdgeVisit> visits = visitNode(nodes.get(start));
    for (int i = 0; i < visits.size(); i++){
      EdgeVisit ev = visits.get(i);
      ArrayList<int[]> p = polylines.get(ev.edge.pid);
      if (ev.reversed){
        Collections.reverse(p);
        path.addAll(p);
        Collections.reverse(p);
      }else{
        path.addAll(p);
      }
    }
    return path;
  }

  public ArrayList<ArrayList<int[]>> multiSolve(){
    ArrayList<ArrayList<int[]>> paths = new ArrayList<ArrayList<int[]>>();
    ArrayList<int[]> sol;
    while (true){
      sol = solve();
      if (sol == null){
        break;
      }
      paths.add(sol);
    }
    return paths;
  }
}

[stephanschulz]

looks very interesting. does it try to minimize the doubled up path lengths? looking at it quickly it seems not always pick the shortest route. if I think of this in terms of double stitching over the previous stitch it might be preferable to have as few as possible of those double stitched paths.

please know I think this is super cool and am just voicing some additional thoughts.

[LingDong-]

nope, it finds one path, not necessarily the shortest. Finding the shortest path would be a different story. Easiest way is to feed it some different permutations of the polylines and pick the best result :)

[golanlevin]

Hey @stephanschulz! @LingDong- just showed me your instagram! Could you tag the ones you made with #PEmbroider? We'd love to know!!!!

[stephanschulz]

@LingDong- how would give it "different permutations". I gets the polylines from doing TraceSkeleton.traceSkeleton first. Would changing the chunk size do anything to help getting a range of permutations?

[LingDong-]

Hi @stephanschulz, No chunk size is for the level of detail of the traced skeletons -- I think Collections.shuffle() will be all you need :)

[stephanschulz]

I ran this 10 times, every time with a new color but the resulting poly line arrays are all the same size.

// Trace the skeletons in the pixels.
    ArrayList<ArrayList<int[]>>  c;
    TraceSkeleton.thinningZS(im, W, H);
    c = TraceSkeleton.traceSkeleton(im, W, H, 0, 0, W, H, _minLength, 999, null);

    ArrayList<ArrayList<int[]>> lines;
    OneLinerGraph OLG;

    OLG = new OneLinerGraph(c);
    lines = OLG.multiSolve();

 java.util.Collections.shuffle(lines);
    for (int i = 0; i < lines.size(); i++) {
      E.beginShape();
      for (int j = 0; j < lines.get(i).size(); j++) {
        E.vertex(lines.get(i).get(j)[0], lines.get(i).get(j)[1]);
      }
      E.endShape();
    }

[LingDong-]

// Trace the skeletons in the pixels.
    ArrayList<ArrayList<int[]>>  c;
    TraceSkeleton.thinningZS(im, W, H);
    c = TraceSkeleton.traceSkeleton(im, W, H, 0, 0, W, H, _minLength, 999, null);
 java.util.Collections.shuffle(c);

    ArrayList<ArrayList<int[]>> lines;
    OneLinerGraph OLG;

    OLG = new OneLinerGraph(c);
    lines = OLG.multiSolve();

    for (int i = 0; i < lines.size(); i++) {
      E.beginShape();
      for (int j = 0; j < lines.get(i).size(); j++) {
        E.vertex(lines.get(i).get(j)[0], lines.get(i).get(j)[1]);
      }
      E.endShape();
    }

[stephanschulz]

Thanks for this. But println(i+" lines.get(i).size() "+lines.get(i).size()); still produces the same length array. I am guessing this means it's the same path tracing, which means they are all the same?