diff options
Diffstat (limited to 'lib/stitches')
| -rw-r--r-- | lib/stitches/__init__.py | 1 | ||||
| -rw-r--r-- | lib/stitches/auto_fill.py | 60 | ||||
| -rw-r--r-- | lib/stitches/auto_run.py | 284 | ||||
| -rw-r--r-- | lib/stitches/auto_satin.py | 248 | ||||
| -rw-r--r-- | lib/stitches/contour_fill.py | 551 | ||||
| -rw-r--r-- | lib/stitches/fill.py | 7 | ||||
| -rw-r--r-- | lib/stitches/guided_fill.py | 183 | ||||
| -rw-r--r-- | lib/stitches/running_stitch.py | 96 | ||||
| -rw-r--r-- | lib/stitches/utils/autoroute.py | 221 |
9 files changed, 1345 insertions, 306 deletions
diff --git a/lib/stitches/__init__.py b/lib/stitches/__init__.py index 4de88733..8b2738bc 100644 --- a/lib/stitches/__init__.py +++ b/lib/stitches/__init__.py @@ -5,6 +5,7 @@ from .auto_fill import auto_fill from .fill import legacy_fill +from .guided_fill import guided_fill from .running_stitch import * # Can't put this here because we get a circular import :( diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 160d927e..65b1e06d 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -16,8 +16,7 @@ from shapely.strtree import STRtree from ..debug import debug from ..stitch_plan import Stitch from ..svg import PIXELS_PER_MM -from ..utils.geometry import Point as InkstitchPoint -from ..utils.geometry import line_string_to_point_list +from ..utils.geometry import Point as InkstitchPoint, line_string_to_point_list, ensure_multi_line_string from .fill import intersect_region_with_grating, stitch_row from .running_stitch import running_stitch @@ -59,9 +58,10 @@ def auto_fill(shape, starting_point, ending_point=None, underpath=True): - fill_stitch_graph = [] try: - fill_stitch_graph = build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point, ending_point) + rows = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) + segments = [segment for row in rows for segment in row] + fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point) except ValueError: # Small shapes will cause the graph to fail - min() arg is an empty sequence through insert node return fallback(shape, running_stitch_length) @@ -88,9 +88,10 @@ def which_outline(shape, coords): # fail sometimes. point = shgeo.Point(*coords) - outlines = list(shape.boundary) + outlines = ensure_multi_line_string(shape.boundary).geoms outline_indices = list(range(len(outlines))) - closest = min(outline_indices, key=lambda index: outlines[index].distance(point)) + closest = min(outline_indices, + key=lambda index: outlines[index].distance(point)) return closest @@ -101,12 +102,12 @@ def project(shape, coords, outline_index): This returns the distance along the outline at which the point resides. """ - outline = list(shape.boundary)[outline_index] + outline = ensure_multi_line_string(shape.boundary).geoms[outline_index] return outline.project(shgeo.Point(*coords)) @debug.time -def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point=None, ending_point=None): +def build_fill_stitch_graph(shape, segments, starting_point=None, ending_point=None): """build a graph representation of the grating segments This function builds a specialized graph (as in graph theory) that will @@ -141,10 +142,6 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting debug.add_layer("auto-fill fill stitch") - # Convert the shape into a set of parallel line segments. - 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 = networkx.MultiGraph() # First, add the grating segments as edges. We'll use the coordinates @@ -152,7 +149,7 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting 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", underpath_edges=[]) + graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[], geometry=shgeo.LineString(segment)) tag_nodes_with_outline_and_projection(graph, shape, graph.nodes()) add_edges_between_outline_nodes(graph, duplicate_every_other=True) @@ -174,7 +171,7 @@ def insert_node(graph, shape, point): point = tuple(point) outline = which_outline(shape, point) projection = project(shape, point, outline) - projected_point = list(shape.boundary)[outline].interpolate(projection) + projected_point = ensure_multi_line_string(shape.boundary).geoms[outline].interpolate(projection) node = (projected_point.x, projected_point.y) edges = [] @@ -199,7 +196,8 @@ def tag_nodes_with_outline_and_projection(graph, shape, nodes): def add_boundary_travel_nodes(graph, shape): - for outline_index, outline in enumerate(shape.boundary): + outlines = ensure_multi_line_string(shape.boundary).geoms + for outline_index, outline in enumerate(outlines): prev = None for point in outline.coords: point = shgeo.Point(point) @@ -230,7 +228,8 @@ def add_edges_between_outline_nodes(graph, duplicate_every_other=False): outline. """ - nodes = list(graph.nodes(data=True)) # returns a list of tuples: [(node, {data}), (node, {data}) ...] + # returns a list of tuples: [(node, {data}), (node, {data}) ...] + nodes = list(graph.nodes(data=True)) nodes.sort(key=lambda node: (node[1]['outline'], node[1]['projection'])) for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['outline']): @@ -261,7 +260,10 @@ def fallback(shape, running_stitch_length): matter. """ - return running_stitch(line_string_to_point_list(shape.boundary[0]), running_stitch_length) + boundary = ensure_multi_line_string(shape.boundary) + outline = boundary.geoms[0] + + return running_stitch(line_string_to_point_list(outline), running_stitch_length) @debug.time @@ -325,7 +327,7 @@ def get_segments(graph): segments = [] for start, end, key, data in graph.edges(keys=True, data=True): if key == 'segment': - segments.append(shgeo.LineString((start, end))) + segments.append(data["geometry"]) return segments @@ -363,7 +365,8 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): # segments that _might_ intersect ls. Refining the result is # necessary but the STRTree still saves us a ton of time. if segment.crosses(ls): - start, end = segment.coords + start = segment.coords[0] + end = segment.coords[-1] fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge) # The weight of a travel edge is the length of the line segment. @@ -384,19 +387,10 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): def travel_grating(shape, angle, row_spacing): - rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing) - segments = list(chain(*rows_of_segments)) - - return shgeo.MultiLineString(segments) + rows = intersect_region_with_grating(shape, angle, row_spacing) + segments = [segment for row in rows for segment in row] - -def ensure_multi_line_string(thing): - """Given either a MultiLineString or a single LineString, return a MultiLineString""" - - if isinstance(thing, shgeo.LineString): - return shgeo.MultiLineString([thing]) - else: - return thing + return shgeo.MultiLineString(list(segments)) def build_travel_edges(shape, fill_angle): @@ -443,7 +437,7 @@ def build_travel_edges(shape, fill_angle): debug.log_line_strings(grating3, "grating3") endpoints = [coord for mls in (grating1, grating2, grating3) - for ls in mls + for ls in mls.geoms for coord in ls.coords] diagonal_edges = ensure_multi_line_string(grating1.symmetric_difference(grating2)) @@ -451,7 +445,7 @@ def build_travel_edges(shape, fill_angle): # without this, floating point inaccuracies prevent the intersection points from lining up perfectly. vertical_edges = ensure_multi_line_string(snap(grating3.difference(grating1), diagonal_edges, 0.005)) - return endpoints, chain(diagonal_edges, vertical_edges) + return endpoints, chain(diagonal_edges.geoms, vertical_edges.geoms) def nearest_node(nodes, point, attr=None): diff --git a/lib/stitches/auto_run.py b/lib/stitches/auto_run.py new file mode 100644 index 00000000..847a1bcd --- /dev/null +++ b/lib/stitches/auto_run.py @@ -0,0 +1,284 @@ +# Authors: see git history +# +# Copyright (c) 2022 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +from collections import defaultdict + +import networkx as nx +from shapely.geometry import LineString, MultiLineString, MultiPoint, Point +from shapely.ops import nearest_points, substring, unary_union + +import inkex + +from ..commands import add_commands +from ..elements import Stroke +from ..i18n import _ +from ..svg import PIXELS_PER_MM, generate_unique_id +from ..svg.tags import INKSCAPE_LABEL, INKSTITCH_ATTRIBS +from .utils.autoroute import (add_elements_to_group, add_jumps, + create_new_group, find_path, + get_starting_and_ending_nodes, + preserve_original_groups, + remove_original_elements) + + +class LineSegments: + ''' + Takes elements and splits them into segments. + + Attributes: + _lines -- a list of LineStrings from the subpaths of the Stroke elements + _elements -- a list of Stroke elements for each corresponding line in _lines + _intersection_points -- a dictionary with intersection points {line_index: [intersection_points]} + segments -- (public) a list of segments and corresponding elements [[segment, element], ...] + ''' + + def __init__(self, elements): + self._lines = [] + self._elements = [] + self._intersection_points = defaultdict(list) + self.segments = [] + + self._process_elements(elements) + self._get_intersection_points() + self._get_segments() + + def _process_elements(self, elements): + for element in elements: + lines = element.as_multi_line_string().geoms + + for line in lines: + # split at self-intersections if necessary + unary_lines = unary_union(line) + if isinstance(unary_lines, MultiLineString): + for unary_line in unary_lines.geoms: + self._lines.append(unary_line) + self._elements.append(element) + else: + self._lines.append(line) + self._elements.append(element) + + def _get_intersection_points(self): + for i, line1 in enumerate(self._lines): + for j in range(i + 1, len(self._lines)): + line2 = self._lines[j] + distance = line1.distance(line2) + if distance > 50: + continue + if not distance == 0: + # add nearest points + near = nearest_points(line1, line2) + self._add_point(i, near[0]) + self._add_point(j, near[1]) + # add intersections + intersections = line1.intersection(line2) + if isinstance(intersections, Point): + self._add_point(i, intersections) + self._add_point(j, intersections) + elif isinstance(intersections, MultiPoint): + for point in intersections.geoms: + self._add_point(i, point) + self._add_point(j, point) + elif isinstance(intersections, LineString): + for point in intersections.coords: + self._add_point(i, Point(*point)) + self._add_point(j, Point(*point)) + + def _add_point(self, element, point): + self._intersection_points[element].append(point) + + def _get_segments(self): + ''' + Splits elements into segments at intersection and "almost intersecions". + The split method would make this very easy (it can split a MultiString with + MultiPoints) but sadly it fails too often, while snap moves the points away + from where we want them. So we need to calculate the distance along the line + and finally split it into segments with shapelys substring method. + ''' + self.segments = [] + for i, line in enumerate(self._lines): + length = line.length + points = self._intersection_points[i] + + distances = [0, length] + for point in points: + distances.append(line.project(point)) + distances = sorted(set(distances)) + + for j in range(len(distances) - 1): + start = distances[j] + end = distances[j + 1] + + if end - start > 0.1: + seg = substring(line, start, end) + self.segments.append([seg, self._elements[i]]) + + +def autorun(elements, preserve_order=False, break_up=None, starting_point=None, ending_point=None, trim=False): + graph = build_graph(elements, preserve_order, break_up) + graph = add_jumps(graph, elements, preserve_order) + + starting_point, ending_point = get_starting_and_ending_nodes( + graph, elements, preserve_order, starting_point, ending_point) + + path = find_path(graph, starting_point, ending_point) + path = add_path_attribs(path) + + new_elements, trims, original_parents = path_to_elements(graph, path, trim) + + if preserve_order: + preserve_original_groups(new_elements, original_parents) + else: + parent = elements[0].node.getparent() + insert_index = parent.index(elements[0].node) + group = create_new_group(parent, insert_index, _("Auto-Run")) + add_elements_to_group(new_elements, group) + + if trim: + add_trims(new_elements, trims) + + remove_original_elements(elements) + + +def build_graph(elements, preserve_order, break_up): + if preserve_order: + graph = nx.DiGraph() + else: + graph = nx.Graph() + + if not break_up: + segments = [] + for element in elements: + line_strings = [[line, element] for line in element.as_multi_line_string().geoms] + segments.extend(line_strings) + else: + segments = LineSegments(elements).segments + + for segment, element in segments: + for c1, c2 in zip(segment.coords[:-1], segment.coords[1:]): + start = Point(*c1) + end = Point(*c2) + + graph.add_node(str(start), point=start) + graph.add_node(str(end), point=end) + graph.add_edge(str(start), str(end), element=element) + + if preserve_order: + # The graph is a directed graph, but we want to allow travel in + # any direction, so we add the edge in the opposite direction too. + graph.add_edge(str(end), str(start), element=element) + + return graph + + +def add_path_attribs(path): + # find_path() will have duplicated some of the edges in the graph. We don't + # want to sew the same running stitch twice. If a running stitch section appears + # twice in the path, we'll sew the first occurrence as a simple running stitch without + # the original running stitch repetitions and bean stitch settings. + seen = set() + for i, point in reversed(list(enumerate(path))): + if point in seen: + path[i] = (*point, "underpath") + else: + path[i] = (*point, "autorun") + seen.add(point) + seen.add((point[1], point[0])) + return path + + +def path_to_elements(graph, path, trim): # noqa: C901 + element_list = [] + original_parents = [] + trims = [] + + d = "" + position = 0 + path_direction = "autorun" + just_trimmed = False + el = None + for start, end, direction in path: + element = graph[start][end].get('element') + start_coord = graph.nodes[start]['point'] + end_coord = graph.nodes[end]['point'] + if element: + el = element + + if just_trimmed: + if direction == "underpath": + # no sense in doing underpath after we trim + continue + else: + just_trimmed = False + + # create a new element if direction (purpose) changes + if direction != path_direction: + if d: + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + d = "" + position += 1 + path_direction = direction + + if d == "": + d = "M %s %s, %s %s" % (start_coord.x, start_coord.y, end_coord.x, end_coord.y) + else: + d += ", %s %s" % (end_coord.x, end_coord.y) + elif el and d: + # this is a jump, so complete the element whose path we've been building + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + d = "" + + if trim and start_coord.distance(end_coord) > 0.75 * PIXELS_PER_MM: + trims.append(position) + just_trimmed = True + + position += 1 + + if d: + element_list.append(create_element(d, position, path_direction, el)) + original_parents.append(el.node.getparent()) + + return element_list, trims, original_parents + + +def create_element(path, position, direction, element): + if not path: + return + + style = inkex.Style(element.node.get("style")) + style = style + inkex.Style("stroke-dasharray:0.5,0.5;fill:none;") + el_id = "%s_%s_" % (direction, position) + + index = position + 1 + if direction == "autorun": + label = _("AutoRun %d") % index + else: + label = _("AutoRun Underpath %d") % index + + stitch_length = element.node.get(INKSTITCH_ATTRIBS['running_stitch_length_mm'], '') + bean = element.node.get(INKSTITCH_ATTRIBS['bean_stitch_repeats'], 0) + repeats = int(element.node.get(INKSTITCH_ATTRIBS['repeats'], 1)) + if repeats % 2 == 0: + repeats -= 1 + + node = inkex.PathElement() + node.set("id", generate_unique_id(element.node, el_id)) + node.set(INKSCAPE_LABEL, label) + node.set("d", path) + node.set("style", str(style)) + if stitch_length: + node.set(INKSTITCH_ATTRIBS['running_stitch_length_mm'], stitch_length) + if direction == "autorun": + node.set(INKSTITCH_ATTRIBS['repeats'], str(repeats)) + if bean: + node.set(INKSTITCH_ATTRIBS['bean_stitch_repeats'], bean) + + return Stroke(node) + + +def add_trims(elements, trim_indices): + for i in trim_indices: + add_commands(elements[i], ["trim"]) diff --git a/lib/stitches/auto_satin.py b/lib/stitches/auto_satin.py index 2b7f0906..ba5c8698 100644 --- a/lib/stitches/auto_satin.py +++ b/lib/stitches/auto_satin.py @@ -6,19 +6,24 @@ import math from itertools import chain -import inkex import networkx as nx from shapely import geometry as shgeo from shapely.geometry import Point as ShapelyPoint +import inkex + from ..commands import add_commands from ..elements import SatinColumn, Stroke from ..i18n import _ -from ..svg import (PIXELS_PER_MM, generate_unique_id, get_correction_transform, - line_strings_to_csp) -from ..svg.tags import (INKSCAPE_LABEL, INKSTITCH_ATTRIBS) +from ..svg import PIXELS_PER_MM, generate_unique_id, line_strings_to_csp +from ..svg.tags import INKSCAPE_LABEL, INKSTITCH_ATTRIBS from ..utils import Point as InkstitchPoint from ..utils import cache, cut +from .utils.autoroute import (add_elements_to_group, add_jumps, + create_new_group, find_path, + get_starting_and_ending_nodes, + preserve_original_groups, + remove_original_elements) class SatinSegment(object): @@ -177,7 +182,7 @@ class SatinSegment(object): class JumpStitch(object): """A jump stitch between two points.""" - def __init__(self, start, end): + def __init__(self, start, end, source_element, destination_element): """Initialize a JumpStitch. Arguments: @@ -186,6 +191,8 @@ class JumpStitch(object): self.start = start self.end = end + self.source_element = source_element + self.destination_element = destination_element def is_sequential(self, other): # Don't bother joining jump stitches. @@ -196,6 +203,15 @@ class JumpStitch(object): def length(self): return self.start.distance(self.end) + def as_line_string(self): + return shgeo.LineString((self.start, self.end)) + + def should_trim(self): + actual_jump = self.as_line_string().difference(self.source_element.shape) + actual_jump = actual_jump.difference(self.destination_element.shape) + + return actual_jump.length > PIXELS_PER_MM + class RunningStitch(object): """Running stitch along a path.""" @@ -326,7 +342,7 @@ def auto_satin(elements, preserve_order=False, starting_point=None, ending_point if preserve_order: preserve_original_groups(new_elements, original_parents) else: - group = create_new_group(parent, index) + group = create_new_group(parent, index, _("Auto-Route")) add_elements_to_group(new_elements, group) name_elements(new_elements, preserve_order) @@ -358,8 +374,8 @@ def build_graph(elements, preserve_order=False): for segment in segments: # This is necessary because shapely points aren't hashable and thus # can't be used as nodes directly. - graph.add_node(str(segment.start_point), point=segment.start_point) - graph.add_node(str(segment.end_point), point=segment.end_point) + graph.add_node(str(segment.start_point), point=segment.start_point, element=element) + graph.add_node(str(segment.end_point), point=segment.end_point, element=element) graph.add_edge(str(segment.start_point), str( segment.end_point), segment=segment, element=element) @@ -373,168 +389,6 @@ def build_graph(elements, preserve_order=False): return graph -def get_starting_and_ending_nodes(graph, elements, preserve_order, starting_point, ending_point): - """Find or choose the starting and ending graph nodes. - - If points were passed, we'll find the nearest graph nodes. Since we split - every satin up into 1mm-chunks, we'll be at most 1mm away which is good - enough. - - If we weren't given starting and ending points, we'll pic kthe far left and - right nodes. - - returns: - (starting graph node, ending graph node) - """ - - nodes = [] - - nodes.append(find_node(graph, starting_point, - min, preserve_order, elements[0])) - nodes.append(find_node(graph, ending_point, - max, preserve_order, elements[-1])) - - return nodes - - -def find_node(graph, point, extreme_function, constrain_to_satin=False, satin=None): - if constrain_to_satin: - nodes = get_nodes_on_element(graph, satin) - else: - nodes = graph.nodes() - - if point is None: - return extreme_function(nodes, key=lambda node: graph.nodes[node]['point'].x) - else: - point = shgeo.Point(*point) - return min(nodes, key=lambda node: graph.nodes[node]['point'].distance(point)) - - -def get_nodes_on_element(graph, element): - nodes = set() - - for start_node, end_node, element_for_edge in graph.edges(data='element'): - if element_for_edge is element: - nodes.add(start_node) - nodes.add(end_node) - - return nodes - - -def add_jumps(graph, elements, preserve_order): - """Add jump stitches between elements as necessary. - - Jump stitches are added to ensure that all elements can be reached. Only the - minimal number and length of jumps necessary will be added. - """ - - if preserve_order: - # For each sequential pair of elements, find the shortest possible jump - # stitch between them and add it. The directions of these new edges - # will enforce stitching the satins in order. - - for element1, element2 in zip(elements[:-1], elements[1:]): - potential_edges = [] - - nodes1 = get_nodes_on_element(graph, element1) - nodes2 = get_nodes_on_element(graph, element2) - - for node1 in nodes1: - for node2 in nodes2: - point1 = graph.nodes[node1]['point'] - point2 = graph.nodes[node2]['point'] - potential_edges.append((point1, point2)) - - if potential_edges: - edge = min(potential_edges, key=lambda p1_p2: p1_p2[0].distance(p1_p2[1])) - graph.add_edge(str(edge[0]), str(edge[1]), jump=True) - else: - # networkx makes this super-easy! k_edge_agumentation tells us what edges - # we need to add to ensure that the graph is fully connected. We give it a - # set of possible edges that it can consider adding (avail). Each edge has - # a weight, which we'll set as the length of the jump stitch. The - # algorithm will minimize the total length of jump stitches added. - for jump in nx.k_edge_augmentation(graph, 1, avail=list(possible_jumps(graph))): - graph.add_edge(*jump, jump=True) - - -def possible_jumps(graph): - """All possible jump stitches in the graph with their lengths. - - Returns: a generator of tuples: (node1, node2, length) - """ - - # We'll take the easy approach and list all edges that aren't already in - # the graph. networkx's algorithm is pretty efficient at ignoring - # pointless options like jumping between two points on the same satin. - - for start, end in nx.complement(graph).edges(): - start_point = graph.nodes[start]['point'] - end_point = graph.nodes[end]['point'] - yield (start, end, start_point.distance(end_point)) - - -def find_path(graph, starting_node, ending_node): - """Find a path through the graph that sews every satin.""" - - # This is done in two steps. First, we find the shortest path from the - # start to the end. We remove it from the graph, and proceed to step 2. - # - # Then, we traverse the path node by node. At each node, we follow any - # branchings with a depth-first search. We travel down each branch of - # the tree, inserting each seen branch into the tree. When the DFS - # hits a dead-end, as it back-tracks, we also add the seen edges _again_. - # Repeat until there are no more edges left in the graph. - # - # Visiting the edges again on the way back allows us to set up - # "underpathing". As we stitch down each branch, we'll do running stitch. - # Then when we come back up, we'll do satin stitch, covering the previous - # running stitch. - path = nx.shortest_path(graph, starting_node, ending_node) - - # Copy the graph so that we can remove the edges as we visit them. - # This also converts the directed graph into an undirected graph in the - # case that "preserve_order" is set. This way we avoid going back and - # forth on each satin twice due to the satin edges being in the graph - # twice (forward and reverse). - graph = nx.Graph(graph) - graph.remove_edges_from(list(zip(path[:-1], path[1:]))) - - final_path = [] - prev = None - for node in path: - if prev is not None: - final_path.append((prev, node)) - prev = node - - for n1, n2, edge_type in list(nx.dfs_labeled_edges(graph, node)): - if n1 == n2: - # dfs_labeled_edges gives us (start, start, "forward") for - # the starting node for some reason - continue - - if edge_type == "forward": - final_path.append((n1, n2)) - graph.remove_edge(n1, n2) - elif edge_type == "reverse": - final_path.append((n2, n1)) - elif edge_type == "nontree": - # a "nontree" happens when there exists an edge from n1 to n2 - # but n2 has already been visited. It's a dead-end that runs - # into part of the graph that we've already traversed. We - # do still need to make sure that satin is sewn, so we travel - # down and back on this edge. - # - # It's possible for a given "nontree" edge to be listed more - # than once so we'll deduplicate. - if (n1, n2) in graph.edges: - final_path.append((n1, n2)) - final_path.append((n2, n1)) - graph.remove_edge(n1, n2) - - return final_path - - def reversed_path(path): """Generator for a version of the path travelling in the opposite direction. @@ -563,7 +417,10 @@ def path_to_operations(graph, path): segment = segment.reversed() operations.append(segment) else: - operations.append(JumpStitch(graph.nodes[start]['point'], graph.nodes[end]['point'])) + operations.append(JumpStitch(graph.nodes[start]['point'], + graph.nodes[end]['point'], + graph.nodes[start]['element'], + graph.nodes[end]['element'])) # find_path() will have duplicated some of the edges in the graph. We don't # want to sew the same satin twice. If a satin section appears twice in the @@ -616,59 +473,12 @@ def operations_to_elements_and_trims(operations, preserve_order): elements.append(operation.to_element()) original_parent_nodes.append(operation.original_node.getparent()) elif isinstance(operation, (JumpStitch)): - if elements and operation.length > 0.75 * PIXELS_PER_MM: + if elements and operation.should_trim(): trims.append(len(elements) - 1) return elements, list(set(trims)), original_parent_nodes -def remove_original_elements(elements): - for element in elements: - for command in element.commands: - command_group = command.use.getparent() - if command_group is not None and command_group.get('id').startswith('command_group'): - remove_from_parent(command_group) - else: - remove_from_parent(command.connector) - remove_from_parent(command.use) - remove_from_parent(element.node) - - -def remove_from_parent(node): - if node.getparent() is not None: - node.getparent().remove(node) - - -def preserve_original_groups(elements, original_parent_nodes): - """Ensure that all elements are contained in the original SVG group elements. - - When preserve_order is True, no SatinColumn or Stroke elements will be - reordered in the XML tree. This makes it possible to preserve original SVG - group membership. We'll ensure that each newly-created Element is added - to the group that contained the original SatinColumn that spawned it. - """ - - for element, parent in zip(elements, original_parent_nodes): - if parent is not None: - parent.append(element.node) - element.node.set('transform', get_correction_transform(parent, child=True)) - - -def create_new_group(parent, insert_index): - group = inkex.Group(attrib={ - INKSCAPE_LABEL: _("Auto-Satin"), - "transform": get_correction_transform(parent, child=True) - }) - parent.insert(insert_index, group) - - return group - - -def add_elements_to_group(elements, group): - for element in elements: - group.append(element.node) - - def name_elements(new_elements, preserve_order): """Give the newly-created SVG objects useful names. diff --git a/lib/stitches/contour_fill.py b/lib/stitches/contour_fill.py new file mode 100644 index 00000000..c42cc6f2 --- /dev/null +++ b/lib/stitches/contour_fill.py @@ -0,0 +1,551 @@ +from collections import namedtuple +from itertools import chain + +import networkx as nx +import numpy as np +import trimesh +from shapely.geometry import GeometryCollection, MultiPolygon, Polygon, LineString, Point +from shapely.geometry.polygon import orient +from shapely.ops import nearest_points +from shapely.ops import polygonize + +from .running_stitch import running_stitch +from ..stitch_plan import Stitch +from ..utils import DotDict +from ..utils.geometry import cut, reverse_line_string, roll_linear_ring +from ..utils.geometry import ensure_geometry_collection, ensure_multi_polygon + + +class Tree(nx.DiGraph): + # This lets us do tree.nodes['somenode'].parent instead of the default + # tree.nodes['somenode']['parent']. + node_attr_dict_factory = DotDict + + def __init__(self, *args, **kwargs): + self.__node_num = 0 + super().__init__(**kwargs) + + def generate_node_name(self): + node = self.__node_num + self.__node_num += 1 + + return node + + +nearest_neighbor_tuple = namedtuple( + "nearest_neighbor_tuple", + [ + "nearest_point_parent", + "nearest_point_child", + "proj_distance_parent", + "child_node", + ], +) + + +def _offset_linear_ring(ring, offset, resolution, join_style, mitre_limit): + result = Polygon(ring).buffer(-offset, resolution, cap_style=2, join_style=join_style, mitre_limit=mitre_limit, single_sided=True) + result = ensure_multi_polygon(result) + rings = GeometryCollection([poly.exterior for poly in result.geoms]) + rings = rings.simplify(0.01, False) + + return _take_only_valid_linear_rings(rings) + + +def _take_only_valid_linear_rings(rings): + """ + Removes all geometries which do not form a "valid" LinearRing. + + A "valid" ring is one that does not form a straight line. + """ + + valid_rings = [] + + for ring in ensure_geometry_collection(rings).geoms: + if len(ring.coords) > 3 or (len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1]): + valid_rings.append(ring) + + return GeometryCollection(valid_rings) + + +def _orient_linear_ring(ring, clockwise=True): + # Unfortunately for us, Inkscape SVGs have an inverted Y coordinate. + # Normally we don't have to care about that, but in this very specific + # case, the meaning of is_ccw is flipped. It actually tests whether + # a ring is clockwise. That makes this logic super-confusing. + if ring.is_ccw != clockwise: + return reverse_line_string(ring) + else: + return ring + + +def _orient_tree(tree, clockwise=True): + """ + Orient all linear rings in the tree. + + Since naturally holes have the opposite point ordering than non-holes we + make all lines within the tree uniform (having all the same ordering + direction) + """ + + for node in tree.nodes.values(): + node.val = _orient_linear_ring(node.val, clockwise) + + +def offset_polygon(polygon, offset, join_style, clockwise): + """ + Convert a polygon to a tree of isocontours. + + An isocontour is an offset version of the polygon's boundary. For example, + the isocontours of a circle are a set of concentric circles inside the + circle. + + This function takes a polygon (which may have holes) as input and creates + isocontours until the polygon is filled completely. The isocontours are + returned as a Tree, with a parent-child relationship indicating that the + parent isocontour contains the child isocontour. + + Arguments: + polygon - The shapely Polygon which may have holes + offset - The spacing between isocontours + join_style - Join style used when offsetting the Polygon border to create + isocontours. Can be round, mitered or bevel, as defined by + shapely: + https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE + clockwise - If True, isocontour points are in clockwise order; if False, counter-clockwise. + + Return Value: + Tree - see above + """ + + ordered_polygon = orient(polygon, -1) + tree = Tree() + tree.add_node('root', type='node', parent=None, val=ordered_polygon.exterior) + active_polygons = ['root'] + active_holes = [[]] + + for hole in ordered_polygon.interiors: + hole_node = tree.generate_node_name() + tree.add_node(hole_node, type="hole", val=hole) + active_holes[0].append(hole_node) + + while len(active_polygons) > 0: + current_poly = active_polygons.pop() + current_holes = active_holes.pop() + + outer, inners = _offset_polygon_and_holes(tree, current_poly, current_holes, offset, join_style) + polygons = _match_polygons_and_holes(outer, inners) + + for polygon in polygons.geoms: + new_polygon, new_holes = _convert_polygon_to_nodes(tree, polygon, parent_polygon=current_poly, child_holes=current_holes) + + if new_polygon is not None: + active_polygons.append(new_polygon) + active_holes.append(new_holes) + + for previous_hole in current_holes: + # If the previous holes are not + # contained in the new holes they + # have been merged with the + # outer polygon + if not tree.nodes[previous_hole].parent: + tree.nodes[previous_hole].parent = current_poly + tree.add_edge(current_poly, previous_hole) + + _orient_tree(tree, clockwise) + return tree + + +def _offset_polygon_and_holes(tree, poly, holes, offset, join_style): + outer = _offset_linear_ring( + tree.nodes[poly].val, + offset, + resolution=5, + join_style=join_style, + mitre_limit=10, + ) + + inners = [] + for hole in holes: + inner = _offset_linear_ring( + tree.nodes[hole].val, + -offset, # take negative offset for holes + resolution=5, + join_style=join_style, + mitre_limit=10, + ) + if not inner.is_empty: + inners.append(Polygon(inner.geoms[0])) + + return outer, inners + + +def _match_polygons_and_holes(outer, inners): + result = MultiPolygon(polygonize(outer.geoms)) + if len(inners) > 0: + result = ensure_geometry_collection(result.difference(MultiPolygon(inners))) + + return result + + +def _convert_polygon_to_nodes(tree, polygon, parent_polygon, child_holes): + polygon = orient(polygon, -1) + + if polygon.area < 0.1: + return None, None + + valid_rings = _take_only_valid_linear_rings(polygon.exterior) + + try: + exterior = valid_rings.geoms[0] + except IndexError: + return None, None + + node = tree.generate_node_name() + tree.add_node(node, type='node', parent=parent_polygon, val=exterior) + tree.add_edge(parent_polygon, node) + + hole_nodes = [] + for hole in polygon.interiors: + hole_node = tree.generate_node_name() + tree.add_node(hole_node, type="hole", val=hole) + for previous_hole in child_holes: + if Polygon(hole).contains(Polygon(tree.nodes[previous_hole].val)): + tree.nodes[previous_hole].parent = hole_node + tree.add_edge(hole_node, previous_hole) + hole_nodes.append(hole_node) + + return node, hole_nodes + + +def _get_nearest_points_closer_than_thresh(travel_line, next_line, threshold): + """ + Find the first point along travel_line that is within threshold of next_line. + + Input: + travel_line - The "parent" line for which the distance should + be minimized to enter next_line + next_line - contains the next_line which need to be entered + threshold - The distance between travel_line and next_line needs + to below threshold to be a valid point for entering + + Return value: + tuple or None + - the tuple structure is: + (point in travel_line, point in next_line) + - None is returned if there is no point that satisfies the threshold. + """ + + # We'll buffer next_line and find the intersection with travel_line. + # Then we'll return the very first point in the intersection, + # matched with a corresponding point on next_line. Fortunately for + # us, intersection of a Polygon with a LineString yields pieces of + # the LineString in the same order as the input LineString. + threshold_area = next_line.buffer(threshold) + portion_within_threshold = travel_line.intersection(threshold_area) + + if portion_within_threshold.is_empty: + return None + else: + # Projecting with 0 lets us avoid distinguishing between LineString and + # MultiLineString. + parent_point = Point(portion_within_threshold.interpolate(0)) + return nearest_points(parent_point, next_line) + + +def _create_nearest_points_list(travel_line, tree, children, threshold, threshold_hard): + """Determine the best place to enter each of parent's children + + Arguments: + travel_line - The "parent" line for which the distance should + be minimized to enter each child + children - children of travel_line that need to be entered + threshold - The distance between travel_line and a child should + to be below threshold to be a valid point for entering + threshold_hard - As a last resort, we can accept an entry point + that is this far way + + Return value: + list of nearest_neighbor_tuple - indicating where to enter each + respective child + """ + + children_nearest_points = [] + + for child in children: + result = _get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold) + if result is None: + # where holes meet outer borders a distance + # up to 2 * used offset can arise + result = _get_nearest_points_closer_than_thresh(travel_line, tree.nodes[child].val, threshold_hard) + + proj = travel_line.project(result[0]) + children_nearest_points.append( + nearest_neighbor_tuple( + nearest_point_parent=result[0], + nearest_point_child=result[1], + proj_distance_parent=proj, + child_node=child, + ) + ) + + return children_nearest_points + + +def _find_path_inner_to_outer(tree, node, offset, starting_point, avoid_self_crossing, forward=True): + """Find a stitch path for this ring and its children. + + Strategy: A connection from parent to child is made as fast as possible to + reach the innermost child as fast as possible in order to stitch afterwards + from inner to outer. + + This function calls itself recursively to find a stitch path for each child + (and its children). + + Arguments: + tree - a Tree of isocontours (as returned by offset_polygon) + offset - offset that was passed to offset_polygon + starting_point - starting point for stitching + avoid_self_crossing - if True, tries to generate a path that does not + cross itself. + forward - if True, this ring will be stitched in its natural direction + (used internally by avoid_self_crossing) + + Return value: + LineString -- the stitching path + """ + + current_node = tree.nodes[node] + current_ring = current_node.val + + if not forward and avoid_self_crossing: + current_ring = reverse_line_string(current_ring) + + # reorder the coordinates of this ring so that it starts with + # a point nearest the starting_point + start_distance = current_ring.project(starting_point) + current_ring = roll_linear_ring(current_ring, start_distance) + current_node.val = current_ring + + # Find where along this ring to connect to each child. + nearest_points_list = _create_nearest_points_list( + current_ring, + tree, + tree[node], + threshold=1.5 * offset, + threshold_hard=2.05 * offset + ) + nearest_points_list.sort(key=lambda tup: tup.proj_distance_parent) + + result_coords = [] + if not nearest_points_list: + # We have no children, so we're at the center of a spiral. Reversing + # the innermost ring gives a nicer visual appearance. + if not avoid_self_crossing: + current_ring = reverse_line_string(current_ring) + else: + # This is a recursive algorithm. We'll stitch along this ring, pausing + # to jump to each child ring in turn and sew it before continuing on + # this ring. We'll end back where we started. + + result_coords.append(current_ring.coords[0]) + distance_so_far = 0 + for child_connection in nearest_points_list: + # Cut this ring into pieces before and after where this child will connect. + before, after = cut(current_ring, child_connection.proj_distance_parent - distance_so_far) + distance_so_far = child_connection.proj_distance_parent + + # Stitch the part leading up to this child. + if before is not None: + result_coords.extend(before.coords) + + # Stitch this child. The child will start and end in the same + # place, which should be close to our current location. + child_path = _find_path_inner_to_outer( + tree, + child_connection.child_node, + offset, + child_connection.nearest_point_child, + avoid_self_crossing, + not forward + ) + result_coords.extend(child_path.coords) + + # Skip ahead a little bit on this ring before resuming. This + # gives a nice spiral pattern, where we spiral out from the + # innermost child. + if after is not None: + skip, after = cut(after, offset) + distance_so_far += offset + + current_ring = after + + if current_ring is not None: + # skip a little at the end so we don't end exactly where we started. + remaining_length = current_ring.length + if remaining_length > offset: + current_ring, skip = cut(current_ring, current_ring.length - offset) + + result_coords.extend(current_ring.coords) + + return LineString(result_coords) + + +def inner_to_outer(tree, offset, stitch_length, starting_point, avoid_self_crossing): + """Fill a shape with spirals, from innermost to outermost.""" + + stitch_path = _find_path_inner_to_outer(tree, 'root', offset, starting_point, avoid_self_crossing) + points = [Stitch(*point) for point in stitch_path.coords] + stitches = running_stitch(points, stitch_length) + + return stitches + + +def _reorder_linear_ring(ring, start): + distances = ring - start + start_index = np.argmin(np.linalg.norm(distances, axis=1)) + return np.roll(ring, -start_index, axis=0) + + +def _interpolate_linear_rings(ring1, ring2, max_stitch_length, start=None): + """ + Interpolate between two LinearRings + + Creates a path from start_point on ring1 and around the rings, ending at a + nearby point on ring2. The path will smoothly transition from ring1 to + ring2 as it travels around the rings. + + Inspired by interpolate() from https://github.com/mikedh/pocketing/blob/master/pocketing/polygons.py + + Arguments: + ring1 -- LinearRing start point will lie on + ring2 -- LinearRing end point will lie on + max_stitch_length -- maximum stitch length (used to calculate resampling accuracy) + start -- Point on ring1 to start at, as a tuple + + Return value: Path interpolated between two LinearRings, as a LineString. + """ + + # Resample the two LinearRings so that they are the same number of points + # long. Then take the corresponding points in each ring and interpolate + # between them, gradually going more toward ring2. + # + # This is a little less accurate than the method in interpolate(), but several + # orders of magnitude faster because we're not building and querying a KDTree. + + num_points = int(20 * ring1.length / max_stitch_length) + ring1_resampled = trimesh.path.traversal.resample_path(np.array(ring1.coords), count=num_points) + ring2_resampled = trimesh.path.traversal.resample_path(np.array(ring2.coords), count=num_points) + + if start is not None: + ring1_resampled = _reorder_linear_ring(ring1_resampled, start) + ring2_resampled = _reorder_linear_ring(ring2_resampled, start) + + weights = np.linspace(0.0, 1.0, num_points).reshape((-1, 1)) + points = (ring1_resampled * (1.0 - weights)) + (ring2_resampled * weights) + result = LineString(points) + + return result.simplify(0.1, False) + + +def _check_and_prepare_tree_for_valid_spiral(tree): + """Check whether spiral fill is possible, and tweak if necessary. + + Takes a tree consisting of isocontours. If a parent has more than one child + we cannot create a spiral. However, to make the routine more robust, we + allow more than one child if only one of the children has own children. The + other children are removed in this routine then. If the routine returns true, + the tree will have been cleaned up from unwanted children. + + If even with these weaker constraints, a spiral is not possible, False is + returned. + """ + + def process_node(node): + children = set(tree[node]) + + if len(children) == 0: + return True + elif len(children) == 1: + child = children.pop() + return process_node(child) + else: + children_with_children = {child for child in children if tree[child]} + if len(children_with_children) > 1: + # Node has multiple children with children, so a perfect spiral is not possible. + # This False value will be returned all the way up the stack. + return False + elif len(children_with_children) == 1: + children_without_children = children - children_with_children + child = children_with_children.pop() + tree.remove_nodes_from(children_without_children) + return process_node(child) + else: + # None of the children has its own children, so we'll just take the longest. + longest = max(children, key=lambda child: tree[child]['val'].length) + shorter_children = children - {longest} + tree.remove_nodes_from(shorter_children) + return process_node(longest) + + return process_node('root') + + +def single_spiral(tree, stitch_length, starting_point): + """Fill a shape with a single spiral going from outside to center.""" + return _spiral_fill(tree, stitch_length, starting_point, _make_spiral) + + +def double_spiral(tree, stitch_length, starting_point): + """Fill a shape with a double spiral going from outside to center and back to outside. """ + return _spiral_fill(tree, stitch_length, starting_point, _make_fermat_spiral) + + +def _spiral_fill(tree, stitch_length, close_point, spiral_maker): + starting_point = close_point.coords[0] + + rings = _get_spiral_rings(tree) + path = spiral_maker(rings, stitch_length, starting_point) + path = [Stitch(*stitch) for stitch in path] + + return running_stitch(path, stitch_length) + + +def _get_spiral_rings(tree): + rings = [] + + node = 'root' + while True: + rings.append(tree.nodes[node].val) + + children = tree[node] + if len(children) == 0: + break + elif len(children) == 1: + node = list(children)[0] + else: + # We can only really fill a shape with a single spiral if each + # parent has only one child. We'll do our best though, because + # that is probably more helpful to the user than just refusing + # entirely. We'll pick the child that's closest to the center. + parent_center = rings[-1].centroid + node = min(children, key=lambda child: parent_center.distance(tree.nodes[child].val.centroid)) + + return rings + + +def _make_fermat_spiral(rings, stitch_length, starting_point): + forward = _make_spiral(rings[::2], stitch_length, starting_point) + back = _make_spiral(rings[1::2], stitch_length, starting_point) + back.reverse() + + return chain(forward, back) + + +def _make_spiral(rings, stitch_length, starting_point): + path = [] + + for ring1, ring2 in zip(rings[:-1], rings[1:]): + spiral_part = _interpolate_linear_rings(ring1, ring2, stitch_length, starting_point) + path.extend(spiral_part.coords) + + return path diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index 21e35d83..46352d4f 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -131,8 +131,6 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non # 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: @@ -159,15 +157,13 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non runs.reverse() runs = [tuple(reversed(run)) for run in runs] - rows.append(runs) + yield 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, skip_last): stitches = [] @@ -221,6 +217,7 @@ def pull_runs(rows, shape, row_spacing): # print >>sys.stderr, "\n".join(str(len(row)) for row in rows) + rows = list(rows) runs = [] count = 0 while (len(rows) > 0): diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py new file mode 100644 index 00000000..e4918e1d --- /dev/null +++ b/lib/stitches/guided_fill.py @@ -0,0 +1,183 @@ +from shapely import geometry as shgeo +from shapely.ops import linemerge, unary_union + +from .auto_fill import (build_fill_stitch_graph, + build_travel_graph, collapse_sequential_outline_edges, fallback, + find_stitch_path, graph_is_valid, travel) +from .running_stitch import running_stitch +from ..i18n import _ +from ..stitch_plan import Stitch +from ..utils.geometry import Point as InkstitchPoint, reverse_line_string + + +def guided_fill(shape, + guideline, + angle, + row_spacing, + max_stitch_length, + running_stitch_length, + skip_last, + starting_point, + ending_point=None, + underpath=True): + try: + segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing) + fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point) + except ValueError: + # Small shapes will cause the graph to fail - min() arg is an empty sequence through insert node + return fallback(shape, running_stitch_length) + + if not graph_is_valid(fill_stitch_graph, shape, max_stitch_length): + return fallback(shape, running_stitch_length) + + travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath) + path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point) + result = path_to_stitches(path, travel_graph, fill_stitch_graph, max_stitch_length, running_stitch_length, skip_last) + + return result + + +def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, running_stitch_length, skip_last): + path = collapse_sequential_outline_edges(path) + + stitches = [] + + # If the very first stitch is travel, we'll omit it in travel(), so add it here. + if not path[0].is_segment(): + stitches.append(Stitch(*path[0].nodes[0])) + + for edge in path: + if edge.is_segment(): + current_edge = fill_stitch_graph[edge[0]][edge[-1]]['segment'] + path_geometry = current_edge['geometry'] + + if edge[0] != path_geometry.coords[0]: + path_geometry = reverse_line_string(path_geometry) + + point_list = [Stitch(*point) for point in path_geometry.coords] + new_stitches = running_stitch(point_list, stitch_length) + + # need to tag stitches + + if skip_last: + del new_stitches[-1] + + stitches.extend(new_stitches) + + travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', [])) + else: + stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last)) + + return stitches + + +def extend_line(line, minx, maxx, miny, maxy): + line = line.simplify(0.01, False) + + upper_left = InkstitchPoint(minx, miny) + lower_right = InkstitchPoint(maxx, maxy) + length = (upper_left - lower_right).length() + + point1 = InkstitchPoint(*line.coords[0]) + point2 = InkstitchPoint(*line.coords[1]) + new_starting_point = point1 - (point2 - point1).unit() * length + + point3 = InkstitchPoint(*line.coords[-2]) + point4 = InkstitchPoint(*line.coords[-1]) + new_ending_point = point4 + (point4 - point3).unit() * length + + return shgeo.LineString([new_starting_point.as_tuple()] + + line.coords[1:-1] + [new_ending_point.as_tuple()]) + + +def repair_multiple_parallel_offset_curves(multi_line): + lines = linemerge(multi_line) + lines = list(lines.geoms) + max_length = -1 + max_length_idx = -1 + for idx, subline in enumerate(lines): + if subline.length > max_length: + max_length = subline.length + max_length_idx = idx + # need simplify to avoid doubled points caused by linemerge + return lines[max_length_idx].simplify(0.01, False) + + +def repair_non_simple_lines(line): + repaired = unary_union(line) + counter = 0 + # Do several iterations since we might have several concatenated selfcrossings + while repaired.geom_type != 'LineString' and counter < 4: + line_segments = [] + for line_seg in repaired.geoms: + if not line_seg.is_ring: + line_segments.append(line_seg) + + repaired = unary_union(linemerge(line_segments)) + counter += 1 + if repaired.geom_type != 'LineString': + raise ValueError( + _("Guide line (or offset copy) is self crossing!")) + else: + return repaired + + +def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False): # noqa: C901 + + row_spacing = abs(row_spacing) + (minx, miny, maxx, maxy) = shape.bounds + upper_left = InkstitchPoint(minx, miny) + rows = [] + + if line.geom_type != 'LineString' or not line.is_simple: + line = repair_non_simple_lines(line) + # extend the line towards the ends to increase probability that all offsetted curves cross the shape + line = extend_line(line, minx, maxx, miny, maxy) + + line_offsetted = line + res = line_offsetted.intersection(shape) + while isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)) or (not res.is_empty and len(res.coords) > 1): + if isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)): + runs = [line_string.coords for line_string in res.geoms if ( + not line_string.is_empty and len(line_string.coords) > 1)] + else: + runs = [res.coords] + + runs.sort(key=lambda seg: ( + InkstitchPoint(*seg[0]) - upper_left).length()) + if flip: + runs.reverse() + runs = [tuple(reversed(run)) for run in runs] + + if row_spacing > 0: + rows.append(runs) + else: + rows.insert(0, runs) + + line_offsetted = line_offsetted.parallel_offset(row_spacing, 'left', 5) + if line_offsetted.geom_type == 'MultiLineString': # if we got multiple lines take the longest + line_offsetted = repair_multiple_parallel_offset_curves(line_offsetted) + if not line_offsetted.is_simple: + line_offsetted = repair_non_simple_lines(line_offsetted) + + if row_spacing < 0: + line_offsetted = reverse_line_string(line_offsetted) + line_offsetted = line_offsetted.simplify(0.01, False) + res = line_offsetted.intersection(shape) + if row_spacing > 0 and not isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)): + if (res.is_empty or len(res.coords) == 1): + row_spacing = -row_spacing + + line_offsetted = line.parallel_offset(row_spacing, 'left', 5) + if line_offsetted.geom_type == 'MultiLineString': # if we got multiple lines take the longest + line_offsetted = repair_multiple_parallel_offset_curves( + line_offsetted) + if not line_offsetted.is_simple: + line_offsetted = repair_non_simple_lines(line_offsetted) + # using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this + line_offsetted = reverse_line_string(line_offsetted) + line_offsetted = line_offsetted.simplify(0.01, False) + res = line_offsetted.intersection(shape) + + for row in rows: + yield from row diff --git a/lib/stitches/running_stitch.py b/lib/stitches/running_stitch.py index 2878480c..cb8acf68 100644 --- a/lib/stitches/running_stitch.py +++ b/lib/stitches/running_stitch.py @@ -3,11 +3,15 @@ # Copyright (c) 2010 Authors # Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. +from ..debug import debug +import math from copy import copy +from shapely.geometry import LineString """ Utility functions to produce running stitches. """ +@debug.time def running_stitch(points, stitch_length): """Generate running stitch along a path. @@ -23,56 +27,50 @@ def running_stitch(points, stitch_length): if len(points) < 2: return [] + # simplify will remove as many points as possible while ensuring that the + # resulting path stays within 0.75 pixels (0.2mm) of the original path. + path = LineString(points) + simplified = path.simplify(0.75, preserve_topology=False) + + # save the points that simplify picked and make sure we stitch them + important_points = set(simplified.coords) + important_point_indices = [i for i, point in enumerate(points) if point.as_tuple() in important_points] + output = [] - segment_start = points[0] - last_segment_direction = None - - # This tracks the distance we've traveled along the current segment so - # far. Each time we make a stitch, we add the stitch_length to this - # value. If we fall off the end of the current segment, we carry over - # the remainder to the next segment. - distance = 0.0 - - for segment_end in points[1:]: - segment = segment_end - segment_start - segment_length = segment.length() - - if segment_length == 0: - continue - - segment_direction = segment.unit() - - # corner detection - if last_segment_direction: - cos_angle_between = segment_direction * last_segment_direction - - # This checks whether the corner is sharper than 45 degrees. - if cos_angle_between < 0.5: - # Only add the corner point if it's more than 0.1mm away to - # avoid a double-stitch. - if (segment_start - output[-1]).length() > 0.1: - # add a stitch at the corner - output.append(segment_start) - - # next stitch needs to be stitch_length along this segment - distance = stitch_length - - while distance < segment_length: - output.append(segment_start + distance * segment_direction) - distance += stitch_length - - # prepare for the next segment - segment_start = segment_end - last_segment_direction = segment_direction - distance -= segment_length - - # stitch a single point if the path has a length of zero - if not output: - output.append(segment_start) - - # stitch the last point unless we're already almost there - if (segment_start - output[-1]).length() > 0.1 or len(output) == 0: - output.append(segment_start) + for start, end in zip(important_point_indices[:-1], important_point_indices[1:]): + # consider sections of the original path, each one starting and ending + # with an important point + section = points[start:end + 1] + output.append(section[0]) + + # Now split each section up evenly into stitches, each with a length no + # greater than the specified stitch_length. + section_ls = LineString(section) + section_length = section_ls.length + if section_length > stitch_length: + # a fractional stitch needs to be rounded up, which will make all + # of the stitches shorter + num_stitches = math.ceil(section_length / stitch_length) + actual_stitch_length = section_length / num_stitches + + distance = actual_stitch_length + + segment_start = section[0] + for segment_end in section[1:]: + segment = segment_end - segment_start + segment_length = segment.length() + + if distance < segment_length: + segment_direction = segment.unit() + + while distance < segment_length: + output.append(segment_start + distance * segment_direction) + distance += actual_stitch_length + + distance -= segment_length + segment_start = segment_end + + output.append(points[-1]) return output diff --git a/lib/stitches/utils/autoroute.py b/lib/stitches/utils/autoroute.py new file mode 100644 index 00000000..5acb1400 --- /dev/null +++ b/lib/stitches/utils/autoroute.py @@ -0,0 +1,221 @@ +# Authors: see git history +# +# Copyright (c) 2010 Authors +# Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. + +from itertools import combinations + +import networkx as nx +from shapely.geometry import Point, MultiPoint +from shapely.ops import nearest_points + +import inkex + +from ...svg import get_correction_transform +from ...svg.tags import INKSCAPE_LABEL + + +def find_path(graph, starting_node, ending_node): + """Find a path through the graph that sews every edge.""" + + # This is done in two steps. First, we find the shortest path from the + # start to the end. We remove it from the graph, and proceed to step 2. + # + # Then, we traverse the path node by node. At each node, we follow any + # branchings with a depth-first search. We travel down each branch of + # the tree, inserting each seen branch into the tree. When the DFS + # hits a dead-end, as it back-tracks, we also add the seen edges _again_. + # Repeat until there are no more edges left in the graph. + # + # Visiting the edges again on the way back allows us to set up + # "underpathing". + path = nx.shortest_path(graph, starting_node, ending_node) + + # Copy the graph so that we can remove the edges as we visit them. + # This also converts the directed graph into an undirected graph in the + # case that "preserve_order" is set. + graph = nx.Graph(graph) + graph.remove_edges_from(list(zip(path[:-1], path[1:]))) + + final_path = [] + prev = None + for node in path: + if prev is not None: + final_path.append((prev, node)) + prev = node + + for n1, n2, edge_type in list(nx.dfs_labeled_edges(graph, node)): + if n1 == n2: + # dfs_labeled_edges gives us (start, start, "forward") for + # the starting node for some reason + continue + + if edge_type == "forward": + final_path.append((n1, n2)) + graph.remove_edge(n1, n2) + elif edge_type == "reverse": + final_path.append((n2, n1)) + elif edge_type == "nontree": + # a "nontree" happens when there exists an edge from n1 to n2 + # but n2 has already been visited. It's a dead-end that runs + # into part of the graph that we've already traversed. We + # do still need to make sure that edge is sewn, so we travel + # down and back on this edge. + # + # It's possible for a given "nontree" edge to be listed more + # than once so we'll deduplicate. + if (n1, n2) in graph.edges: + final_path.append((n1, n2)) + final_path.append((n2, n1)) + graph.remove_edge(n1, n2) + + return final_path + + +def add_jumps(graph, elements, preserve_order): + """Add jump stitches between elements as necessary. + + Jump stitches are added to ensure that all elements can be reached. Only the + minimal number and length of jumps necessary will be added. + """ + + if preserve_order: + # For each sequential pair of elements, find the shortest possible jump + # stitch between them and add it. The directions of these new edges + # will enforce stitching the elements in order. + + for element1, element2 in zip(elements[:-1], elements[1:]): + potential_edges = [] + + nodes1 = get_nodes_on_element(graph, element1) + nodes2 = get_nodes_on_element(graph, element2) + + for node1 in nodes1: + for node2 in nodes2: + point1 = graph.nodes[node1]['point'] + point2 = graph.nodes[node2]['point'] + potential_edges.append((point1, point2)) + + if potential_edges: + edge = min(potential_edges, key=lambda p1_p2: p1_p2[0].distance(p1_p2[1])) + graph.add_edge(str(edge[0]), str(edge[1]), jump=True) + else: + # networkx makes this super-easy! k_edge_agumentation tells us what edges + # we need to add to ensure that the graph is fully connected. We give it a + # set of possible edges that it can consider adding (avail). Each edge has + # a weight, which we'll set as the length of the jump stitch. The + # algorithm will minimize the total length of jump stitches added. + for jump in nx.k_edge_augmentation(graph, 1, avail=list(possible_jumps(graph))): + graph.add_edge(*jump, jump=True) + + return graph + + +def possible_jumps(graph): + """All possible jump stitches in the graph with their lengths. + + Returns: a generator of tuples: (node1, node2, length) + """ + + for component1, component2 in combinations(nx.connected_components(graph), 2): + points1 = MultiPoint([graph.nodes[node]['point'] for node in component1]) + points2 = MultiPoint([graph.nodes[node]['point'] for node in component2]) + + start_point, end_point = nearest_points(points1, points2) + + yield (str(start_point), str(end_point), start_point.distance(end_point)) + + +def get_starting_and_ending_nodes(graph, elements, preserve_order, starting_point, ending_point): + """Find or choose the starting and ending graph nodes. + + If points were passed, we'll find the nearest graph nodes. Since we split + every path up into 1mm-chunks, we'll be at most 1mm away which is good + enough. + + If we weren't given starting and ending points, we'll pic kthe far left and + right nodes. + + returns: + (starting graph node, ending graph node) + """ + + nodes = [] + + nodes.append(find_node(graph, starting_point, + min, preserve_order, elements[0])) + nodes.append(find_node(graph, ending_point, + max, preserve_order, elements[-1])) + + return nodes + + +def find_node(graph, point, extreme_function, constrain_to_satin=False, satin=None): + if constrain_to_satin: + nodes = get_nodes_on_element(graph, satin) + else: + nodes = graph.nodes() + + if point is None: + return extreme_function(nodes, key=lambda node: graph.nodes[node]['point'].x) + else: + point = Point(*point) + return min(nodes, key=lambda node: graph.nodes[node]['point'].distance(point)) + + +def get_nodes_on_element(graph, element): + nodes = set() + + for start_node, end_node, element_for_edge in graph.edges(data='element'): + if element_for_edge is element: + nodes.add(start_node) + nodes.add(end_node) + + return nodes + + +def remove_original_elements(elements): + for element in elements: + for command in element.commands: + command_group = command.use.getparent() + if command_group is not None and command_group.get('id').startswith('command_group'): + remove_from_parent(command_group) + else: + remove_from_parent(command.connector) + remove_from_parent(command.use) + remove_from_parent(element.node) + + +def remove_from_parent(node): + if node.getparent() is not None: + node.getparent().remove(node) + + +def create_new_group(parent, insert_index, label): + group = inkex.Group(attrib={ + INKSCAPE_LABEL: label, + "transform": get_correction_transform(parent, child=True) + }) + parent.insert(insert_index, group) + + return group + + +def preserve_original_groups(elements, original_parent_nodes): + """Ensure that all elements are contained in the original SVG group elements. + + When preserve_order is True, no elements will be reordered in the XML tree. + This makes it possible to preserve original SVG group membership. We'll + ensure that each newly-created element is added to the group that contained + the original element that spawned it. + """ + + for element, parent in zip(elements, original_parent_nodes): + if parent is not None: + parent.append(element.node) + element.node.set('transform', get_correction_transform(parent, child=True)) + + +def add_elements_to_group(elements, group): + for element in elements: + group.append(element.node) |