import networkx from depq import DEPQ from shapely.geometry import GeometryCollection, LineString, MultiLineString from shapely.ops import linemerge, unary_union from .auto_fill import (add_edges_between_outline_nodes, build_travel_graph, collapse_sequential_outline_edges, fallback, find_stitch_path, graph_is_valid, insert_node, tag_nodes_with_outline_and_projection, travel) from .point_transfer import transfer_points_to_surrounding_graph from .sample_linestring import raster_line_string_with_priority_points from ..debug import debug from ..i18n import _ from ..stitch_plan import Stitch from ..utils.geometry import Point as InkstitchPoint, reverse_line_string @debug.time def guided_fill(shape, guideline, angle, row_spacing, max_stitch_length, min_stitch_length, running_stitch_length, skip_last, starting_point, ending_point=None, underpath=True, offset_by_half=True): fill_stitch_graph = [] try: fill_stitch_graph = build_guided_fill_stitch_graph( shape, guideline, row_spacing, 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, angle, row_spacing, max_stitch_length, min_stitch_length, running_stitch_length, skip_last, offset_by_half) return result @debug.time def build_guided_fill_stitch_graph(shape, guideline, row_spacing, 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 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. """ debug.add_layer("auto-fill fill stitch") rows_of_segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing) # segments = [segment for row in rows_of_segments for segment in row] graph = networkx.MultiGraph() for i in range(len(rows_of_segments)): for segment in rows_of_segments[i]: # First, add the grating segments as edges. We'll use the coordinates # of the endpoints as nodes, which networkx will add automatically. # 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=[]) previous_neighbors = [(seg[0], seg[-1]) for seg in rows_of_segments[i-1] if i > 0] next_neighbors = [(seg[0], seg[-1]) for seg in rows_of_segments[(i+1) % len(rows_of_segments)] if i < len(rows_of_segments)-1] graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[], geometry=LineString(segment), previous_neighbors=previous_neighbors, next_neighbors=next_neighbors, projected_points=DEPQ(iterable=None, maxlen=None), already_rastered=False) tag_nodes_with_outline_and_projection(graph, shape, graph.nodes()) add_edges_between_outline_nodes(graph, duplicate_every_other=True) if starting_point: insert_node(graph, shape, starting_point) if ending_point: insert_node(graph, shape, ending_point) debug.log_graph(graph, "graph") return graph def stitch_line(stitches, stitching_direction, geometry, projected_points, max_stitch_length, min_stitch_length, row_spacing, skip_last, offset_by_half): if stitching_direction == 1: stitched_line, _ = raster_line_string_with_priority_points( geometry, 0.0, geometry.length, max_stitch_length, min_stitch_length, projected_points, abs(row_spacing), offset_by_half, True) else: stitched_line, _ = raster_line_string_with_priority_points( geometry, geometry.length, 0.0, max_stitch_length, min_stitch_length, projected_points, abs(row_spacing), offset_by_half, True) stitches.append(Stitch(*stitched_line[0], tags=('fill_row_start',))) for i in range(1, len(stitched_line) - 1): stitches.append(Stitch(*stitched_line[i], tags=('fill_row'))) if not skip_last: if stitching_direction == 1: stitches.append( Stitch(*geometry.coords[-1], tags=('fill_row_end',))) else: stitches.append( Stitch(*geometry.coords[0], tags=('fill_row_end',))) @debug.time def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, min_stitch_length, running_stitch_length, skip_last, offset_by_half): 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(): new_stitches = [] current_edge = fill_stitch_graph[edge[0]][edge[-1]]['segment'] path_geometry = current_edge['geometry'] projected_points = current_edge['projected_points'] stitching_direction = 1 if (abs(edge[0][0]-path_geometry.coords[0][0])+abs(edge[0][1]-path_geometry.coords[0][1]) > abs(edge[0][0]-path_geometry.coords[-1][0])+abs(edge[0][1]-path_geometry.coords[-1][1])): stitching_direction = -1 stitch_line(new_stitches, stitching_direction, path_geometry, projected_points, max_stitch_length, min_stitch_length, row_spacing, skip_last, offset_by_half) current_edge['already_rastered'] = True transfer_points_to_surrounding_graph( fill_stitch_graph, current_edge, row_spacing, False, new_stitches, overnext_neighbor=True) transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, row_spacing, offset_by_half, new_stitches, overnext_neighbor=False, transfer_forbidden_points=offset_by_half) stitches.extend(new_stitches) 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 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 offsetted instance) 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, (GeometryCollection, MultiLineString)) or (not res.is_empty and len(res.coords) > 1): if isinstance(res, (GeometryCollection, 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, (GeometryCollection, 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) return rows