diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/elements/fill_stitch.py | 14 | ||||
| -rw-r--r-- | lib/stitches/auto_fill.py | 12 | ||||
| -rw-r--r-- | lib/stitches/tangential_fill_stitch_line_creator.py | 253 | ||||
| -rw-r--r-- | lib/stitches/tangential_fill_stitch_pattern_creator.py | 14 | ||||
| -rw-r--r-- | lib/utils/geometry.py | 31 |
5 files changed, 154 insertions, 170 deletions
diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index 70d4f356..5e795f45 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -576,19 +576,17 @@ class FillStitch(EmbroideryElement): if not starting_point: starting_point = (0, 0) for poly in polygons: - connectedLine, _ = tangential_fill_stitch_line_creator.offset_poly( + connected_line = tangential_fill_stitch_line_creator.tangential_fill( poly, - -self.row_spacing, - self.join_style + 1, - self.max_stitch_length, - min(self.min_stitch_length, self.max_stitch_length), - self.interlaced, self.tangential_strategy, + self.row_spacing, + self.max_stitch_length, + self.join_style + 1, + self.clockwise, shgeo.Point(starting_point), self.avoid_self_crossing, - self.clockwise ) - path = [InkstitchPoint(*p) for p in connectedLine] + path = [InkstitchPoint(*p) for p in connected_line] stitch_group = StitchGroup( color=self.color, tags=("auto_fill", "auto_fill_top"), diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 35412e93..630178c4 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 @@ -396,15 +395,6 @@ def travel_grating(shape, angle, row_spacing): return shgeo.MultiLineString(list(segments)) -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 - - def build_travel_edges(shape, fill_angle): r"""Given a graph, compute the interior travel edges. diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py index 69bb13f2..1c10c397 100644 --- a/lib/stitches/tangential_fill_stitch_line_creator.py +++ b/lib/stitches/tangential_fill_stitch_line_creator.py @@ -1,10 +1,7 @@ from enum import IntEnum import networkx as nx -from depq import DEPQ -from shapely.geometry import MultiLineString, Polygon -from shapely.geometry import MultiPolygon -from shapely.geometry.polygon import LinearRing +from shapely.geometry import Polygon, MultiPolygon, GeometryCollection from shapely.geometry.polygon import orient from shapely.ops import polygonize @@ -13,7 +10,7 @@ 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 +from ..utils.geometry import reverse_line_string, ensure_geometry_collection, ensure_multi_polygon class Tree(nx.DiGraph): @@ -23,15 +20,13 @@ class Tree(nx.DiGraph): 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 = Polygon(ring).buffer(-offset, resolution, cap_style=2, join_style=join_style, mitre_limit=mitre_limit, single_sided=True) + result = ensure_multi_polygon(result) - if result.geom_type == 'Polygon': - return result.exterior - else: - result_list = [] - for poly in result.geoms: - result_list.append(poly.exterior) - return MultiLineString(result_list) + 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): @@ -39,24 +34,14 @@ 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) """ - if rings.geom_type == "MultiLineString": - new_list = [] - for ring in rings.geoms: - if len(ring.coords) > 3 or (len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1]): - new_list.append(ring) - if len(new_list) == 1: - return LinearRing(new_list[0]) - else: - return MultiLineString(new_list) - elif rings.geom_type == "LineString" or rings.geom_type == "LinearRing": - if len(rings.coords) <= 2: - return LinearRing() - elif len(rings.coords) == 3 and rings.coords[0] == rings.coords[-1]: - return LinearRing() - else: - return rings - else: - return LinearRing() + + 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): @@ -127,8 +112,7 @@ def check_and_prepare_tree_for_valid_spiral(tree): return process_node('root') -def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, offset_by_half, strategy, starting_point, # noqa: C901 - avoid_self_crossing, clockwise): +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. @@ -159,21 +143,9 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, at this position """ - 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!") - ordered_poly = orient(poly, -1) - ordered_poly = ordered_poly.simplify( - constants.simplification_threshold, False) tree = Tree() - tree.add_node('root', - type='node', - parent=None, - val=ordered_poly.exterior, - already_rastered=False, - transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), - ) + tree.add_node('root', type='node', parent=None, val=ordered_poly.exterior) active_polys = ['root'] active_holes = [[]] @@ -181,103 +153,26 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, node_num = 0 for hole in ordered_poly.interiors: - tree.add_node(node_num, - type="hole", - val=hole, - already_rastered=False, - transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), - ) + 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() - poly_inners = [] + outer, inners = offset_polygon_and_holes(tree, current_poly, current_holes, offset, join_style) - outer = offset_linear_ring( - tree.nodes[current_poly].val, - offset, - resolution=5, - join_style=join_style, - mitre_limit=10, - ) - outer = outer.simplify(constants.simplification_threshold, False) - outer = take_only_valid_linear_rings(outer) - - for hole in current_holes: - inner = offset_linear_ring( - tree.nodes[hole].val, - -offset, # take negative offset for holes - resolution=5, - join_style=join_style, - mitre_limit=10, - ) - inner = inner.simplify(constants.simplification_threshold, False) - inner = take_only_valid_linear_rings(inner) - if not inner.is_empty: - poly_inners.append(Polygon(inner)) if not outer.is_empty: - if len(poly_inners) == 0: - if outer.geom_type == "LineString" or outer.geom_type == "LinearRing": - result = Polygon(outer) - else: - result = MultiPolygon(polygonize(outer)) - else: - if outer.geom_type == "LineString" or outer.geom_type == "LinearRing": - result = Polygon(outer).difference( - MultiPolygon(poly_inners)) - else: - result = MultiPolygon(polygonize(outer)).difference( - MultiPolygon(poly_inners)) - - if not result.is_empty and result.area > offset * offset / 10: - if result.geom_type == "Polygon": - result_list = [result] - else: - result_list = list(result.geoms) - - for polygon in result_list: - polygon = orient(polygon, -1) - - if polygon.area < offset * offset / 10: - continue - - polygon = polygon.simplify( - constants.simplification_threshold, False - ) - poly_coords = polygon.exterior - poly_coords = take_only_valid_linear_rings(poly_coords) - if poly_coords.is_empty: - continue - - node = node_num - node_num += 1 - tree.add_node(node, - type='node', - parent=current_poly, - val=poly_coords, - already_rastered=False, - transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), - ) - tree.add_edge(current_poly, node) - active_polys.append(node) - hole_node_list = [] - for hole in polygon.interiors: - hole_node = node_num - node_num += 1 - tree.add_node(hole_node, - type="hole", - val=hole, - already_rastered=False, - transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), - ) - for previous_hole in current_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) - active_holes.append(hole_node_list) + 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 @@ -289,22 +184,96 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, 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', abs(offset), stitch_distance, min_stitch_distance, starting_point, offset_by_half, avoid_self_crossing) + 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), "whatever" + 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, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_single_spiral( - tree, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half) + 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, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_double_spiral( - tree, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half) + 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, connected_line_origin + return connected_line diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py index edc6e0af..a19c0a0a 100644 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py @@ -107,8 +107,8 @@ def create_nearest_points_list( return children_nearest_points -def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, min_stitch_distance, starting_point, - offset_by_half, avoid_self_crossing, forward=True): +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 @@ -183,9 +183,7 @@ def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, child_connection.child_node, offset, stitch_distance, - min_stitch_distance, child_connection.nearest_point_child, - offset_by_half, avoid_self_crossing, not forward ) @@ -259,7 +257,7 @@ def interpolate_linear_rings(ring1, ring2, max_stitch_length, start=None): return result.simplify(constants.simplification_threshold, False) -def connect_raster_tree_single_spiral(tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half): # noqa: C901 +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 @@ -288,10 +286,10 @@ def connect_raster_tree_single_spiral(tree, used_offset, stitch_distance, min_st path = make_spiral(rings, stitch_distance, starting_point) path = [Stitch(*stitch) for stitch in path] - return running_stitch(path, stitch_distance), None + return running_stitch(path, stitch_distance) -def connect_raster_tree_double_spiral(tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half): # noqa: C901 +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 @@ -320,7 +318,7 @@ def connect_raster_tree_double_spiral(tree, used_offset, stitch_distance, min_st path = make_fermat_spiral(rings, stitch_distance, starting_point) path = [Stitch(*stitch) for stitch in path] - return running_stitch(path, stitch_distance), None + return running_stitch(path, stitch_distance) def make_fermat_spiral(rings, stitch_distance, starting_point): diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py index ed1e2c0e..86205f02 100644 --- a/lib/utils/geometry.py +++ b/lib/utils/geometry.py @@ -5,7 +5,7 @@ import math -from shapely.geometry import LineString, LinearRing +from shapely.geometry import LineString, LinearRing, MultiLineString, Polygon, MultiPolygon, GeometryCollection from shapely.geometry import Point as ShapelyPoint @@ -66,6 +66,35 @@ def reverse_line_string(line_string): return LineString(line_string.coords[::-1]) +def ensure_multi_line_string(thing): + """Given either a MultiLineString or a single LineString, return a MultiLineString""" + + if isinstance(thing, LineString): + return MultiLineString([thing]) + else: + return thing + + +def ensure_geometry_collection(thing): + """Given either some kind of geometry or a GeometryCollection, return a GeometryCollection""" + + if isinstance(thing, (MultiLineString, MultiPolygon)): + return GeometryCollection(thing.geoms) + elif isinstance(thing, GeometryCollection): + return thing + else: + return GeometryCollection([thing]) + + +def ensure_multi_polygon(thing): + """Given either a MultiPolygon or a single Polygon, return a MultiPolygon""" + + if isinstance(thing, Polygon): + return MultiPolygon([thing]) + else: + return thing + + def cut_path(points, length): """Return a subsection of at the start of the path that is length units long. |