From b7cb98d277bcad6a9b418fc11ee716bbc754e69d Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 23 Jun 2018 16:34:35 -0400 Subject: end on the ending point --- lib/stitches/auto_fill.py | 82 +++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 68 insertions(+), 14 deletions(-) (limited to 'lib/stitches/auto_fill.py') diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 518a2812..c558fa1b 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -15,17 +15,17 @@ class MaxQueueLengthExceeded(Exception): pass -def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, running_stitch_length, staggers, starting_point=None): +def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, running_stitch_length, staggers, starting_point, ending_point=None): stitches = [] rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) segments = [segment for row in rows_of_segments for segment in row] graph = build_graph(shape, segments, angle, row_spacing) - path = find_stitch_path(graph, segments) + path = find_stitch_path(graph, segments, starting_point, ending_point) - if starting_point: - stitches.extend(connect_points(shape, starting_point, path[0][0], running_stitch_length)) +# if starting_point: +# stitches.extend(connect_points(shape, starting_point, path[0][0], running_stitch_length)) stitches.extend(path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers)) @@ -272,7 +272,7 @@ def insert_loop(path, loop): start and end point. The points will be specified in order, such that they will look like this: - ((p1, p2), (p2, p3), (p3, p4) ... (pn, p1)) + ((p1, p2), (p2, p3), (p3, p4), ...) path will be modified in place. """ @@ -282,11 +282,55 @@ def insert_loop(path, loop): for i, (start, end) in enumerate(path): if start == loop_start: break + else: + # if we didn't find the start of the loop in the list at all, it must + # be the endpoint of the last segment + i += 1 path[i:i] = loop +def nearest_node_on_outline(graph, point, outline_index=0): + point = shapely.geometry.Point(*point) + outline_nodes = [node for node, data in graph.nodes(data=True) if data['index'] == outline_index] + nearest = min(outline_nodes, key=lambda node: shapely.geometry.Point(*node).distance(point)) + + return nearest + +def get_outline_nodes(graph, outline_index=0): + outline_nodes = [(node, data['projection']) \ + for node, data \ + in graph.nodes(data=True) \ + if data['index'] == outline_index] + outline_nodes.sort(key=lambda (node, projection): projection) + outline_nodes = [node for node, data in outline_nodes] + + return outline_nodes + +def find_initial_path(graph, starting_point, ending_point=None): + starting_node = nearest_node_on_outline(graph, starting_point) + + if ending_point is None: + # If they didn't give an ending point, pick either neighboring node + # along the outline -- doesn't matter which. This effectively means + # we end where we started. + neighbors = [n for n, keys in graph.adj[starting_node].iteritems() if 'outline' in keys] + return [(starting_node, neighbors[0])] + else: + ending_node = nearest_node_on_outline(graph, ending_point) + outline_nodes = get_outline_nodes(graph) + + # Multiply the outline_nodes list by 2 (duplicate it) because + # the ending_node may occur first. + outline_nodes *= 2 + start_index = outline_nodes.index(starting_node) + end_index = outline_nodes.index(ending_node, start_index) + path = outline_nodes[start_index:end_index + 1] + + # we have a series of sequential points, but we need to + # turn it into an edge list + return node_list_to_edge_list(path) -def find_stitch_path(graph, segments): +def find_stitch_path(graph, segments, starting_point=None, ending_point=None): """find a path that visits every grating segment exactly once Theoretically, we just need to find an Eulerian Path in the graph. @@ -313,14 +357,20 @@ def find_stitch_path(graph, segments): segments_visited = 0 nodes_visited = deque() - # start with a simple loop: down one segment and then back along the - # outer border to the starting point. - path = [segments[0], list(reversed(segments[0]))] + if starting_point is None: + starting_point = segments[0][0] + path = find_initial_path(graph, starting_point, ending_point) - graph.remove_edges_from(path) + # We're starting with a path and _not_ removing the edges of that path from + # the graph. This means we're implicitly adding those edges to the graph. + # That means that the starting and ending point (and only those two) will + # now have odd degree. That means that there must exist an Eulerian + # Path that starts and ends at those two nodes. - segments_visited += 1 - nodes_visited.extend(segments[0]) + nodes_visited.append(path[0][0]) + #print >> sys.stderr, "starting path:", path + + #return path while segments_visited < num_segments: result = find_loop(graph, nodes_visited) @@ -331,15 +381,19 @@ def find_stitch_path(graph, segments): loop, segments = result - #print >> dbg, "found loop:", loop + #print >> sys.stderr, "found loop:", loop #dbg.flush() segments_visited += segments - nodes_visited += [edge[0] for edge in loop] + nodes_visited.extend(edge[0] for edge in loop) graph.remove_edges_from(loop) insert_loop(path, loop) + #print >> sys.stderr, "loop made, nodes_visited:", nodes_visited + + #print >> sys.stderr, "path:", path + #if segments_visited >= 12: # break -- cgit v1.2.3 From e0a2b31ede8b412c83747fef168c3dda0d07087f Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 23 Jun 2018 21:41:00 -0400 Subject: fix collapse_sequential_outline_edges --- lib/stitches/auto_fill.py | 77 ++++++++++++++++++++++++++++++++--------------- 1 file changed, 52 insertions(+), 25 deletions(-) (limited to 'lib/stitches/auto_fill.py') diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index c558fa1b..42fd1ef5 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -2,7 +2,7 @@ import sys import shapely import networkx import math -from itertools import groupby +from itertools import groupby, izip from collections import deque from .fill import intersect_region_with_grating, row_num, stitch_row @@ -14,6 +14,29 @@ from ..utils.geometry import Point as InkstitchPoint class MaxQueueLengthExceeded(Exception): pass +class PathEdge(object): + OUTLINE_KEYS = ("outline", "extra", "initial") + SEGMENT_KEY = "segment" + + def __init__(self, nodes, key): + self.nodes = nodes + self._sorted_nodes = tuple(sorted(self.nodes)) + self.key = key + + def __getitem__(self, item): + return self.nodes[item] + + def __hash__(self): + return hash((self._sorted_nodes, self.key)) + + def __eq__(self, other): + return self._sorted_nodes == other._sorted_nodes and self.key == other.key + + def is_outline(self): + return self.key in self.OUTLINE_KEYS + + def is_segment(self): + return self.key == self.SEGMENT_KEY def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, running_stitch_length, staggers, starting_point, ending_point=None): stitches = [] @@ -157,14 +180,20 @@ def node_list_to_edge_list(node_list): def bfs_for_loop(graph, starting_node, max_queue_length=2000): to_search = deque() - to_search.appendleft(([starting_node], set(), 0)) + to_search.append((None, set())) while to_search: if len(to_search) > max_queue_length: raise MaxQueueLengthExceeded() - path, visited_edges, visited_segments = to_search.pop() - ending_node = path[-1] + path, visited_edges = to_search.pop() + + if path is None: + # This is the very first time through the loop, so initialize. + path = [] + ending_node = starting_node + else: + ending_node = path[-1][-1] # get a list of neighbors paired with the key of the edge I can follow to get there neighbors = [ @@ -178,26 +207,21 @@ def bfs_for_loop(graph, starting_node, max_queue_length=2000): for next_node, key in neighbors: # skip if I've already followed this edge - edge = (tuple(sorted((ending_node, next_node))), key) + edge = PathEdge((ending_node, next_node), key) if edge in visited_edges: continue - new_path = path + [next_node] - - if key == "segment": - new_visited_segments = visited_segments + 1 - else: - new_visited_segments = visited_segments + new_path = path + [edge] if next_node == starting_node: # ignore trivial loops (down and back a doubled edge) if len(new_path) > 3: - return node_list_to_edge_list(new_path), new_visited_segments + return new_path new_visited_edges = visited_edges.copy() new_visited_edges.add(edge) - to_search.appendleft((new_path, new_visited_edges, new_visited_segments)) + to_search.appendleft((new_path, new_visited_edges)) def find_loop(graph, starting_nodes): @@ -314,7 +338,7 @@ def find_initial_path(graph, starting_point, ending_point=None): # along the outline -- doesn't matter which. This effectively means # we end where we started. neighbors = [n for n, keys in graph.adj[starting_node].iteritems() if 'outline' in keys] - return [(starting_node, neighbors[0])] + return [PathEdge((starting_node, neighbors[0]), "initial")] else: ending_node = nearest_node_on_outline(graph, ending_point) outline_nodes = get_outline_nodes(graph) @@ -324,11 +348,15 @@ def find_initial_path(graph, starting_point, ending_point=None): outline_nodes *= 2 start_index = outline_nodes.index(starting_node) end_index = outline_nodes.index(ending_node, start_index) - path = outline_nodes[start_index:end_index + 1] + nodes = outline_nodes[start_index:end_index + 1] # we have a series of sequential points, but we need to # turn it into an edge list - return node_list_to_edge_list(path) + path = [] + for start, end in izip(nodes[:-1], nodes[1:]): + path.append(PathEdge((start, end), "initial")) + + return path def find_stitch_path(graph, segments, starting_point=None, ending_point=None): """find a path that visits every grating segment exactly once @@ -368,23 +396,22 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None): # Path that starts and ends at those two nodes. nodes_visited.append(path[0][0]) + #print >> sys.stderr, "nodes_visited", nodes_visited #print >> sys.stderr, "starting path:", path #return path while segments_visited < num_segments: - result = find_loop(graph, nodes_visited) + loop = find_loop(graph, nodes_visited) - if not result: + if not loop: print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.") break - loop, segments = result - #print >> sys.stderr, "found loop:", loop #dbg.flush() - segments_visited += segments + segments_visited += sum(1 for edge in loop if edge.is_segment()) nodes_visited.extend(edge[0] for edge in loop) graph.remove_edges_from(loop) @@ -417,10 +444,10 @@ def collapse_sequential_outline_edges(graph, path): new_path = [] for edge in path: - if graph.has_edge(*edge, key="segment"): + if edge.is_segment(): if start_of_run: # close off the last run - new_path.append((start_of_run, edge[0])) + new_path.append(PathEdge((start_of_run, edge[0]), "collapsed")) start_of_run = None new_path.append(edge) @@ -430,7 +457,7 @@ def collapse_sequential_outline_edges(graph, path): if start_of_run: # if we were still in a run, close it off - new_path.append((start_of_run, edge[1])) + new_path.append(PathEdge((start_of_run, edge[1]), "collapsed")) return new_path @@ -496,7 +523,7 @@ def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, stitches = [] for edge in path: - if graph.has_edge(*edge, key="segment"): + if edge.is_segment(): stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers) else: stitches.extend(connect_points(shape, edge[0], edge[1], running_stitch_length)) -- cgit v1.2.3 From 78efaf120f08883e00428d54c2035e63934566ba Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 23 Jun 2018 22:53:17 -0400 Subject: remove unnecessary travel back to start --- lib/stitches/auto_fill.py | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'lib/stitches/auto_fill.py') diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 42fd1ef5..c7c3cdec 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -47,8 +47,10 @@ def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, run graph = build_graph(shape, segments, angle, row_spacing) path = find_stitch_path(graph, segments, starting_point, ending_point) -# if starting_point: -# stitches.extend(connect_points(shape, starting_point, path[0][0], running_stitch_length)) + if ending_point is None: + # The end of the path travels around the outline back to the start. + # This isn't necessary, so remove it. + trim_end(path) stitches.extend(path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers)) @@ -516,6 +518,9 @@ def connect_points(shape, start, end, running_stitch_length): return stitches +def trim_end(path): + while path and path[-1].is_outline(): + path.pop() def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers): path = collapse_sequential_outline_edges(graph, path) -- cgit v1.2.3 From 3950be13160dca1117cdebac0ab41332ac744e40 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 23 Jun 2018 23:10:01 -0400 Subject: tidy comments --- lib/stitches/auto_fill.py | 79 ++++++++++++++--------------------------------- 1 file changed, 23 insertions(+), 56 deletions(-) (limited to 'lib/stitches/auto_fill.py') diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index c7c3cdec..6326ced2 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -47,11 +47,6 @@ def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, run graph = build_graph(shape, segments, angle, row_spacing) path = find_stitch_path(graph, segments, starting_point, ending_point) - if ending_point is None: - # The end of the path travels around the outline back to the start. - # This isn't necessary, so remove it. - trim_end(path) - stitches.extend(path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers)) return stitches @@ -159,8 +154,6 @@ def build_graph(shape, segments, angle, row_spacing): else: edge_set = 1 - #print >> sys.stderr, outline_index, "es", edge_set, "rn", row_num, inkstitch.Point(*nodes[0]) * self.north(angle), inkstitch.Point(*nodes[1]) * self.north(angle) - # add an edge between each successive node for i, (node1, node2) in enumerate(zip(nodes, nodes[1:] + [nodes[0]])): graph.add_edge(node1, node2, key="outline") @@ -242,14 +235,6 @@ def find_loop(graph, starting_nodes): somewhere else. """ - #loop = self.simple_loop(graph, starting_nodes[-2]) - - #if loop: - # print >> sys.stderr, "simple_loop success" - # starting_nodes.pop() - # starting_nodes.pop() - # return loop - loop = None retry = [] max_queue_length = 2000 @@ -257,7 +242,6 @@ def find_loop(graph, starting_nodes): while not loop: while not loop and starting_nodes: starting_node = starting_nodes.pop() - #print >> sys.stderr, "find loop from", starting_node try: # Note: if bfs_for_loop() returns None, no loop can be @@ -266,12 +250,7 @@ def find_loop(graph, starting_nodes): # case we discard that node and try the next. loop = bfs_for_loop(graph, starting_node, max_queue_length) - #if not loop: - #print >> dbg, "failed on", starting_node - #dbg.flush() except MaxQueueLengthExceeded: - #print >> dbg, "gave up on", starting_node - #dbg.flush() # We're giving up on this node for now. We could try # this node again later, so add it to the bottm of the # stack. @@ -337,8 +316,8 @@ def find_initial_path(graph, starting_point, ending_point=None): if ending_point is None: # If they didn't give an ending point, pick either neighboring node - # along the outline -- doesn't matter which. This effectively means - # we end where we started. + # along the outline -- doesn't matter which. We do this because + # the algorithm requires we start with _some_ path. neighbors = [n for n, keys in graph.adj[starting_node].iteritems() if 'outline' in keys] return [PathEdge((starting_node, neighbors[0]), "initial")] else: @@ -368,13 +347,14 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None): The edges on the outline of the region are only there to help us get from one grating segment to the next. - We'll build a "cycle" (a path that ends where it starts) using - Hierholzer's algorithm. We'll stop once we've visited every grating - segment. + We'll build a Eulerian Path using Hierholzer's algorithm. A true + Eulerian Path would visit every single edge (including all the extras + we inserted in build_graph()),but we'll stop short once we've visited + every grating segment since that's all we really care about. Hierholzer's algorithm says to select an arbitrary starting node at each step. In order to produce a reasonable stitch path, we'll select - the vertex carefully such that we get back-and-forth traversal like + the starting node carefully such that we get back-and-forth traversal like mowing a lawn. To do this, we'll use a simple heuristic: try to start from nodes in @@ -389,19 +369,21 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None): if starting_point is None: starting_point = segments[0][0] + path = find_initial_path(graph, starting_point, ending_point) - # We're starting with a path and _not_ removing the edges of that path from - # the graph. This means we're implicitly adding those edges to the graph. - # That means that the starting and ending point (and only those two) will - # now have odd degree. That means that there must exist an Eulerian - # Path that starts and ends at those two nodes. + # Our graph is Eulerian: every node has an even degree. An Eulerian graph + # must have an Eulerian Circuit which visits every edge and ends where it + # starts. + # + # However, we're starting with a path and _not_ removing the edges of that + # path from the graph. By doing this, we're implicitly adding those edges + # to the graph, after which the starting and ending point (and only those + # two) will now have odd degree. A graph that's Eulerian except for two + # nodes must have an Eulerian Path that starts and ends at those two nodes. + # That's how we force the starting and ending point. nodes_visited.append(path[0][0]) - #print >> sys.stderr, "nodes_visited", nodes_visited - #print >> sys.stderr, "starting path:", path - - #return path while segments_visited < num_segments: loop = find_loop(graph, nodes_visited) @@ -410,26 +392,17 @@ def find_stitch_path(graph, segments, starting_point=None, ending_point=None): print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.") break - #print >> sys.stderr, "found loop:", loop - #dbg.flush() - segments_visited += sum(1 for edge in loop if edge.is_segment()) nodes_visited.extend(edge[0] for edge in loop) graph.remove_edges_from(loop) insert_loop(path, loop) - #print >> sys.stderr, "loop made, nodes_visited:", nodes_visited - - #print >> sys.stderr, "path:", path - - #if segments_visited >= 12: - # break - - # Now we have a loop that covers every grating segment. It returns to - # where it started, which is unnecessary, so we'll snip the last bit off. - #while original_graph.has_edge(*path[-1], key="outline"): - # path.pop() + if ending_point is None: + # If they didn't specify an ending point, then the end of the path travels + # around the outline back to the start (see find_initial_path()). This + # isn't necessary, so remove it. + trim_end(path) return path @@ -499,9 +472,6 @@ def connect_points(shape, start, end, running_stitch_length): direction = math.copysign(1.0, distance) one_stitch = running_stitch_length * direction - #print >> dbg, "connect_points:", outline_index, start, end, distance, stitches, direction - #dbg.flush() - stitches = [InkstitchPoint(*outline.interpolate(pos).coords[0])] for i in xrange(num_stitches): @@ -513,9 +483,6 @@ def connect_points(shape, start, end, running_stitch_length): if (end - stitches[-1]).length() > 0.1 * PIXELS_PER_MM: stitches.append(end) - #print >> dbg, "end connect_points" - #dbg.flush() - return stitches def trim_end(path): -- cgit v1.2.3