From 6ca1af0c88728bd91f1775d0056a66d9272b3a1b Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Thu, 21 Apr 2022 23:09:05 -0400 Subject: avoid anytree dependency --- lib/utils/dotdict.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/utils') diff --git a/lib/utils/dotdict.py b/lib/utils/dotdict.py index acd575b9..12cf6e79 100644 --- a/lib/utils/dotdict.py +++ b/lib/utils/dotdict.py @@ -15,7 +15,7 @@ class DotDict(dict): def update(self, *args, **kwargs): super(DotDict, self).update(*args, **kwargs) - self.dotdictify() + self._dotdictify() def _dotdictify(self): for k, v in self.items(): -- cgit v1.3.1 From e14fffb879875cae43124a7daae7cebb5bcadddc Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 30 Apr 2022 15:21:13 -0400 Subject: remove redundant cut() function --- .../tangential_fill_stitch_pattern_creator.py | 32 ++-------------------- lib/utils/geometry.py | 29 +++++++++++++++++++- 2 files changed, 31 insertions(+), 30 deletions(-) (limited to 'lib/utils') diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py index 92a508cd..c3ad0047 100644 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py @@ -14,6 +14,7 @@ from ..stitches import constants from ..stitches import point_transfer from ..stitches import sample_linestring from ..stitch_plan import Stitch +from ..utils.geometry import cut, reverse_line_string, roll_linear_ring nearest_neighbor_tuple = namedtuple( "nearest_neighbor_tuple", @@ -26,34 +27,6 @@ nearest_neighbor_tuple = namedtuple( ) -def cut(line, distance): - """ - Cuts a closed line so that the new closed line starts at the - point with "distance" to the beginning of the old line. - """ - if distance <= 0.0 or distance >= line.length: - return [LineString(line)] - coords = list(line.coords) - for i, p in enumerate(coords): - if i > 0 and p == coords[0]: - pd = line.length - else: - pd = line.project(Point(p)) - if pd == distance: - if coords[0] == coords[-1]: - return LineString(coords[i:] + coords[1: i + 1]) - else: - return LineString(coords[i:] + coords[:i]) - if pd > distance: - cp = line.interpolate(distance) - if coords[0] == coords[-1]: - return LineString( - [(cp.x, cp.y)] + coords[i:] + coords[1:i] + [(cp.x, cp.y)] - ) - else: - return LineString([(cp.x, cp.y)] + coords[i:] + coords[:i]) - - def get_nearest_points_closer_than_thresh(travel_line, next_line, thresh): """ Takes a line and calculates the nearest distance along this @@ -237,7 +210,7 @@ def connect_raster_tree_from_inner_to_outer(tree, node, used_offset, stitch_dist start_distance = current_coords.project(close_point) # We cut the current path so that its index 0 is closest to close_point if start_distance > 0: - current_coords = cut(current_coords, start_distance) + current_coords = roll_linear_ring(current_coords, start_distance) current_node.val = current_coords if not current_node.transferred_point_priority_deque.is_empty(): @@ -254,6 +227,7 @@ def connect_raster_tree_from_inner_to_outer(tree, node, used_offset, stitch_dist # We try to use always the opposite stitching direction with respect to the # parent to avoid crossings when entering and leaving the child + # LEX: this seems like a lie ^^ parent_stitching_direction = -1 if current_node.parent is not None: parent_stitching_direction = tree.nodes[current_node.parent].stitching_direction diff --git a/lib/utils/geometry.py b/lib/utils/geometry.py index bce278ed..ed1e2c0e 100644 --- a/lib/utils/geometry.py +++ b/lib/utils/geometry.py @@ -5,7 +5,7 @@ import math -from shapely.geometry import LineString +from shapely.geometry import LineString, LinearRing from shapely.geometry import Point as ShapelyPoint @@ -39,6 +39,33 @@ def cut(line, distance, normalized=False): LineString([(cp.x, cp.y)] + coords[i:])] +def roll_linear_ring(ring, distance, normalized=False): + """Make a linear ring start at a different point. + + Example: A B C D E F G A -> D E F G A B C + + Same linear ring, different ordering of the coordinates. + """ + + if not isinstance(ring, LinearRing): + # In case they handed us a LineString + ring = LinearRing(ring) + + pieces = cut(LinearRing(ring), distance, normalized=False) + + if None in pieces: + # We cut exactly at the start or end. + return ring + + # The first and last point in a linear ring are duplicated, so we omit one + # copy + return LinearRing(pieces[1].coords[:] + pieces[0].coords[1:]) + + +def reverse_line_string(line_string): + return LineString(line_string.coords[::-1]) + + def cut_path(points, length): """Return a subsection of at the start of the path that is length units long. -- cgit v1.3.1 From aeeaf72338e2d7645309725be641d552a3c56190 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Tue, 3 May 2022 16:58:55 -0400 Subject: wip --- lib/elements/fill_stitch.py | 14 +- lib/stitches/auto_fill.py | 12 +- .../tangential_fill_stitch_line_creator.py | 253 +++++++++------------ .../tangential_fill_stitch_pattern_creator.py | 14 +- lib/utils/geometry.py | 31 ++- 5 files changed, 154 insertions(+), 170 deletions(-) (limited to 'lib/utils') 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. -- cgit v1.3.1