Comments (10)
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.
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.
Hey @stephanschulz! @LingDong- just showed me your instagram! Could you tag the ones you made with #PEmbroider? We'd love to know!!!!
from pembroider.
Hi @stephanschulz (cc @golanlevin),
I added a new example that showcases the described algorithm! 66f01a2
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.
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.
@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.
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.
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.
// 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.
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?
from pembroider.
Related Issues (20)
- compile with Eclipse HOT 3
- non-closed shapes with E.strokeMode(E.PERPENDICULAR) have connecting line HOT 2
- under layer support stitch HOT 1
- Request toggle to enable/disable generation of connecting lines HOT 3
- .jef file format causes machine confusion HOT 1
- Jump stitches not being cut, but stitched HOT 9
- no menu preview (but editor preview!) of .pes files on the Brother NV800E
- SVG Export leave connecting lines between shapes HOT 1
- Concentric fill error on imported images
- HatchSpine looks like dot pattern and less like lines HOT 1
- java.io.FileNotFoundException when running PEmbroider_stroke_outlines HOT 4
- Unexpected error when using culling in PEmbroider_bitmap_image_2 HOT 1
- .jef file displays badly on machine HOT 2
- simple E.rect problem HOT 2
- Inaccurate license information HOT 4
- layer names as metadata HOT 1
- culling question. HOT 3
- getting access to PEmbroiderGraphics polylines HOT 2
- satin hatching does not catch all polygons HOT 7
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from pembroider.