diff options
| -rw-r--r-- | lib/stitches/auto_fill.py | 137 | ||||
| -rw-r--r-- | lib/stitches/fill.py | 4 |
2 files changed, 59 insertions, 82 deletions
diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index c2e2e0bb..2e424267 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -1,14 +1,14 @@ -from collections import deque -from itertools import groupby, izip -import sys +from itertools import groupby, chain +import math import networkx from shapely import geometry as shgeo from ..exceptions import InkstitchException from ..i18n import _ +from ..svg import PIXELS_PER_MM from ..utils.geometry import Point as InkstitchPoint, cut -from .fill import intersect_region_with_grating, row_num, stitch_row +from .fill import intersect_region_with_grating, stitch_row from .running_stitch import running_stitch @@ -50,13 +50,16 @@ def auto_fill(shape, staggers, skip_last, starting_point, - ending_point=None): + ending_point=None, + underpath=True): graph = build_graph(shape, angle, row_spacing, end_row_spacing) check_graph(graph, shape, max_stitch_length) + travel_graph = build_travel_graph(graph, shape, angle, underpath) path = find_stitch_path(graph, starting_point, ending_point) + result = path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last) - return path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last) + return result def which_outline(shape, coords): @@ -156,6 +159,48 @@ def build_graph(shape, angle, row_spacing, end_row_spacing): return graph +def build_travel_graph(top_stitch_graph, shape, top_stitch_angle, underpath): + graph = networkx.Graph() + graph.add_nodes_from(top_stitch_graph.nodes(data=True)) + + if underpath: + # need to concatenate all the rows + grating1 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle + math.pi / 4, 2 * PIXELS_PER_MM)))) + grating2 = shgeo.MultiLineString(list(chain(*intersect_region_with_grating(shape, top_stitch_angle - math.pi / 4, 2 * PIXELS_PER_MM)))) + + endpoints = [coord for mls in (grating1, grating2) + for ls in mls + for coord in ls.coords] + + for node in endpoints: + 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] + + # add an edge between each successive node + for node1, node2 in zip(nodes, nodes[1:] + [nodes[0]]): + p1 = InkstitchPoint(*node1) + p2 = InkstitchPoint(*node2) + graph.add_edge(node1, node2, weight=3 * p1.distance(p2)) + + if underpath: + interior_edges = grating1.symmetric_difference(grating2) + for ls in interior_edges.geoms: + p1, p2 = [InkstitchPoint(*coord) for coord in ls.coords] + + graph.add_edge(p1.as_tuple(), p2.as_tuple(), weight=p1.distance(p2)) + + return graph + + def check_graph(graph, shape, max_stitch_length): if networkx.is_empty(graph) or not networkx.is_eulerian(graph): if shape.area < max_stitch_length ** 2: @@ -285,86 +330,18 @@ def collapse_sequential_outline_edges(path): return new_path -def connect_points(graph, shape, start, end, running_stitch_length, row_spacing): - """Create stitches to get from one point on an outline of the shape to another. - - An outline is essentially a loop (a path of points that ends where it starts). - Given point A and B on that loop, we want to take the shortest path from one - to the other. Due to the way our path-finding algorithm above works, it may - have had to take the long way around the shape to get from A to B, but we'd - rather ignore that and just get there the short way. - """ - - # We may be on the outer boundary or on on of the hole boundaries. - outline_index = graph.nodes[start]['index'] - outline = shape.boundary[outline_index] - - # First, figure out the start and end position along the outline. The - # projection gives us the distance travelled down the outline to get to - # that point. - start_projection = graph.nodes[start]['projection'] - start = shgeo.Point(start) - end_projection = graph.nodes[end]['projection'] - end = shgeo.Point(end) - - # If the points are pretty close, just jump there. There's a slight - # risk that we're going to sew outside the shape here. The way to - # avoid that is to use running_stitch() even for these really short - # connections, but that would be really slow for all of the - # connections from one row to the next. - # - # This seems to do a good job of avoiding going outside the shape in - # most cases. 1.4 is chosen as approximately the length of the - # stitch connecting two rows if the side of the shape is at a 45 - # degree angle to the rows of stitches (sqrt(2)). - direct_distance = abs(end_projection - start_projection) - if direct_distance < row_spacing * 1.4 and direct_distance < running_stitch_length: - return [InkstitchPoint(end.x, end.y)] - - # The outline path has a "natural" starting point. Think of this as - # 0 or 12 on an analog clock. - - # Cut the outline into two paths at the starting point. The first - # section will go from 12 o'clock to the starting point. The second - # section will go from the starting point all the way around and end - # up at 12 again. - result = cut(outline, start_projection) - - # result[0] will be None if our starting point happens to already be at - # 12 o'clock. - if result[0] is not None: - before, after = result - - # Make a new outline, starting from the starting point. This is - # like rotating the clock so that now our starting point is - # at 12 o'clock. - outline = shgeo.LineString(list(after.coords) + list(before.coords)) - - # Now figure out where our ending point is on the newly-rotated clock. - end_projection = outline.project(end) - - # Cut the new path at the ending point. before and after now represent - # two ways to get from the starting point to the ending point. One - # will most likely be longer than the other. - before, after = cut(outline, end_projection) - - if before.length <= after.length: - points = list(before.coords) - else: - # after goes from the ending point to the starting point, so reverse - # it to get from start to end. - points = list(reversed(after.coords)) +def travel(graph, travel_graph, shape, start, end, running_stitch_length, row_spacing): + """Create stitches to get from one point on an outline of the shape to another.""" - # Now do running stitch along the path we've found. running_stitch() will - # avoid cutting sharp corners. - path = [InkstitchPoint(*p) for p in points] + path = networkx.shortest_path(travel_graph, start, end, weight='weight') + path = [InkstitchPoint(*p) for p in path] stitches = running_stitch(path, running_stitch_length) # The row of stitches already stitched the first point, so skip it. return stitches[1:] -def path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last): +def path_to_stitches(path, graph, travel_graph, shape, angle, row_spacing, max_stitch_length, running_stitch_length, staggers, skip_last): path = collapse_sequential_outline_edges(path) stitches = [] @@ -373,6 +350,6 @@ def path_to_stitches(path, graph, shape, angle, row_spacing, max_stitch_length, if edge.is_segment(): stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last) else: - stitches.extend(connect_points(graph, shape, edge[0], edge[1], running_stitch_length, row_spacing)) + stitches.extend(travel(graph, travel_graph, shape, edge[0], edge[1], running_stitch_length, row_spacing)) return stitches diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index e00d66de..924f64f6 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -140,7 +140,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non res = grating_line.intersection(shape) if (isinstance(res, shapely.geometry.MultiLineString)): - runs = map(lambda line_string: line_string.coords, res.geoms) + runs = [line_string.coords for line_string in res.geoms] else: if res.is_empty or len(res.coords) == 1: # ignore if we intersected at a single point or no points @@ -153,7 +153,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non if flip: runs.reverse() - runs = map(lambda run: tuple(reversed(run)), runs) + runs = [tuple(reversed(run)) for run in runs] rows.append(runs) |