diff options
Diffstat (limited to 'lib/stitches')
| -rw-r--r-- | lib/stitches/auto_run.py | 5 | ||||
| -rw-r--r-- | lib/stitches/utils/autoroute.py | 88 |
2 files changed, 60 insertions, 33 deletions
diff --git a/lib/stitches/auto_run.py b/lib/stitches/auto_run.py index d833a885..b8ab84c7 100644 --- a/lib/stitches/auto_run.py +++ b/lib/stitches/auto_run.py @@ -5,23 +5,22 @@ from collections import defaultdict +import inkex 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.threading import check_stop_flag 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) -from ..utils.threading import check_stop_flag class LineSegments: diff --git a/lib/stitches/utils/autoroute.py b/lib/stitches/utils/autoroute.py index 3ada4299..b1538cfd 100644 --- a/lib/stitches/utils/autoroute.py +++ b/lib/stitches/utils/autoroute.py @@ -83,40 +83,68 @@ def add_jumps(graph, elements, preserve_order): 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:]): - check_stop_flag() - - potential_edges = [] - - nodes1 = get_nodes_on_element(graph, element1) - nodes2 = get_nodes_on_element(graph, element2) + _add_ordered_jumps(graph, elements) + else: + _add_unordered_jumps(graph, elements) + return graph - 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))): - check_stop_flag() - graph.add_edge(*jump, jump=True) +def _add_ordered_jumps(graph, elements): + # 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:]): + check_stop_flag() + _insert_smallest_jump(graph, element1, element2) - return graph + # add jumps between subpath too, we do not care about directions here + for element in elements: + check_stop_flag() + geoms = list(element.as_multi_line_string().geoms) + i = 0 + for line1 in geoms: + for line2 in geoms[i+1:]: + if line1.distance(line2) == 0: + continue + node1, node2 = nearest_points(line1, line2) + _insert_jump(graph, node1, node2) + i += 1 + + +def _insert_smallest_jump(graph, element1, element2): + 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) + + +def _insert_jump(graph, node1, node2): + graph.add_node(str(node1), point=node1) + graph.add_node(str(node2), point=node2) + graph.add_edge(str(node1), str(node2), jump=True) + graph.add_edge(str(node2), str(node1), jump=True) + + +def _add_unordered_jumps(graph, elements): + # 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))): + check_stop_flag() + graph.add_edge(*jump, jump=True) def possible_jumps(graph): |