Git Product home page Git Product logo

Comments (10)

LingDong- avatar LingDong- commented on September 22, 2024 1

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.

from pembroider.

LingDong- avatar LingDong- commented on September 22, 2024 1

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 :)

from pembroider.

golanlevin avatar golanlevin commented on September 22, 2024 1

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

from pembroider.

LingDong- avatar LingDong- commented on September 22, 2024

pembroider_oneliner

Hi @stephanschulz (cc @golanlevin),

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

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

from pembroider.

stephanschulz avatar stephanschulz commented on September 22, 2024

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.

from pembroider.

stephanschulz avatar stephanschulz commented on September 22, 2024

@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?

from pembroider.

LingDong- avatar LingDong- commented on September 22, 2024

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

from pembroider.

stephanschulz avatar stephanschulz commented on September 22, 2024

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

from pembroider.

LingDong- avatar LingDong- commented on September 22, 2024
// 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();
    }

from pembroider.

stephanschulz avatar stephanschulz commented on September 22, 2024

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?

Screen Shot 2020-09-17 at 9 18 52 PM

from pembroider.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.