diff options
| -rw-r--r-- | embroider.py | 740 | ||||
| -rw-r--r-- | inkstitch/stitches/__init__.py | 2 | ||||
| -rw-r--r-- | inkstitch/stitches/auto_fill.py | 447 | ||||
| -rw-r--r-- | inkstitch/stitches/fill.py | 244 | ||||
| -rw-r--r-- | messages.po | 11 |
5 files changed, 741 insertions, 703 deletions
diff --git a/embroider.py b/embroider.py index eeab5854..804782a9 100644 --- a/embroider.py +++ b/embroider.py @@ -36,7 +36,7 @@ from pprint import pformat import inkstitch from inkstitch import _, cache, dbg, param, EmbroideryElement, get_nodes, SVG_POLYLINE_TAG, SVG_GROUP_TAG, PIXELS_PER_MM, get_viewbox_transform -from inkstitch.stitches import running_stitch +from inkstitch.stitches import running_stitch, auto_fill, legacy_fill from inkstitch.utils import cut_path class Fill(EmbroideryElement): @@ -120,257 +120,21 @@ class Fill(EmbroideryElement): # print >> sys.stderr, "polygon valid:", polygon.is_valid return polygon - @cache - def east(self, angle): - # "east" is the name of the direction that is to the right along a row - return inkstitch.Point(1, 0).rotate(-angle) - - @cache - def north(self, angle): - return self.east(angle).rotate(math.pi / 2) - - def row_num(self, point, angle, row_spacing): - return round((point * self.north(angle)) / row_spacing) - - def adjust_stagger(self, stitch, angle, row_spacing, max_stitch_length): - row_num = self.row_num(stitch, angle, row_spacing) - row_stagger = row_num % self.staggers - stagger_offset = (float(row_stagger) / self.staggers) * max_stitch_length - offset = ((stitch * self.east(angle)) - stagger_offset) % max_stitch_length - - return stitch - offset * self.east(angle) - - def intersect_region_with_grating(self, angle=None, row_spacing=None, end_row_spacing=None): - if angle is None: - angle = self.angle - - if row_spacing is None: - row_spacing = self.row_spacing - - if end_row_spacing is None: - end_row_spacing = self.end_row_spacing - - # the max line length I'll need to intersect the whole shape is the diagonal - (minx, miny, maxx, maxy) = self.shape.bounds - upper_left = inkstitch.Point(minx, miny) - lower_right = inkstitch.Point(maxx, maxy) - length = (upper_left - lower_right).length() - half_length = length / 2.0 - - # Now get a unit vector rotated to the requested angle. I use -angle - # because shapely rotates clockwise, but my geometry textbooks taught - # me to consider angles as counter-clockwise from the X axis. - direction = inkstitch.Point(1, 0).rotate(-angle) - - # and get a normal vector - normal = direction.rotate(math.pi / 2) - - # I'll start from the center, move in the normal direction some amount, - # and then walk left and right half_length in each direction to create - # a line segment in the grating. - center = inkstitch.Point((minx + maxx) / 2.0, (miny + maxy) / 2.0) - - # I need to figure out how far I need to go along the normal to get to - # the edge of the shape. To do that, I'll rotate the bounding box - # angle degrees clockwise and ask for the new bounding box. The max - # and min y tell me how far to go. - - _, start, _, end = affinity.rotate(self.shape, angle, origin='center', use_radians=True).bounds - - # convert start and end to be relative to center (simplifies things later) - start -= center.y - end -= center.y - - height = abs(end - start) - - print >> dbg, "grating:", start, end, height, row_spacing, end_row_spacing - - # offset start slightly so that rows are always an even multiple of - # row_spacing_px from the origin. This makes it so that abutting - # fill regions at the same angle and spacing always line up nicely. - start -= (start + normal * center) % row_spacing - - rows = [] - - current_row_y = start - - while current_row_y < end: - p0 = center + normal * current_row_y + direction * half_length - p1 = center + normal * current_row_y - direction * half_length - endpoints = [p0.as_tuple(), p1.as_tuple()] - grating_line = shgeo.LineString(endpoints) - - res = grating_line.intersection(self.shape) - - if (isinstance(res, shgeo.MultiLineString)): - runs = map(lambda line_string: line_string.coords, res.geoms) - else: - if res.is_empty or len(res.coords) == 1: - # ignore if we intersected at a single point or no points - runs = [] - else: - runs = [res.coords] - - if runs: - runs.sort(key=lambda seg: (inkstitch.Point(*seg[0]) - upper_left).length()) - - if self.flip: - runs.reverse() - runs = map(lambda run: tuple(reversed(run)), runs) - - rows.append(runs) - - if end_row_spacing: - current_row_y += row_spacing + (end_row_spacing - row_spacing) * ((current_row_y - start) / height) - else: - current_row_y += row_spacing - - return rows - - def make_quadrilateral(self, segment1, segment2): - return shgeo.Polygon((segment1[0], segment1[1], segment2[1], segment2[0], segment1[0])) - - def is_same_run(self, segment1, segment2): - if shgeo.LineString(segment1).distance(shgeo.LineString(segment2)) > self.row_spacing * 1.1: - return False - - quad = self.make_quadrilateral(segment1, segment2) - quad_area = quad.area - intersection_area = self.shape.intersection(quad).area - - return (intersection_area / quad_area) >= 0.9 - - def pull_runs(self, rows): - # Given a list of rows, each containing a set of line segments, - # break the area up into contiguous patches of line segments. - # - # This is done by repeatedly pulling off the first line segment in - # each row and calling that a shape. We have to be careful to make - # sure that the line segments are part of the same shape. Consider - # the letter "H", with an embroidery angle of 45 degrees. When - # we get to the bottom of the lower left leg, the next row will jump - # over to midway up the lower right leg. We want to stop there and - # start a new patch. - - # for row in rows: - # print >> sys.stderr, len(row) - - # print >>sys.stderr, "\n".join(str(len(row)) for row in rows) - - runs = [] - count = 0 - while (len(rows) > 0): - run = [] - prev = None - - for row_num in xrange(len(rows)): - row = rows[row_num] - first, rest = row[0], row[1:] - - # TODO: only accept actually adjacent rows here - if prev is not None and not self.is_same_run(prev, first): - break - - run.append(first) - prev = first - - rows[row_num] = rest - - # print >> sys.stderr, len(run) - runs.append(run) - rows = [row for row in rows if len(row) > 0] - - count += 1 - - return runs - - def stitch_row(self, patch, beg, end, angle, row_spacing, max_stitch_length): - # We want our stitches to look like this: - # - # ---*-----------*----------- - # ------*-----------*-------- - # ---------*-----------*----- - # ------------*-----------*-- - # ---*-----------*----------- - # - # Each successive row of stitches will be staggered, with - # num_staggers rows before the pattern repeats. A value of - # 4 gives a nice fill while hiding the needle holes. The - # first row is offset 0%, the second 25%, the third 50%, and - # the fourth 75%. - # - # Actually, instead of just starting at an offset of 0, we - # can calculate a row's offset relative to the origin. This - # way if we have two abutting fill regions, they'll perfectly - # tile with each other. That's important because we often get - # abutting fill regions from pull_runs(). - - - beg = inkstitch.Point(*beg) - end = inkstitch.Point(*end) - - row_direction = (end - beg).unit() - segment_length = (end - beg).length() - - # only stitch the first point if it's a reasonable distance away from the - # last stitch - if not patch.stitches or (beg - patch.stitches[-1]).length() > 0.5 * PIXELS_PER_MM: - patch.add_stitch(beg) - - first_stitch = self.adjust_stagger(beg, angle, row_spacing, max_stitch_length) - - # we might have chosen our first stitch just outside this row, so move back in - if (first_stitch - beg) * row_direction < 0: - first_stitch += row_direction * max_stitch_length - - offset = (first_stitch - beg).length() - - while offset < segment_length: - patch.add_stitch(beg + offset * row_direction) - offset += max_stitch_length - - if (end - patch.stitches[-1]).length() > 0.1 * PIXELS_PER_MM: - patch.add_stitch(end) - - - def section_to_patch(self, group_of_segments, angle=None, row_spacing=None, max_stitch_length=None): - if max_stitch_length is None: - max_stitch_length = self.max_stitch_length - - if row_spacing is None: - row_spacing = self.row_spacing - - if angle is None: - angle = self.angle - - # print >> sys.stderr, len(groups_of_segments) - - patch = Patch(color=self.color) - first_segment = True - swap = False - last_end = None - - for segment in group_of_segments: - (beg, end) = segment - - if (swap): - (beg, end) = (end, beg) - - self.stitch_row(patch, beg, end, angle, row_spacing, max_stitch_length) - - swap = not swap - - return patch - def to_patches(self, last_patch): - rows_of_segments = self.intersect_region_with_grating() - groups_of_segments = self.pull_runs(rows_of_segments) + stitch_lists = legacy_fill(self.shape, + self.angle, + self.row_spacing, + self.end_row_spacing, + self.max_stitch_length, + self.flip, + self.staggers) + return [Patch(stitches=stitch_list, color=self.color) for stitch_list in stitch_lists] - return [self.section_to_patch(group) for group in groups_of_segments] + rows_of_segments = fill.intersect_region_with_grating(self.shape, self.angle, self.row_spacing, self.end_row_spacing, self.flip) + groups_of_segments = fill.pull_runs(rows_of_segments) + return [fill.section_to_patch(group) for group in groups_of_segments] -class MaxQueueLengthExceeded(Exception): - pass class AutoFill(Fill): element_name = _("Auto-Fill") @@ -427,462 +191,50 @@ class AutoFill(Fill): def fill_underlay_max_stitch_length(self): return self.get_float_param("fill_underlay_max_stitch_length_mm") or self.max_stitch_length - def which_outline(self, coords): - """return the index of the outline on which the point resides - - Index 0 is the outer boundary of the fill region. 1+ are the - outlines of the holes. - """ - - # I'd use an intersection check, but floating point errors make it - # fail sometimes. - - point = shgeo.Point(*coords) - outlines = list(enumerate(self.shape.boundary)) - closest = min(outlines, key=lambda (index, outline): outline.distance(point)) - - return closest[0] - - def project(self, coords, outline_index): - """project the point onto the specified outline - - This returns the distance along the outline at which the point resides. - """ - - return self.shape.boundary.project(shgeo.Point(*coords)) - - def build_graph(self, segments, angle, row_spacing): - """build a graph representation of the grating segments - - This function builds a specialized graph (as in graph theory) that will - help us determine a stitching path. The idea comes from this paper: - - http://www.sciencedirect.com/science/article/pii/S0925772100000158 - - The goal is to build a graph that we know must have an Eulerian Path. - An Eulerian Path is a path from edge to edge in the graph that visits - every edge exactly once and ends at the node it started at. Algorithms - exist to build such a path, and we'll use Hierholzer's algorithm. - - A graph must have an Eulerian Path if every node in the graph has an - even number of edges touching it. Our goal here is to build a graph - that will have this property. - - Based on the paper linked above, we'll build the graph as follows: - - * nodes are the endpoints of the grating segments, where they meet - with the outer outline of the region the outlines of the interior - holes in the region. - * edges are: - * each section of the outer and inner outlines of the region, - between nodes - * double every other edge in the outer and inner hole outlines - - Doubling up on some of the edges seems as if it will just mean we have - to stitch those spots twice. This may be true, but it also ensures - that every node has 4 edges touching it, ensuring that a valid stitch - path must exist. - """ - - graph = networkx.MultiGraph() - - # First, add the grating segments as edges. We'll use the coordinates - # of the endpoints as nodes, which networkx will add automatically. - for segment in segments: - # networkx allows us to label nodes with arbitrary data. We'll - # mark this one as a grating segment. - graph.add_edge(*segment, key="segment") - - for node in graph.nodes(): - outline_index = self.which_outline(node) - outline_projection = self.project(node, outline_index) - - # Tag each node with its index and projection. - graph.add_node(node, index=outline_index, projection=outline_projection) - - nodes = list(graph.nodes(data=True)) # returns a list of tuples: [(node, {data}), (node, {data}) ...] - nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection'])) - - for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']): - nodes = [ node for node, data in nodes ] - - # heuristic: change the order I visit the nodes in the outline if necessary. - # If the start and endpoints are in the same row, I can't tell which row - # I should treat it as being in. - for i in xrange(len(nodes)): - row0 = self.row_num(inkstitch.Point(*nodes[0]), angle, row_spacing) - row1 = self.row_num(inkstitch.Point(*nodes[1]), angle, row_spacing) - - if row0 == row1: - nodes = nodes[1:] + [nodes[0]] - else: - break - - # heuristic: it's useful to try to keep the duplicated edges in the same rows. - # this prevents the BFS from having to search a ton of edges. - row_num = min(row0, row1) - if row_num % 2 == 0: - edge_set = 0 - 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") - - # duplicate edges contained in every other row (exactly half - # will be duplicated) - row_num = min(self.row_num(inkstitch.Point(*node1), angle, row_spacing), - self.row_num(inkstitch.Point(*node2), angle, row_spacing)) - - # duplicate every other edge around this outline - if i % 2 == edge_set: - graph.add_edge(node1, node2, key="extra") - - - if not networkx.is_eulerian(graph): - raise Exception(_("Unable to autofill. This most often happens because your shape is made up of multiple sections that aren't connected.")) - - return graph - - def node_list_to_edge_list(self, node_list): - return zip(node_list[:-1], node_list[1:]) - - def bfs_for_loop(self, graph, starting_node, max_queue_length=2000): - to_search = deque() - to_search.appendleft(([starting_node], set(), 0)) - - while to_search: - if len(to_search) > max_queue_length: - raise MaxQueueLengthExceeded() - - path, visited_edges, visited_segments = to_search.pop() - ending_node = path[-1] - - # get a list of neighbors paired with the key of the edge I can follow to get there - neighbors = [ - (node, key) - for node, adj in graph.adj[ending_node].iteritems() - for key in adj - ] - - # heuristic: try grating segments first - neighbors.sort(key=lambda (dest, key): key == "segment", reverse=True) - - for next_node, key in neighbors: - # skip if I've already followed this edge - edge = (tuple(sorted((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 - - if next_node == starting_node: - # ignore trivial loops (down and back a doubled edge) - if len(new_path) > 3: - return self.node_list_to_edge_list(new_path), new_visited_segments - - new_visited_edges = visited_edges.copy() - new_visited_edges.add(edge) - - to_search.appendleft((new_path, new_visited_edges, new_visited_segments)) - - def find_loop(self, graph, starting_nodes): - """find a loop in the graph that is connected to the existing path - - Start at a candidate node and search through edges to find a path - back to that node. We'll use a breadth-first search (BFS) in order to - find the shortest available loop. - - In most cases, the BFS should not need to search far to find a loop. - The queue should stay relatively short. - - An added heuristic will be used: if the BFS queue's length becomes - too long, we'll abort and try a different starting point. Due to - the way we've set up the graph, there's bound to be a better choice - 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 - - 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 - # constructed from the starting_node (because the - # necessary edges have already been consumed). In that - # case we discard that node and try the next. - loop = self.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. - retry.append(starting_node) - - # Darn, couldn't find a loop. Try harder. - starting_nodes.extendleft(retry) - max_queue_length *= 2 - - starting_nodes.extendleft(retry) - return loop - - def insert_loop(self, path, loop): - """insert a sub-loop into an existing path - - The path will be a series of edges describing a path through the graph - that ends where it starts. The loop will be similar, and its starting - point will be somewhere along the path. - - Insert the loop into the path, resulting in a longer path. - - Both the path and the loop will be a list of edges specified as a - 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)) - - path will be modified in place. - """ - - loop_start = loop[0][0] - - for i, (start, end) in enumerate(path): - if start == loop_start: - break - - path[i:i] = loop - - def find_stitch_path(self, graph, segments): - """find a path that visits every grating segment exactly once - - Theoretically, we just need to find an Eulerian Path in the graph. - However, we don't actually care whether every single edge is visited. - 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. - - 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 - mowing a lawn. - - To do this, we'll use a simple heuristic: try to start from nodes in - the order of most-recently-visited first. - """ - - original_graph = graph - graph = graph.copy() - num_segments = len(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]))] - - graph.remove_edges_from(path) - - segments_visited += 1 - nodes_visited.extend(segments[0]) - - while segments_visited < num_segments: - result = self.find_loop(graph, nodes_visited) - - if not result: - print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.") - break - - loop, segments = result - - print >> dbg, "found loop:", loop - dbg.flush() - - segments_visited += segments - nodes_visited += [edge[0] for edge in loop] - graph.remove_edges_from(loop) - - self.insert_loop(path, loop) - - #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() - - return path - - def collapse_sequential_outline_edges(self, graph, path): - """collapse sequential edges that fall on the same outline - - When the path follows multiple edges along the outline of the region, - replace those edges with the starting and ending points. We'll use - these to stitch along the outline later on. - """ - - start_of_run = None - new_path = [] - - for edge in path: - if graph.has_edge(*edge, key="segment"): - if start_of_run: - # close off the last run - new_path.append((start_of_run, edge[0])) - start_of_run = None - - new_path.append(edge) - else: - if not start_of_run: - start_of_run = edge[0] - - if start_of_run: - # if we were still in a run, close it off - new_path.append((start_of_run, edge[1])) - - return new_path - - def outline_distance(self, outline, p1, p2): - # how far around the outline (and in what direction) do I need to go - # to get from p1 to p2? - - p1_projection = outline.project(shgeo.Point(p1)) - p2_projection = outline.project(shgeo.Point(p2)) - - distance = p2_projection - p1_projection + @property + @param('fill_underlay_inset_mm', _('Inset'), unit='mm', group=_('AutoFill Underlay'), type='float', default=0) + def fill_underlay_inset(self): + return self.get_float_param('fill_underlay_inset_mm', 0) - if abs(distance) > self.outline_length / 2.0: - # if we'd have to go more than halfway around, it's faster to go - # the other way - if distance < 0: - return distance + self.outline_length - elif distance > 0: - return distance - self.outline_length - else: - # this ought not happen, but just for completeness, return 0 if - # p1 and p0 are the same point - return 0 + @property + def underlay_shape(self): + if self.fill_underlay_inset: + shape = self.shape.buffer(-self.fill_underlay_inset) + if not isinstance(shape, shgeo.MultiPolygon): + shape = shgeo.MultiPolygon([shape]) + return shape else: - return distance - - def connect_points(self, patch, start, end): - outline_index = self.which_outline(start) - outline = self.shape.boundary[outline_index] - - pos = outline.project(shgeo.Point(start)) - distance = self.outline_distance(outline, start, end) - stitches = abs(int(distance / self.running_stitch_length)) - - direction = math.copysign(1.0, distance) - one_stitch = self.running_stitch_length * direction - - print >> dbg, "connect_points:", outline_index, start, end, distance, stitches, direction - dbg.flush() - - patch.add_stitch(inkstitch.Point(*start)) - - for i in xrange(stitches): - pos = (pos + one_stitch) % self.outline_length - - patch.add_stitch(inkstitch.Point(*outline.interpolate(pos).coords[0])) - - end = inkstitch.Point(*end) - if (end - patch.stitches[-1]).length() > 0.1 * PIXELS_PER_MM: - patch.add_stitch(end) - - print >> dbg, "end connect_points" - dbg.flush() - - def path_to_patch(self, graph, path, angle, row_spacing, max_stitch_length): - path = self.collapse_sequential_outline_edges(graph, path) - - patch = Patch(color=self.color) - #patch.add_stitch(inkstitch.Point(*path[0][0])) - - #for edge in path: - # patch.add_stitch(inkstitch.Point(*edge[1])) - - for edge in path: - if graph.has_edge(*edge, key="segment"): - self.stitch_row(patch, edge[0], edge[1], angle, row_spacing, max_stitch_length) - else: - self.connect_points(patch, *edge) - - return patch - - def do_auto_fill(self, angle, row_spacing, max_stitch_length, starting_point=None): - patches = [] - - print >> dbg, "start do_auto_fill" - dbg.flush() - - rows_of_segments = self.intersect_region_with_grating(angle, row_spacing) - segments = [segment for row in rows_of_segments for segment in row] - - graph = self.build_graph(segments, angle, row_spacing) - path = self.find_stitch_path(graph, segments) - - if starting_point: - patch = Patch(self.color) - self.connect_points(patch, starting_point, path[0][0]) - patches.append(patch) - - patches.append(self.path_to_patch(graph, path, angle, row_spacing, max_stitch_length)) - - print >> dbg, "end do_auto_fill" - dbg.flush() - - return patches - + return self.shape def to_patches(self, last_patch): - patches = [] + stitches = [] if last_patch is None: starting_point = None else: - nearest_point = self.outline.interpolate(self.outline.project(shgeo.Point(last_patch.stitches[-1]))) - starting_point = inkstitch.Point(*nearest_point.coords[0]) + starting_point = last_patch.stitches[-1] if self.fill_underlay: - patches.extend(self.do_auto_fill(self.fill_underlay_angle, self.fill_underlay_row_spacing, self.fill_underlay_max_stitch_length, starting_point)) - starting_point = patches[-1].stitches[-1] - - patches.extend(self.do_auto_fill(self.angle, self.row_spacing, self.max_stitch_length, starting_point)) - - print >> dbg, "end AutoFill.to_patches" - dbg.flush() - - return patches + stitches.extend(auto_fill(self.underlay_shape, + self.fill_underlay_angle, + self.fill_underlay_row_spacing, + self.fill_underlay_row_spacing, + self.fill_underlay_max_stitch_length, + self.running_stitch_length, + self.staggers, + starting_point)) + starting_point = stitches[-1] + + stitches.extend(auto_fill(self.shape, + self.angle, + self.row_spacing, + self.end_row_spacing, + self.max_stitch_length, + self.running_stitch_length, + self.staggers, + starting_point)) + + return [Patch(stitches=stitches, color=self.color)] class Stroke(EmbroideryElement): diff --git a/inkstitch/stitches/__init__.py b/inkstitch/stitches/__init__.py index 7959ef62..d2ff0446 100644 --- a/inkstitch/stitches/__init__.py +++ b/inkstitch/stitches/__init__.py @@ -1 +1,3 @@ from running_stitch import * +from auto_fill import auto_fill +from fill import legacy_fill diff --git a/inkstitch/stitches/auto_fill.py b/inkstitch/stitches/auto_fill.py new file mode 100644 index 00000000..cf765bc2 --- /dev/null +++ b/inkstitch/stitches/auto_fill.py @@ -0,0 +1,447 @@ +from fill import intersect_region_with_grating, row_num, stitch_row +from .. import _, PIXELS_PER_MM, Point as InkstitchPoint +import sys +import shapely +import networkx +import math +from itertools import groupby +from collections import deque + + +class MaxQueueLengthExceeded(Exception): + pass + + +def auto_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, running_stitch_length, staggers, starting_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) + + 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)) + + return stitches + + +def which_outline(shape, coords): + """return the index of the outline on which the point resides + + Index 0 is the outer boundary of the fill region. 1+ are the + outlines of the holes. + """ + + # I'd use an intersection check, but floating point errors make it + # fail sometimes. + + point = shapely.geometry.Point(*coords) + outlines = enumerate(list(shape.boundary)) + closest = min(outlines, key=lambda (index, outline): outline.distance(point)) + + return closest[0] + + +def project(shape, coords, outline_index): + """project the point onto the specified outline + + This returns the distance along the outline at which the point resides. + """ + + outline = list(shape.boundary)[outline_index] + return outline.project(shapely.geometry.Point(*coords)) + + +def build_graph(shape, segments, angle, row_spacing): + """build a graph representation of the grating segments + + This function builds a specialized graph (as in graph theory) that will + help us determine a stitching path. The idea comes from this paper: + + http://www.sciencedirect.com/science/article/pii/S0925772100000158 + + The goal is to build a graph that we know must have an Eulerian Path. + An Eulerian Path is a path from edge to edge in the graph that visits + every edge exactly once and ends at the node it started at. Algorithms + exist to build such a path, and we'll use Hierholzer's algorithm. + + A graph must have an Eulerian Path if every node in the graph has an + even number of edges touching it. Our goal here is to build a graph + that will have this property. + + Based on the paper linked above, we'll build the graph as follows: + + * nodes are the endpoints of the grating segments, where they meet + with the outer outline of the region the outlines of the interior + holes in the region. + * edges are: + * each section of the outer and inner outlines of the region, + between nodes + * double every other edge in the outer and inner hole outlines + + Doubling up on some of the edges seems as if it will just mean we have + to stitch those spots twice. This may be true, but it also ensures + that every node has 4 edges touching it, ensuring that a valid stitch + path must exist. + """ + + graph = networkx.MultiGraph() + + # First, add the grating segments as edges. We'll use the coordinates + # of the endpoints as nodes, which networkx will add automatically. + for segment in segments: + # networkx allows us to label nodes with arbitrary data. We'll + # mark this one as a grating segment. + graph.add_edge(*segment, key="segment") + + for node in graph.nodes(): + outline_index = which_outline(shape, node) + outline_projection = project(shape, node, outline_index) + + # Tag each node with its index and projection. + graph.add_node(node, index=outline_index, projection=outline_projection) + + nodes = list(graph.nodes(data=True)) # returns a list of tuples: [(node, {data}), (node, {data}) ...] + nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection'])) + + for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']): + nodes = [ node for node, data in nodes ] + + # heuristic: change the order I visit the nodes in the outline if necessary. + # If the start and endpoints are in the same row, I can't tell which row + # I should treat it as being in. + for i in xrange(len(nodes)): + row0 = row_num(InkstitchPoint(*nodes[0]), angle, row_spacing) + row1 = row_num(InkstitchPoint(*nodes[1]), angle, row_spacing) + + if row0 == row1: + nodes = nodes[1:] + [nodes[0]] + else: + break + + # heuristic: it's useful to try to keep the duplicated edges in the same rows. + # this prevents the BFS from having to search a ton of edges. + min_row_num = min(row0, row1) + if min_row_num % 2 == 0: + edge_set = 0 + 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") + + # duplicate every other edge around this outline + if i % 2 == edge_set: + graph.add_edge(node1, node2, key="extra") + + + if not networkx.is_eulerian(graph): + raise Exception(_("Unable to autofill. This most often happens because your shape is made up of multiple sections that aren't connected.")) + + return graph + + +def node_list_to_edge_list(node_list): + return zip(node_list[:-1], node_list[1:]) + + +def bfs_for_loop(graph, starting_node, max_queue_length=2000): + to_search = deque() + to_search.appendleft(([starting_node], set(), 0)) + + while to_search: + if len(to_search) > max_queue_length: + raise MaxQueueLengthExceeded() + + path, visited_edges, visited_segments = to_search.pop() + ending_node = path[-1] + + # get a list of neighbors paired with the key of the edge I can follow to get there + neighbors = [ + (node, key) + for node, adj in graph.adj[ending_node].iteritems() + for key in adj + ] + + # heuristic: try grating segments first + neighbors.sort(key=lambda (dest, key): key == "segment", reverse=True) + + for next_node, key in neighbors: + # skip if I've already followed this edge + edge = (tuple(sorted((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 + + 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 + + new_visited_edges = visited_edges.copy() + new_visited_edges.add(edge) + + to_search.appendleft((new_path, new_visited_edges, new_visited_segments)) + + +def find_loop(graph, starting_nodes): + """find a loop in the graph that is connected to the existing path + + Start at a candidate node and search through edges to find a path + back to that node. We'll use a breadth-first search (BFS) in order to + find the shortest available loop. + + In most cases, the BFS should not need to search far to find a loop. + The queue should stay relatively short. + + An added heuristic will be used: if the BFS queue's length becomes + too long, we'll abort and try a different starting point. Due to + the way we've set up the graph, there's bound to be a better choice + 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 + + 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 + # constructed from the starting_node (because the + # necessary edges have already been consumed). In that + # 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. + retry.append(starting_node) + + # Darn, couldn't find a loop. Try harder. + starting_nodes.extendleft(retry) + max_queue_length *= 2 + + starting_nodes.extendleft(retry) + return loop + + +def insert_loop(path, loop): + """insert a sub-loop into an existing path + + The path will be a series of edges describing a path through the graph + that ends where it starts. The loop will be similar, and its starting + point will be somewhere along the path. + + Insert the loop into the path, resulting in a longer path. + + Both the path and the loop will be a list of edges specified as a + 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)) + + path will be modified in place. + """ + + loop_start = loop[0][0] + + for i, (start, end) in enumerate(path): + if start == loop_start: + break + + path[i:i] = loop + + +def find_stitch_path(graph, segments): + """find a path that visits every grating segment exactly once + + Theoretically, we just need to find an Eulerian Path in the graph. + However, we don't actually care whether every single edge is visited. + 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. + + 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 + mowing a lawn. + + To do this, we'll use a simple heuristic: try to start from nodes in + the order of most-recently-visited first. + """ + + original_graph = graph + graph = graph.copy() + num_segments = len(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]))] + + graph.remove_edges_from(path) + + segments_visited += 1 + nodes_visited.extend(segments[0]) + + while segments_visited < num_segments: + result = find_loop(graph, nodes_visited) + + if not result: + print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.") + break + + loop, segments = result + + #print >> dbg, "found loop:", loop + #dbg.flush() + + segments_visited += segments + nodes_visited += [edge[0] for edge in loop] + graph.remove_edges_from(loop) + + insert_loop(path, loop) + + #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() + + return path + + +def collapse_sequential_outline_edges(graph, path): + """collapse sequential edges that fall on the same outline + + When the path follows multiple edges along the outline of the region, + replace those edges with the starting and ending points. We'll use + these to stitch along the outline later on. + """ + + start_of_run = None + new_path = [] + + for edge in path: + if graph.has_edge(*edge, key="segment"): + if start_of_run: + # close off the last run + new_path.append((start_of_run, edge[0])) + start_of_run = None + + new_path.append(edge) + else: + if not start_of_run: + start_of_run = edge[0] + + if start_of_run: + # if we were still in a run, close it off + new_path.append((start_of_run, edge[1])) + + return new_path + + +def outline_distance(outline, p1, p2): + # how far around the outline (and in what direction) do I need to go + # to get from p1 to p2? + + p1_projection = outline.project(shapely.geometry.Point(p1)) + p2_projection = outline.project(shapely.geometry.Point(p2)) + + distance = p2_projection - p1_projection + + if abs(distance) > outline.length / 2.0: + # if we'd have to go more than halfway around, it's faster to go + # the other way + if distance < 0: + return distance + outline.length + elif distance > 0: + return distance - outline.length + else: + # this ought not happen, but just for completeness, return 0 if + # p1 and p0 are the same point + return 0 + else: + return distance + + +def connect_points(shape, start, end, running_stitch_length): + outline_index = which_outline(shape, start) + outline = shape.boundary[outline_index] + + pos = outline.project(shapely.geometry.Point(start)) + distance = outline_distance(outline, start, end) + num_stitches = abs(int(distance / 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(*start)] + + for i in xrange(num_stitches): + pos = (pos + one_stitch) % outline.length + + stitches.append(InkstitchPoint(*outline.interpolate(pos).coords[0])) + + end = InkstitchPoint(*end) + if (end - stitches[-1]).length() > 0.1 * PIXELS_PER_MM: + stitches.append(end) + + #print >> dbg, "end connect_points" + #dbg.flush() + + return stitches + + +def path_to_stitches(graph, path, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers): + path = collapse_sequential_outline_edges(graph, path) + + stitches = [] + + for edge in path: + if graph.has_edge(*edge, key="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)) + + return stitches diff --git a/inkstitch/stitches/fill.py b/inkstitch/stitches/fill.py new file mode 100644 index 00000000..52c95172 --- /dev/null +++ b/inkstitch/stitches/fill.py @@ -0,0 +1,244 @@ +from .. import Point as InkstitchPoint, cache, PIXELS_PER_MM +import shapely +import math +import sys + + +def legacy_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, flip, staggers): + rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing, flip) + groups_of_segments = pull_runs(rows_of_segments, shape, row_spacing) + + return [section_to_stitches(group, angle, row_spacing, max_stitch_length, staggers) + for group in groups_of_segments] + + +@cache +def east(angle): + # "east" is the name of the direction that is to the right along a row + return InkstitchPoint(1, 0).rotate(-angle) + + +@cache +def north(angle): + return east(angle).rotate(math.pi / 2) + + +def row_num(point, angle, row_spacing): + return round((point * north(angle)) / row_spacing) + + +def adjust_stagger(stitch, angle, row_spacing, max_stitch_length, staggers): + this_row_num = row_num(stitch, angle, row_spacing) + row_stagger = this_row_num % staggers + stagger_offset = (float(row_stagger) / staggers) * max_stitch_length + offset = ((stitch * east(angle)) - stagger_offset) % max_stitch_length + + return stitch - offset * east(angle) + +def stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, staggers): + # We want our stitches to look like this: + # + # ---*-----------*----------- + # ------*-----------*-------- + # ---------*-----------*----- + # ------------*-----------*-- + # ---*-----------*----------- + # + # Each successive row of stitches will be staggered, with + # num_staggers rows before the pattern repeats. A value of + # 4 gives a nice fill while hiding the needle holes. The + # first row is offset 0%, the second 25%, the third 50%, and + # the fourth 75%. + # + # Actually, instead of just starting at an offset of 0, we + # can calculate a row's offset relative to the origin. This + # way if we have two abutting fill regions, they'll perfectly + # tile with each other. That's important because we often get + # abutting fill regions from pull_runs(). + + beg = InkstitchPoint(*beg) + end = InkstitchPoint(*end) + + row_direction = (end - beg).unit() + segment_length = (end - beg).length() + + # only stitch the first point if it's a reasonable distance away from the + # last stitch + if not stitches or (beg - stitches[-1]).length() > 0.5 * PIXELS_PER_MM: + stitches.append(beg) + + first_stitch = adjust_stagger(beg, angle, row_spacing, max_stitch_length, staggers) + + # we might have chosen our first stitch just outside this row, so move back in + if (first_stitch - beg) * row_direction < 0: + first_stitch += row_direction * max_stitch_length + + offset = (first_stitch - beg).length() + + while offset < segment_length: + stitches.append(beg + offset * row_direction) + offset += max_stitch_length + + if (end - stitches[-1]).length() > 0.1 * PIXELS_PER_MM: + stitches.append(end) + + +def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=None, flip=False): + # the max line length I'll need to intersect the whole shape is the diagonal + (minx, miny, maxx, maxy) = shape.bounds + upper_left = InkstitchPoint(minx, miny) + lower_right = InkstitchPoint(maxx, maxy) + length = (upper_left - lower_right).length() + half_length = length / 2.0 + + # Now get a unit vector rotated to the requested angle. I use -angle + # because shapely rotates clockwise, but my geometry textbooks taught + # me to consider angles as counter-clockwise from the X axis. + direction = InkstitchPoint(1, 0).rotate(-angle) + + # and get a normal vector + normal = direction.rotate(math.pi / 2) + + # I'll start from the center, move in the normal direction some amount, + # and then walk left and right half_length in each direction to create + # a line segment in the grating. + center = InkstitchPoint((minx + maxx) / 2.0, (miny + maxy) / 2.0) + + # I need to figure out how far I need to go along the normal to get to + # the edge of the shape. To do that, I'll rotate the bounding box + # angle degrees clockwise and ask for the new bounding box. The max + # and min y tell me how far to go. + + _, start, _, end = shapely.affinity.rotate(shape, angle, origin='center', use_radians=True).bounds + + # convert start and end to be relative to center (simplifies things later) + start -= center.y + end -= center.y + + height = abs(end - start) + + #print >> dbg, "grating:", start, end, height, row_spacing, end_row_spacing + + # offset start slightly so that rows are always an even multiple of + # row_spacing_px from the origin. This makes it so that abutting + # fill regions at the same angle and spacing always line up nicely. + start -= (start + normal * center) % row_spacing + + rows = [] + + current_row_y = start + + while current_row_y < end: + p0 = center + normal * current_row_y + direction * half_length + p1 = center + normal * current_row_y - direction * half_length + endpoints = [p0.as_tuple(), p1.as_tuple()] + grating_line = shapely.geometry.LineString(endpoints) + + res = grating_line.intersection(shape) + + if (isinstance(res, shapely.geometry.MultiLineString)): + runs = map(lambda line_string: line_string.coords, res.geoms) + else: + if res.is_empty or len(res.coords) == 1: + # ignore if we intersected at a single point or no points + runs = [] + else: + runs = [res.coords] + + if runs: + runs.sort(key=lambda seg: (InkstitchPoint(*seg[0]) - upper_left).length()) + + if flip: + runs.reverse() + runs = map(lambda run: tuple(reversed(run)), runs) + + rows.append(runs) + + if end_row_spacing: + current_row_y += row_spacing + (end_row_spacing - row_spacing) * ((current_row_y - start) / height) + else: + current_row_y += row_spacing + + return rows + +def section_to_stitches(group_of_segments, angle, row_spacing, max_stitch_length, staggers): + stitches = [] + first_segment = True + swap = False + last_end = None + + for segment in group_of_segments: + (beg, end) = segment + + if (swap): + (beg, end) = (end, beg) + + stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, staggers) + + swap = not swap + + return stitches + + +def make_quadrilateral(segment1, segment2): + return shapely.geometry.Polygon((segment1[0], segment1[1], segment2[1], segment2[0], segment1[0])) + + +def is_same_run(segment1, segment2, shape, row_spacing): + line1 = shapely.geometry.LineString(segment1) + line2 = shapely.geometry.LineString(segment2) + + if line1.distance(line2) > row_spacing * 1.1: + return False + + quad = make_quadrilateral(segment1, segment2) + quad_area = quad.area + intersection_area = shape.intersection(quad).area + + return (intersection_area / quad_area) >= 0.9 + + +def pull_runs(rows, shape, row_spacing): + # Given a list of rows, each containing a set of line segments, + # break the area up into contiguous patches of line segments. + # + # This is done by repeatedly pulling off the first line segment in + # each row and calling that a shape. We have to be careful to make + # sure that the line segments are part of the same shape. Consider + # the letter "H", with an embroidery angle of 45 degrees. When + # we get to the bottom of the lower left leg, the next row will jump + # over to midway up the lower right leg. We want to stop there and + # start a new patch. + + # for row in rows: + # print >> sys.stderr, len(row) + + # print >>sys.stderr, "\n".join(str(len(row)) for row in rows) + + runs = [] + count = 0 + while (len(rows) > 0): + run = [] + prev = None + + for row_num in xrange(len(rows)): + row = rows[row_num] + first, rest = row[0], row[1:] + + # TODO: only accept actually adjacent rows here + if prev is not None and not is_same_run(prev, first, shape, row_spacing): + break + + run.append(first) + prev = first + + rows[row_num] = rest + + # print >> sys.stderr, len(run) + runs.append(run) + rows = [row for row in rows if len(row) > 0] + + count += 1 + + return runs + diff --git a/messages.po b/messages.po index 109ad310..a2461b39 100644 --- a/messages.po +++ b/messages.po @@ -8,7 +8,7 @@ msgid "" msgstr "" "Project-Id-Version: PACKAGE VERSION\n" "Report-Msgid-Bugs-To: \n" -"POT-Creation-Date: 2018-02-27 23:14-0500\n" +"POT-Creation-Date: 2018-02-28 20:27-0500\n" "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n" "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n" "Language-Team: LANGUAGE <LL@li.org>\n" @@ -62,14 +62,7 @@ msgstr "" msgid "Max stitch length" msgstr "" -msgid "" -"Unable to autofill. This most often happens because your shape is made up " -"of multiple sections that aren't connected." -msgstr "" - -msgid "" -"Unexpected error while generating fill stitches. Please send your SVG file " -"to lexelby@github." +msgid "Inset" msgstr "" msgid "Satin stitch along paths" |