diff options
| -rw-r--r-- | lib/elements/fill_stitch.py | 51 | ||||
| -rw-r--r-- | lib/stitches/guided_fill.py | 16 | ||||
| -rw-r--r-- | lib/stitches/tangential_fill.py | 538 | ||||
| -rw-r--r-- | lib/stitches/tangential_fill_stitch_line_creator.py | 279 | ||||
| -rw-r--r-- | lib/stitches/tangential_fill_stitch_pattern_creator.py | 339 | ||||
| -rw-r--r-- | requirements.txt | 1 |
6 files changed, 574 insertions, 650 deletions
diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index 5e795f45..d7b859b5 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -15,10 +15,9 @@ from shapely.validation import explain_validity from ..i18n import _ from ..marker import get_marker_elements from ..stitch_plan import StitchGroup -from ..stitches import tangential_fill_stitch_line_creator, auto_fill, legacy_fill, guided_fill +from ..stitches import tangential_fill, auto_fill, legacy_fill, guided_fill from ..svg import PIXELS_PER_MM from ..svg.tags import INKSCAPE_LABEL -from ..utils import Point as InkstitchPoint from ..utils import cache, version from .element import EmbroideryElement, param from .validation import ValidationError, ValidationWarning @@ -571,26 +570,40 @@ class FillStitch(EmbroideryElement): return [stitch_group] def do_tangential_fill(self, last_patch, starting_point): - stitch_groups = [] - polygons = self.fill_shape.geoms if not starting_point: starting_point = (0, 0) - for poly in polygons: - connected_line = tangential_fill_stitch_line_creator.tangential_fill( - poly, - self.tangential_strategy, - self.row_spacing, - self.max_stitch_length, - self.join_style + 1, - self.clockwise, - shgeo.Point(starting_point), - self.avoid_self_crossing, - ) - path = [InkstitchPoint(*p) for p in connected_line] + starting_point = shgeo.Point(starting_point) + + stitch_groups = [] + for polygon in self.fill_shape.geoms: + tree = tangential_fill.offset_polygon(polygon, self.row_spacing, self.join_style + 1, self.clockwise) + + stitches = [] + if self.tangential_strategy == 0: + stitches = tangential_fill.inner_to_outer( + tree, + self.row_spacing, + self.max_stitch_length, + starting_point, + self.avoid_self_crossing + ) + elif self.tangential_strategy == 1: + stitches = tangential_fill.single_spiral( + tree, + self.max_stitch_length, + starting_point + ) + elif self.tangential_strategy == 2: + stitches = tangential_fill.double_spiral( + tree, + self.max_stitch_length, + starting_point + ) + stitch_group = StitchGroup( color=self.color, tags=("auto_fill", "auto_fill_top"), - stitches=path) + stitches=stitches) stitch_groups.append(stitch_group) return stitch_groups @@ -611,13 +624,11 @@ class FillStitch(EmbroideryElement): self.angle, self.row_spacing, self.max_stitch_length, - min(self.min_stitch_length, self.max_stitch_length), self.running_stitch_length, self.skip_last, starting_point, ending_point, - self.underpath, - self.interlaced)) + self.underpath)) return [stitch_group] @cache diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py index 40728c53..9694a546 100644 --- a/lib/stitches/guided_fill.py +++ b/lib/stitches/guided_fill.py @@ -11,19 +11,16 @@ 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): + 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) @@ -36,15 +33,12 @@ def guided_fill(shape, 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) + result = path_to_stitches(path, travel_graph, fill_stitch_graph, max_stitch_length, running_stitch_length, skip_last) return result -@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): +def path_to_stitches(path, travel_graph, fill_stitch_graph, stitch_length, running_stitch_length, skip_last): path = collapse_sequential_outline_edges(path) stitches = [] @@ -62,7 +56,7 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, path_geometry = reverse_line_string(path_geometry) point_list = [Stitch(*point) for point in path_geometry.coords] - new_stitches = running_stitch(point_list, max_stitch_length) + new_stitches = running_stitch(point_list, stitch_length) # need to tag stitches @@ -124,7 +118,7 @@ def repair_non_simple_lines(line): counter += 1 if repaired.geom_type != 'LineString': raise ValueError( - _("Guide line (or offsetted instance) is self crossing!")) + _("Guide line (or offset copy) is self crossing!")) else: return repaired diff --git a/lib/stitches/tangential_fill.py b/lib/stitches/tangential_fill.py new file mode 100644 index 00000000..3cc3335f --- /dev/null +++ b/lib/stitches/tangential_fill.py @@ -0,0 +1,538 @@ +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, MultiLineString, 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 ..i18n import _ +from ..stitch_plan import Stitch +from ..stitches import constants +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(constants.simplification_threshold, 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 + + polygon = polygon.simplify(constants.simplification_threshold, False) + 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: + if isinstance(portion_within_threshold, MultiLineString): + portion_within_threshold = portion_within_threshold.geoms[0] + + parent_point = Point(portion_within_threshold.coords[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], + constants.offset_factor_for_adjacent_geometry * offset, + 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 ring gives a nicer visual appearance. + # current_ring = reverse_line_string(current_ring) + pass + 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) + + # TODO: remove when rastering is cheaper + return result.simplify(constants.simplification_threshold, 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): + if not _check_and_prepare_tree_for_valid_spiral(tree): + raise ValueError(_("Shape cannot be filled with single or double spiral!")) + + starting_point = close_point.coords[0] + rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')] + path = spiral_maker(rings, stitch_length, starting_point) + path = [Stitch(*stitch) for stitch in path] + + return running_stitch(path, stitch_length) + + +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/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py deleted file mode 100644 index 1c10c397..00000000 --- a/lib/stitches/tangential_fill_stitch_line_creator.py +++ /dev/null @@ -1,279 +0,0 @@ -from enum import IntEnum - -import networkx as nx -from shapely.geometry import Polygon, MultiPolygon, GeometryCollection -from shapely.geometry.polygon import orient -from shapely.ops import polygonize - -from .running_stitch import running_stitch -from ..stitch_plan import Stitch -from ..stitches import constants -from ..stitches import tangential_fill_stitch_pattern_creator -from ..utils import DotDict -from ..utils.geometry import reverse_line_string, 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 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(constants.simplification_threshold, 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 - (meaning a ring which 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 make_tree_uniform(tree, clockwise=True): - """ - Since naturally holes have the opposite point ordering than non-holes we - make all lines within the tree "root" uniform (having all the same - ordering direction) - """ - - for node in tree.nodes.values(): - node.val = orient_linear_ring(node.val, clockwise) - - -# Used to define which stitching strategy shall be used -class StitchingStrategy(IntEnum): - INNER_TO_OUTER = 0 - SINGLE_SPIRAL = 1 - DOUBLE_SPIRAL = 2 - - -def check_and_prepare_tree_for_valid_spiral(tree): - """ - Takes a tree consisting of offsetted curves. 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 childs has own childs. The other childs are removed in this - routine then. If the routine returns true, the tree will have been cleaned up from unwanted - childs. If the routine returns false even under the mentioned weaker conditions the - tree cannot be connected by one spiral. - """ - - 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 offset_poly(poly, offset, join_style, clockwise): - """ - Takes a polygon (which can have holes) as input and creates offsetted - versions until the polygon is filled with these smaller offsets. - These created geometries are afterwards connected to each other and - resampled with a maximum stitch_distance. - The return value is a LineString which should cover the full polygon. - Input: - -poly: The shapely polygon which can have holes - -offset: The used offset for the curves - -join_style: Join style for the offset - can be round, mitered or bevel - (https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE) - For examples look at - https://shapely.readthedocs.io/en/stable/_images/parallel_offset.png - -stitch_distance maximum allowed stitch distance between two points - -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting - offsetted paths might be shorter. - -offset_by_half: True if the points shall be interlaced - -strategy: According to StitchingStrategy enum class you can select between - different strategies for the connection between parent and childs. In - addition it offers the option "SPIRAL" which creates a real spiral towards inner. - In contrast to the other two options, "SPIRAL" does not end at the starting point - but at the innermost point - -starting_point: Defines the starting point for the stitching - -avoid_self_crossing: don't let the path cross itself when using the Inner to Outer strategy - Output: - -List of point coordinate tuples - -Tag (origin) of each point to analyze why a point was placed - at this position - """ - - ordered_poly = orient(poly, -1) - tree = Tree() - tree.add_node('root', type='node', parent=None, val=ordered_poly.exterior) - active_polys = ['root'] - active_holes = [[]] - - # We don't care about the names of the nodes, we just need them to be unique. - node_num = 0 - - for hole in ordered_poly.interiors: - tree.add_node(node_num, type="hole", val=hole) - active_holes[0].append(node_num) - node_num += 1 - - while len(active_polys) > 0: - current_poly = active_polys.pop() - current_holes = active_holes.pop() - outer, inners = offset_polygon_and_holes(tree, current_poly, current_holes, offset, join_style) - - if not outer.is_empty: - polygons = match_polygons_and_holes(outer, inners) - - if not polygons.is_empty: - 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: - active_polys.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) - - make_tree_uniform(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)) - 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 - - polygon = polygon.simplify(constants.simplification_threshold, False) - valid_rings = take_only_valid_linear_rings(polygon.exterior) - - try: - exterior = valid_rings.geoms[0] - except IndexError: - return None, None - - node = id(polygon) # just needs to be unique - - tree.add_node(node, type='node', parent=parent_polygon, val=exterior) - tree.add_edge(parent_polygon, node) - - hole_node_list = [] - for hole in polygon.interiors: - hole_node = id(hole) - 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_node_list.append(hole_node) - - return node, hole_node_list - - -def tangential_fill(poly, strategy, offset, stitch_distance, join_style, clockwise, starting_point, avoid_self_crossing): - if strategy in (StitchingStrategy.SINGLE_SPIRAL, StitchingStrategy.DOUBLE_SPIRAL) and len(poly.interiors) > 1: - raise ValueError( - "Single spiral geometry must not have more than one hole!") - - tree = offset_poly(poly, offset, join_style, clockwise) - - if strategy == StitchingStrategy.INNER_TO_OUTER: - connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_from_inner_to_outer( - tree, 'root', offset, stitch_distance, starting_point, avoid_self_crossing) - path = [Stitch(*point) for point in connected_line.coords] - return running_stitch(path, stitch_distance) - elif strategy == StitchingStrategy.SINGLE_SPIRAL: - if not check_and_prepare_tree_for_valid_spiral(tree): - raise ValueError("Geometry cannot be filled with one spiral!") - connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_single_spiral( - tree, offset, stitch_distance, starting_point) - elif strategy == StitchingStrategy.DOUBLE_SPIRAL: - if not check_and_prepare_tree_for_valid_spiral(tree): - raise ValueError("Geometry cannot be filled with a double spiral!") - connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_double_spiral( - tree, offset, stitch_distance, starting_point) - else: - raise ValueError("Invalid stitching stratety!") - - return connected_line diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py deleted file mode 100644 index a19c0a0a..00000000 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ /dev/null @@ -1,339 +0,0 @@ -from collections import namedtuple -from itertools import chain -import networkx as nx -import numpy as np -import trimesh -from shapely.geometry import Point, LineString, LinearRing, MultiLineString -from shapely.ops import nearest_points - -from .running_stitch import running_stitch - -from ..debug import debug -from ..stitches import constants -from ..stitch_plan import Stitch -from ..utils.geometry import cut, roll_linear_ring, reverse_line_string - -nearest_neighbor_tuple = namedtuple( - "nearest_neighbor_tuple", - [ - "nearest_point_parent", - "nearest_point_child", - "proj_distance_parent", - "child_node", - ], -) - - -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 - - Output: - -tuple or None - - the tuple structure is: - (nearest point in travel_line, nearest 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: - if isinstance(portion_within_threshold, MultiLineString): - portion_within_threshold = portion_within_threshold.geoms[0] - - parent_point = Point(portion_within_threshold.coords[0]) - return nearest_points(parent_point, next_line) - - -def create_nearest_points_list( - travel_line, tree, children_list, threshold, threshold_hard): - """ - Takes a line and calculates the nearest distance along this line to - enter the childs in children_list - The method calculates the distances along the line and along the - reversed line to find the best direction which minimizes the overall - distance for all childs. - Input: - -travel_line: The "parent" line for which the distance should - be minimized to enter the childs - -children_list: contains the childs of travel_line which need to be entered - -threshold: The distance between travel_line and a child needs to be - below threshold to be a valid point for entering - -preferred_direction: Put a bias on the desired travel direction along - travel_line. If equals zero no bias is applied. - preferred_direction=1 means we prefer the direction of travel_line; - preferred_direction=-1 means we prefer the opposite direction. - Output: - -stitching direction for travel_line - -list of tuples (one tuple per child). The tuple structure is: - ((nearest point in travel_line, nearest point in child), - distance along travel_line, belonging child) - """ - - children_nearest_points = [] - - for child in children_list: - 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 connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, starting_point, - avoid_self_crossing, forward=True): - """ - Takes the offset curves organized as a tree, connects and samples them. - 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. - Input: - -tree: contains the offsetted curves in a hierachical organized - data structure. - -used_offset: used offset when the offsetted curves were generated - -stitch_distance: maximum allowed distance between two points - after sampling - -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting - offsetted paths might be shorter. - -close_point: defines the beginning point for stitching - (stitching starts always from the undisplaced curve) - -offset_by_half: If true the resulting points are interlaced otherwise not. - Returnvalues: - -All offsetted curves connected to one line and sampled with points obeying - stitch_distance and offset_by_half - -Tag (origin) of each point to analyze why a point was placed - at this position - """ - - 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], - constants.offset_factor_for_adjacent_geometry * offset, - 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 ring gives a nicer visual appearance. - # current_ring = reverse_line_string(current_ring) - pass - 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 = connect_raster_tree_from_inner_to_outer( - tree, - child_connection.child_node, - offset, - stitch_distance, - 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 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) - - # TODO: remove when rastering is cheaper - return result.simplify(constants.simplification_threshold, False) - - -def connect_raster_tree_single_spiral(tree, used_offset, stitch_distance, close_point): # noqa: C901 - """ - Takes the offsetted curves organized as tree, connects and samples them as a spiral. - It expects that each node in the tree has max. one child - Input: - -tree: contains the offsetted curves in a hierarchical organized - data structure. - -used_offset: used offset when the offsetted curves were generated - -stitch_distance: maximum allowed distance between two points - after sampling - -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting - offsetted paths might be shorter. - -close_point: defines the beginning point for stitching - (stitching starts always from the undisplaced curve) - -offset_by_half: If true the resulting points are interlaced otherwise not. - Return values: - -All offsetted curves connected to one spiral and sampled with - points obeying stitch_distance and offset_by_half - -Tag (origin) of each point to analyze why a point was - placed at this position - """ - - starting_point = close_point.coords[0] - - rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')] - - path = make_spiral(rings, stitch_distance, starting_point) - path = [Stitch(*stitch) for stitch in path] - - return running_stitch(path, stitch_distance) - - -def connect_raster_tree_double_spiral(tree, used_offset, stitch_distance, close_point): # noqa: C901 - """ - Takes the offsetted curves organized as tree, connects and samples them as a spiral. - It expects that each node in the tree has max. one child - Input: - -tree: contains the offsetted curves in a hierarchical organized - data structure. - -used_offset: used offset when the offsetted curves were generated - -stitch_distance: maximum allowed distance between two points - after sampling - -min_stitch_distance stitches within a row shall be at least min_stitch_distance apart. Stitches connecting - offsetted paths might be shorter. - -close_point: defines the beginning point for stitching - (stitching starts always from the undisplaced curve) - -offset_by_half: If true the resulting points are interlaced otherwise not. - Return values: - -All offsetted curves connected to one spiral and sampled with - points obeying stitch_distance and offset_by_half - -Tag (origin) of each point to analyze why a point was - placed at this position - """ - - starting_point = close_point.coords[0] - - rings = [tree.nodes[node].val for node in nx.dfs_preorder_nodes(tree, 'root')] - - path = make_fermat_spiral(rings, stitch_distance, starting_point) - path = [Stitch(*stitch) for stitch in path] - - return running_stitch(path, stitch_distance) - - -def make_fermat_spiral(rings, stitch_distance, starting_point): - forward = make_spiral(rings[::2], stitch_distance, starting_point) - back = make_spiral(rings[1::2], stitch_distance, starting_point) - back.reverse() - - return chain(forward, back) - - -def make_spiral(rings, stitch_distance, starting_point): - path = [] - - for ring1, ring2 in zip(rings[:-1], rings[1:]): - spiral_part = interpolate_linear_rings(ring1, ring2, stitch_distance, starting_point) - path.extend(spiral_part.coords) - - return path diff --git a/requirements.txt b/requirements.txt index 585b1dac..e0b07b0b 100644 --- a/requirements.txt +++ b/requirements.txt @@ -19,7 +19,6 @@ stringcase tinycss2 flask fonttools -depq trimesh scipy==1.7.3 |