From 0fcf8bb97ced8df552cd0283b4ea009b6ca42623 Mon Sep 17 00:00:00 2001 From: Andreas Date: Thu, 21 Oct 2021 16:24:40 +0200 Subject: added tangential and guided fill --- lib/svg/tags.py | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'lib/svg') diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 8b6f02a4..f3118661 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -11,7 +11,6 @@ inkex.NSS['inkstitch'] = 'http://inkstitch.org/namespace' SVG_PATH_TAG = inkex.addNS('path', 'svg') SVG_POLYLINE_TAG = inkex.addNS('polyline', 'svg') -SVG_POLYGON_TAG = inkex.addNS('polygon', 'svg') SVG_RECT_TAG = inkex.addNS('rect', 'svg') SVG_ELLIPSE_TAG = inkex.addNS('ellipse', 'svg') SVG_CIRCLE_TAG = inkex.addNS('circle', 'svg') @@ -23,15 +22,12 @@ SVG_LINK_TAG = inkex.addNS('a', 'svg') SVG_SYMBOL_TAG = inkex.addNS('symbol', 'svg') SVG_USE_TAG = inkex.addNS('use', 'svg') SVG_IMAGE_TAG = inkex.addNS('image', 'svg') -SVG_CLIPPATH_TAG = inkex.addNS('clipPath', 'svg') -SVG_MASK_TAG = inkex.addNS('mask', 'svg') INKSCAPE_LABEL = inkex.addNS('label', 'inkscape') INKSCAPE_GROUPMODE = inkex.addNS('groupmode', 'inkscape') CONNECTION_START = inkex.addNS('connection-start', 'inkscape') CONNECTION_END = inkex.addNS('connection-end', 'inkscape') CONNECTOR_TYPE = inkex.addNS('connector-type', 'inkscape') -INKSCAPE_DOCUMENT_UNITS = inkex.addNS('document-units', 'inkscape') XLINK_HREF = inkex.addNS('href', 'xlink') @@ -41,8 +37,7 @@ SODIPODI_ROLE = inkex.addNS('role', 'sodipodi') INKSTITCH_LETTERING = inkex.addNS('lettering', 'inkstitch') -EMBROIDERABLE_TAGS = (SVG_PATH_TAG, SVG_POLYLINE_TAG, SVG_POLYGON_TAG, - SVG_RECT_TAG, SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG) +EMBROIDERABLE_TAGS = (SVG_PATH_TAG, SVG_POLYLINE_TAG, SVG_RECT_TAG, SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG) NOT_EMBROIDERABLE_TAGS = (SVG_IMAGE_TAG, SVG_TEXT_TAG) SVG_OBJECT_TAGS = (SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG, SVG_RECT_TAG) @@ -57,6 +52,10 @@ inkstitch_attribs = [ # fill 'angle', 'auto_fill', + 'fill_method', + 'tangential_strategy', + 'join_style', + 'interlaced', 'expand_mm', 'fill_underlay', 'fill_underlay_angle', -- cgit v1.3.1 From 6916a3371695205ca388daa37e3b9a0cc8d51de6 Mon Sep 17 00:00:00 2001 From: Andreas Date: Sun, 20 Mar 2022 17:15:39 +0100 Subject: bug fixing + introduction of min_stitch_distance parameter --- lib/elements/fill_stitch.py | 15 ++++++++ lib/stitches/guided_fill.py | 16 ++++----- lib/stitches/point_transfer.py | 2 +- lib/stitches/sample_linestring.py | 19 +++++++--- .../tangential_fill_stitch_line_creator.py | 10 +++--- .../tangential_fill_stitch_pattern_creator.py | 40 +++++++++++++--------- lib/svg/tags.py | 1 + 7 files changed, 69 insertions(+), 34 deletions(-) (limited to 'lib/svg') diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index eaddcfe0..e0de0f22 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -191,6 +191,19 @@ class FillStitch(EmbroideryElement): def max_stitch_length(self): return max(self.get_float_param("max_stitch_length_mm", 3.0), 0.1 * PIXELS_PER_MM) + @property + @param('min_stitch_length_mm', + _('Minimum fill stitch length'), + tooltip=_( + 'The minimum length of a stitch in a row. Larger values might introduce deviations from the desired path. Shorter stitch may be used at the start or end of a row.'), + unit='mm', + sort_index=4, + select_items=[('fill_method', 1), ('fill_method', 2)], + type='float', + default=0.0) + def min_stitch_length(self): + return self.get_float_param("min_stitch_length_mm", 0.0) + @property @param('staggers', _('Stagger rows this many times before repeating'), @@ -557,6 +570,7 @@ class FillStitch(EmbroideryElement): -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, shgeo.Point(starting_point)) @@ -585,6 +599,7 @@ 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, diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py index 4cc250ef..6948a086 100644 --- a/lib/stitches/guided_fill.py +++ b/lib/stitches/guided_fill.py @@ -24,6 +24,7 @@ def guided_fill(shape, angle, row_spacing, max_stitch_length, + min_stitch_length, running_stitch_length, skip_last, starting_point, @@ -45,7 +46,7 @@ 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, running_stitch_length, skip_last, offset_by_half) + max_stitch_length, min_stitch_length, running_stitch_length, skip_last, offset_by_half) return result @@ -187,13 +188,13 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): del strtree -def stitch_line(stitches, stitching_direction, geometry, projected_points, max_stitch_length, row_spacing, skip_last, offset_by_half): +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, projected_points, abs(row_spacing), offset_by_half, True) + 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, projected_points, abs(row_spacing), offset_by_half, True) + 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): @@ -209,7 +210,7 @@ def stitch_line(stitches, stitching_direction, geometry, projected_points, max_s @debug.time -def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, +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) @@ -230,7 +231,7 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, 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, row_spacing, skip_last, offset_by_half) + 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) @@ -264,9 +265,8 @@ def extend_line(line, minx, maxx, miny, maxy): def repair_multiple_parallel_offset_curves(multi_line): - # TODO: linemerge is overritten by the very next line?!? lines = linemerge(multi_line) - lines = list(multi_line.geoms) + lines = list(lines.geoms) max_length = -1 max_length_idx = -1 for idx, subline in enumerate(lines): diff --git a/lib/stitches/point_transfer.py b/lib/stitches/point_transfer.py index cf4597dd..5506324d 100644 --- a/lib/stitches/point_transfer.py +++ b/lib/stitches/point_transfer.py @@ -70,7 +70,7 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra assert(not transfer_forbidden_points or transfer_forbidden_points and ( offset_by_half or not offset_by_half and overnext_neighbor)) - if len(to_transfer_points) == 0: + if len(to_transfer_points) < 3: return # Get a list of all possible adjacent nodes which will be considered for transferring the points of treenode: diff --git a/lib/stitches/sample_linestring.py b/lib/stitches/sample_linestring.py index b2298984..838b1792 100644 --- a/lib/stitches/sample_linestring.py +++ b/lib/stitches/sample_linestring.py @@ -63,7 +63,7 @@ def calculate_line_angles(line): return Angles -def raster_line_string_with_priority_points(line, start_distance, end_distance, maxstitch_distance, # noqa: C901 +def raster_line_string_with_priority_points(line, start_distance, end_distance, maxstitch_distance, minstitch_distance, # noqa: C901 must_use_points_deque, abs_offset, offset_by_half, replace_forbidden_points): """ Rasters a line between start_distance and end_distance. @@ -72,6 +72,7 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, -start_distance: The distance along the line from which the rastering should start -end_distance: The distance along the line until which the rastering should be done -maxstitch_distance: The maximum allowed stitch distance + -minstitch_distance: The minimum allowed stitch distance -Note that start_distance > end_distance for stitching_direction = -1 -must_use_points_deque: deque with projected points on line from its neighbors. An item of the deque is setup as follows: ((projected point on line, LineStringSampling.PointSource), priority=distance along line) @@ -84,7 +85,7 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, -List which defines the point origin for each point according to the PointSource enum. """ - if (abs(end_distance-start_distance) < constants.line_lengh_seen_as_one_point): + if (abs(end_distance-start_distance) < max(minstitch_distance, constants.line_lengh_seen_as_one_point)): return [line.interpolate(start_distance).coords[0]], [PointSource.HARD_EDGE] deque_points = list(must_use_points_deque) @@ -103,9 +104,9 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, deque_points = deque_points[::-1] # Remove all points from the deque which do not fall in the segment [start_distance; end_distance] - while (len(deque_points) > 0 and deque_points[0][1] <= start_distance+min(maxstitch_distance/20, constants.point_spacing_to_be_considered_equal)): + while (len(deque_points) > 0 and deque_points[0][1] <= start_distance+min(maxstitch_distance/20, minstitch_distance, constants.point_spacing_to_be_considered_equal)): deque_points.pop(0) - while (len(deque_points) > 0 and deque_points[-1][1] >= end_distance-min(maxstitch_distance/20, constants.point_spacing_to_be_considered_equal)): + while (len(deque_points) > 0 and deque_points[-1][1] >= end_distance-min(maxstitch_distance/20, minstitch_distance, constants.point_spacing_to_be_considered_equal)): deque_points.pop() @@ -185,6 +186,9 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, while segment_end_index < len(merged_point_list): segment_length = merged_point_list[segment_end_index][1] - \ merged_point_list[segment_start_index][1] + if segment_length < minstitch_distance: + segment_end_index += 1 + continue if segment_length > maxstitch_distance+constants.point_spacing_to_be_considered_equal: new_distance = merged_point_list[segment_start_index][1] + \ maxstitch_distance @@ -214,6 +218,13 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, iter = segment_start_index+1 while (iter <= segment_end_index): + segment_length = merged_point_list[iter][1] - \ + merged_point_list[segment_start_index][1] + if segment_length < minstitch_distance and merged_point_list[iter][0].point_source != PointSource.HARD_EDGE_INTERNAL: + #We need to create this hard edge exception - otherwise there are some too large deviations posible + iter += 1 + continue + if merged_point_list[iter][0].point_source == PointSource.OVERNEXT: index_overnext = iter elif merged_point_list[iter][0].point_source == PointSource.DIRECT: diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py index af14ea0f..4d4377f0 100644 --- a/lib/stitches/tangential_fill_stitch_line_creator.py +++ b/lib/stitches/tangential_fill_stitch_line_creator.py @@ -158,7 +158,7 @@ def check_and_prepare_tree_for_valid_spiral(root): return True -def offset_poly(poly, offset, join_style, stitch_distance, offset_by_half, strategy, starting_point): # noqa: C901 +def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, offset_by_half, strategy, starting_point): # noqa: C901 """ Takes a polygon (which can have holes) as input and creates offsetted versions until the polygon is filled with these smaller offsets. @@ -173,6 +173,8 @@ def offset_poly(poly, offset, join_style, stitch_distance, offset_by_half, strat 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 @@ -315,15 +317,15 @@ def offset_poly(poly, offset, join_style, stitch_distance, offset_by_half, strat if strategy == StitchingStrategy.CLOSEST_POINT: (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_nearest_neighbor( - root, offset, stitch_distance, starting_point, offset_by_half) + root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half) elif strategy == StitchingStrategy.INNER_TO_OUTER: (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_from_inner_to_outer( - root, offset, stitch_distance, starting_point, offset_by_half) + root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half) elif strategy == StitchingStrategy.SPIRAL: if not check_and_prepare_tree_for_valid_spiral(root): raise ValueError("Geometry cannot be filled with one spiral!") (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_spiral( - root, offset, stitch_distance, starting_point, offset_by_half) + root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half) else: raise ValueError("Invalid stitching stratety!") diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py index d7afad0c..95143bce 100644 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py @@ -52,7 +52,7 @@ def cut(line, distance): def connect_raster_tree_nearest_neighbor( # noqa: C901 - tree, used_offset, stitch_distance, close_point, offset_by_half): + tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half): """ Takes the offsetted curves organized as tree, connects and samples them. Strategy: A connection from parent to child is made where both curves @@ -63,6 +63,8 @@ def connect_raster_tree_nearest_neighbor( # noqa: C901 -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. @@ -136,6 +138,7 @@ def connect_raster_tree_nearest_neighbor( # noqa: C901 # points for start and end) end_distance, stitch_distance, + min_stitch_distance, tree.transferred_point_priority_deque, abs_offset, offset_by_half, @@ -230,6 +233,7 @@ def connect_raster_tree_nearest_neighbor( # noqa: C901 item.child_node, used_offset, stitch_distance, + min_stitch_distance, item.nearest_point_child, offset_by_half, ) @@ -432,7 +436,7 @@ def calculate_replacing_middle_point(line_segment, abs_offset, max_stitch_distan return line_segment.coords[1] -def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, close_point, offset_by_half): # noqa: C901 +def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half): # noqa: C901 """ Takes the offsetted curves organized as tree, connects and samples them. Strategy: A connection from parent to child is made as fast as possible to @@ -444,6 +448,8 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, -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. @@ -514,11 +520,12 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, if stitching_direction == 1: (own_coords, own_coords_origin) = sample_linestring.raster_line_string_with_priority_points( current_coords, - start_offset, # We add start_offset to not sample the same - # point again (avoid double points for start + start_offset, # We add start_offset to not sample the initial/end + # point twice (avoid double points for start # and end) end_offset, stitch_distance, + min_stitch_distance, tree.transferred_point_priority_deque, abs_offset, offset_by_half, @@ -529,12 +536,13 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, current_coords, current_coords.length - start_offset, # We subtract # start_offset to not - # sample the same point - # again (avoid double + # sample the initial/end point + # twice (avoid double # points for start # and end) current_coords.length - end_offset, stitch_distance, + min_stitch_distance, tree.transferred_point_priority_deque, abs_offset, offset_by_half, @@ -639,6 +647,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, item.child_node, used_offset, stitch_distance, + min_stitch_distance, item.nearest_point_child, offset_by_half, ) @@ -683,19 +692,12 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, if cur_item < len(nearest_points_list) - 1: d = min( d, - abs( - nearest_points_list[cur_item + - 1].proj_distance_parent - - item.proj_distance_parent - ), + abs(nearest_points_list[cur_item + 1].proj_distance_parent - item.proj_distance_parent), ) if d > constants.factor_offset_starting_points * abs_offset: result_coords.append( - current_coords.interpolate( - item.proj_distance_parent - + 2 * constants.factor_offset_starting_points * abs_offset - ).coords[0] + current_coords.interpolate(item.proj_distance_parent + 2 * constants.factor_offset_starting_points * abs_offset).coords[0] ) result_coords_origin.append( sample_linestring.PointSource.ENTER_LEAVING_POINT @@ -792,7 +794,7 @@ def interpolate_LinearRings(a, b, start=None, step=.005): def connect_raster_tree_spiral( - tree, used_offset, stitch_distance, close_point, offset_by_half): + tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half): """ 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 @@ -802,6 +804,8 @@ def connect_raster_tree_spiral( -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. @@ -819,6 +823,7 @@ def connect_raster_tree_spiral( 0, tree.val.length, stitch_distance, + min_stitch_distance, tree.transferred_point_priority_deque, abs_offset, offset_by_half, @@ -842,6 +847,7 @@ def connect_raster_tree_spiral( 0, node.val.length, stitch_distance, + min_stitch_distance, node.transferred_point_priority_deque, abs_offset, offset_by_half, @@ -883,7 +889,7 @@ def connect_raster_tree_spiral( lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[0], own_coords[1]]) else: lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[1]]) - (temp_coords, _) = sample_linestring.raster_line_string_with_priority_points(lineseg, 0, lineseg.length, stitch_distance, + (temp_coords, _) = sample_linestring.raster_line_string_with_priority_points(lineseg, 0, lineseg.length, stitch_distance, min_stitch_distance, DEPQ(), abs_offset, offset_by_half, False) if len(temp_coords) == 2: # only start and end point of lineseg was needed result_coords.pop() diff --git a/lib/svg/tags.py b/lib/svg/tags.py index f3118661..37eb5752 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -64,6 +64,7 @@ inkstitch_attribs = [ 'fill_underlay_row_spacing_mm', 'fill_underlay_skip_last', 'max_stitch_length_mm', + 'min_stitch_length_mm', 'row_spacing_mm', 'end_row_spacing_mm', 'skip_last', -- cgit v1.3.1 From bd8cb0d1ff2ce1f17ed8d3a5eaca19f8e8652ad0 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 2 May 2022 14:38:33 -0400 Subject: use running_stitch instead for guided fill --- lib/stitches/auto_fill.py | 23 +++--- lib/stitches/fill.py | 6 +- lib/stitches/guided_fill.py | 170 +++++++++----------------------------------- lib/svg/path.py | 6 ++ 4 files changed, 48 insertions(+), 157 deletions(-) (limited to 'lib/svg') diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 27328bab..35412e93 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -59,9 +59,9 @@ def auto_fill(shape, starting_point, ending_point=None, underpath=True): - fill_stitch_graph = [] try: - fill_stitch_graph = build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point, ending_point) + segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) + fill_stitch_graph = build_fill_stitch_graph(shape, segments, 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) @@ -109,7 +109,7 @@ def project(shape, coords, outline_index): @debug.time -def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting_point=None, ending_point=None): +def build_fill_stitch_graph(shape, segments, 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 @@ -144,10 +144,6 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting debug.add_layer("auto-fill fill stitch") - # Convert the shape into a set of parallel line segments. - rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) - segments = [segment for row in rows_of_segments for segment in row] - graph = networkx.MultiGraph() # First, add the grating segments as edges. We'll use the coordinates @@ -155,7 +151,7 @@ def build_fill_stitch_graph(shape, angle, row_spacing, end_row_spacing, starting for segment in segments: # 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=[], geometry=shgeo.LineString(segment)) + graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[], geometry=shgeo.LineString(segment)) tag_nodes_with_outline_and_projection(graph, shape, graph.nodes()) add_edges_between_outline_nodes(graph, duplicate_every_other=True) @@ -177,7 +173,7 @@ def insert_node(graph, shape, point): point = tuple(point) outline = which_outline(shape, point) projection = project(shape, point, outline) - projected_point = list(shape.boundary)[outline].interpolate(projection) + projected_point = list(shape.boundary.geoms)[outline].interpolate(projection) node = (projected_point.x, projected_point.y) edges = [] @@ -395,10 +391,9 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): def travel_grating(shape, angle, row_spacing): - rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing) - segments = list(chain(*rows_of_segments)) + segments = intersect_region_with_grating(shape, angle, row_spacing) - return shgeo.MultiLineString(segments) + return shgeo.MultiLineString(list(segments)) def ensure_multi_line_string(thing): @@ -457,7 +452,7 @@ def build_travel_edges(shape, fill_angle): debug.log_line_strings(grating3, "grating3") endpoints = [coord for mls in (grating1, grating2, grating3) - for ls in mls + for ls in mls.geoms for coord in ls.coords] diagonal_edges = ensure_multi_line_string( @@ -467,7 +462,7 @@ def build_travel_edges(shape, fill_angle): vertical_edges = ensure_multi_line_string( snap(grating3.difference(grating1), diagonal_edges, 0.005)) - return endpoints, chain(diagonal_edges, vertical_edges) + return endpoints, chain(diagonal_edges.geoms, vertical_edges.geoms) def nearest_node(nodes, point, attr=None): diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index 1fdc6fac..a09b93b1 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -136,8 +136,6 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non # fill regions at the same angle and spacing always line up nicely. start -= (start + normal * center) % row_spacing - rows = [] - current_row_y = start while current_row_y < end: @@ -165,7 +163,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non runs.reverse() runs = [tuple(reversed(run)) for run in runs] - rows.append(runs) + yield from runs if end_row_spacing: current_row_y += row_spacing + \ @@ -174,8 +172,6 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non else: current_row_y += row_spacing - return rows - def section_to_stitches(group_of_segments, angle, row_spacing, max_stitch_length, staggers, skip_last): stitches = [] diff --git a/lib/stitches/guided_fill.py b/lib/stitches/guided_fill.py index 9170d66f..40728c53 100644 --- a/lib/stitches/guided_fill.py +++ b/lib/stitches/guided_fill.py @@ -1,14 +1,10 @@ -import networkx -from depq import DEPQ -from shapely.geometry import GeometryCollection, LineString, MultiLineString +from shapely import geometry as shgeo 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 .auto_fill import (build_fill_stitch_graph, + build_travel_graph, collapse_sequential_outline_edges, fallback, + find_stitch_path, graph_is_valid, travel) +from .running_stitch import running_stitch from ..debug import debug from ..i18n import _ from ..stitch_plan import Stitch @@ -28,11 +24,9 @@ def guided_fill(shape, 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) + segments = intersect_region_with_grating_guideline(shape, guideline, row_spacing) + fill_stitch_graph = build_fill_stitch_graph(shape, segments, 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) @@ -48,108 +42,6 @@ def guided_fill(shape, 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): @@ -163,23 +55,23 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, 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) + + if edge[0] != path_geometry.coords[0]: + 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) + + # need to tag stitches + + if skip_last: + del new_stitches[-1] stitches.extend(new_stitches) + + travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', [])) else: stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last)) @@ -195,14 +87,14 @@ def extend_line(line, minx, maxx, miny, maxy): point1 = InkstitchPoint(*line.coords[0]) point2 = InkstitchPoint(*line.coords[1]) - new_starting_point = point1-(point2-point1).unit()*length + 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 + new_ending_point = point4 + (point4 - point3).unit() * length - return LineString([new_starting_point.as_tuple()] + - line.coords[1:-1]+[new_ending_point.as_tuple()]) + return shgeo.LineString([new_starting_point.as_tuple()] + + line.coords[1:-1] + [new_ending_point.as_tuple()]) def repair_multiple_parallel_offset_curves(multi_line): @@ -251,15 +143,15 @@ def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False 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)): + while isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)) or (not res.is_empty and len(res.coords) > 1): + if isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)): runs = [line_string.coords for line_string in res.geoms if ( - not line_string.is_empty and len(line_string.coords) > 1)] + 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()) + InkstitchPoint(*seg[0]) - upper_left).length()) if flip: runs.reverse() runs = [tuple(reversed(run)) for run in runs] @@ -279,7 +171,7 @@ def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False 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 row_spacing > 0 and not isinstance(res, (shgeo.GeometryCollection, shgeo.MultiLineString)): if (res.is_empty or len(res.coords) == 1): row_spacing = -row_spacing @@ -293,4 +185,6 @@ def intersect_region_with_grating_guideline(shape, line, row_spacing, flip=False line_offsetted = reverse_line_string(line_offsetted) line_offsetted = line_offsetted.simplify(0.01, False) res = line_offsetted.intersection(shape) - return rows + + for row in rows: + yield from row diff --git a/lib/svg/path.py b/lib/svg/path.py index c33a7a8f..6c2cbe35 100644 --- a/lib/svg/path.py +++ b/lib/svg/path.py @@ -74,6 +74,12 @@ def get_correction_transform(node, child=False): def line_strings_to_csp(line_strings): + try: + # This lets us accept a MultiLineString or a list. + line_strings = line_strings.geoms + except AttributeError: + pass + return point_lists_to_csp(ls.coords for ls in line_strings) -- cgit v1.3.1 From 76ab3197317f258ede1bd98195535f33b856b3fd Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 2 May 2022 15:00:52 -0400 Subject: add avoid_self_Crossing option --- lib/elements/fill_stitch.py | 11 +- .../tangential_fill_stitch_line_creator.py | 6 +- .../tangential_fill_stitch_pattern_creator.py | 10 +- lib/svg/tags.py | 111 +++++++++++---------- 4 files changed, 77 insertions(+), 61 deletions(-) (limited to 'lib/svg') diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index 4157d3fb..bc022ab3 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -118,6 +118,11 @@ class FillStitch(EmbroideryElement): def interlaced(self): return self.get_boolean_param('interlaced', True) + @property + @param('avoid_self_crossing', _('Avoid self-crossing'), type='boolean', default=False, select_items=[('fill_method', 1)], sort_index=2) + def avoid_self_crossing(self): + return self.get_boolean_param('avoid_self_crossing', False) + @property @param('angle', _('Angle of lines of stitches'), @@ -569,12 +574,14 @@ class FillStitch(EmbroideryElement): connectedLine, _ = tangential_fill_stitch_line_creator.offset_poly( poly, -self.row_spacing, - self.join_style+1, + self.join_style + 1, self.max_stitch_length, min(self.min_stitch_length, self.max_stitch_length), self.interlaced, self.tangential_strategy, - shgeo.Point(starting_point)) + shgeo.Point(starting_point), + self.avoid_self_crossing + ) path = [InkstitchPoint(*p) for p in connectedLine] stitch_group = StitchGroup( color=self.color, diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py index 7f8b3bea..61598b58 100644 --- a/lib/stitches/tangential_fill_stitch_line_creator.py +++ b/lib/stitches/tangential_fill_stitch_line_creator.py @@ -115,7 +115,8 @@ 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 +def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, offset_by_half, strategy, starting_point, # noqa: C901 + avoid_self_crossing): """ Takes a polygon (which can have holes) as input and creates offsetted versions until the polygon is filled with these smaller offsets. @@ -139,6 +140,7 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, 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 @@ -277,7 +279,7 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, 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) + tree, 'root', abs(offset), stitch_distance, min_stitch_distance, starting_point, offset_by_half, avoid_self_crossing) path = [Stitch(*point) for point in connected_line.coords] return running_stitch(path, stitch_distance), "whatever" elif strategy == StitchingStrategy.SPIRAL: diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py index 20f7a651..553241f8 100644 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py @@ -110,7 +110,7 @@ def create_nearest_points_list( @debug.time def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, min_stitch_distance, starting_point, - offset_by_half): # noqa: C901 + offset_by_half, 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 @@ -137,6 +137,9 @@ def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, 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) @@ -157,7 +160,8 @@ def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, 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) + # 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 @@ -184,6 +188,8 @@ def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, min_stitch_distance, child_connection.nearest_point_child, offset_by_half, + avoid_self_crossing, + not forward ) result_coords.extend(child_path.coords) diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 37eb5752..3f412c2e 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -43,60 +43,61 @@ SVG_OBJECT_TAGS = (SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG, SVG_RECT_TAG) INKSTITCH_ATTRIBS = {} inkstitch_attribs = [ - 'ties', - 'force_lock_stitches', - # clone - 'clone', - # polyline - 'polyline', - # fill - 'angle', - 'auto_fill', - 'fill_method', - 'tangential_strategy', - 'join_style', - 'interlaced', - 'expand_mm', - 'fill_underlay', - 'fill_underlay_angle', - 'fill_underlay_inset_mm', - 'fill_underlay_max_stitch_length_mm', - 'fill_underlay_row_spacing_mm', - 'fill_underlay_skip_last', - 'max_stitch_length_mm', - 'min_stitch_length_mm', - 'row_spacing_mm', - 'end_row_spacing_mm', - 'skip_last', - 'staggers', - 'underlay_underpath', - 'underpath', - 'flip', - 'expand_mm', - # stroke - 'manual_stitch', - 'bean_stitch_repeats', - 'repeats', - 'running_stitch_length_mm', - # satin column - 'satin_column', - 'running_stitch_length_mm', - 'center_walk_underlay', - 'center_walk_underlay_stitch_length_mm', - 'contour_underlay', - 'contour_underlay_stitch_length_mm', - 'contour_underlay_inset_mm', - 'zigzag_underlay', - 'zigzag_spacing_mm', - 'zigzag_underlay_inset_mm', - 'zigzag_underlay_spacing_mm', - 'zigzag_underlay_max_stitch_length_mm', - 'e_stitch', - 'pull_compensation_mm', - 'stroke_first', - # Legacy - 'trim_after', - 'stop_after' - ] + 'ties', + 'force_lock_stitches', + # clone + 'clone', + # polyline + 'polyline', + # fill + 'angle', + 'auto_fill', + 'fill_method', + 'tangential_strategy', + 'join_style', + 'interlaced', + 'avoid_self_crossing', + 'expand_mm', + 'fill_underlay', + 'fill_underlay_angle', + 'fill_underlay_inset_mm', + 'fill_underlay_max_stitch_length_mm', + 'fill_underlay_row_spacing_mm', + 'fill_underlay_skip_last', + 'max_stitch_length_mm', + 'min_stitch_length_mm', + 'row_spacing_mm', + 'end_row_spacing_mm', + 'skip_last', + 'staggers', + 'underlay_underpath', + 'underpath', + 'flip', + 'expand_mm', + # stroke + 'manual_stitch', + 'bean_stitch_repeats', + 'repeats', + 'running_stitch_length_mm', + # satin column + 'satin_column', + 'running_stitch_length_mm', + 'center_walk_underlay', + 'center_walk_underlay_stitch_length_mm', + 'contour_underlay', + 'contour_underlay_stitch_length_mm', + 'contour_underlay_inset_mm', + 'zigzag_underlay', + 'zigzag_spacing_mm', + 'zigzag_underlay_inset_mm', + 'zigzag_underlay_spacing_mm', + 'zigzag_underlay_max_stitch_length_mm', + 'e_stitch', + 'pull_compensation_mm', + 'stroke_first', + # Legacy + 'trim_after', + 'stop_after' +] for attrib in inkstitch_attribs: INKSTITCH_ATTRIBS[attrib] = inkex.addNS(attrib, 'inkstitch') -- cgit v1.3.1 From 68ee0eea8733d613543a28627bd21a4481da8b46 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 2 May 2022 23:48:46 -0400 Subject: add clockwise option --- lib/elements/fill_stitch.py | 8 +++++- .../tangential_fill_stitch_line_creator.py | 29 +++++++++++++++------- .../tangential_fill_stitch_pattern_creator.py | 12 --------- lib/svg/tags.py | 1 + 4 files changed, 28 insertions(+), 22 deletions(-) (limited to 'lib/svg') diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index bc022ab3..2f8687a1 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -123,6 +123,11 @@ class FillStitch(EmbroideryElement): def avoid_self_crossing(self): return self.get_boolean_param('avoid_self_crossing', False) + @property + @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 1), ('fill_method', 2)], sort_index=2) + def clockwise(self): + return self.get_boolean_param('clockwise', True) + @property @param('angle', _('Angle of lines of stitches'), @@ -580,7 +585,8 @@ class FillStitch(EmbroideryElement): self.interlaced, self.tangential_strategy, shgeo.Point(starting_point), - self.avoid_self_crossing + self.avoid_self_crossing, + self.clockwise ) path = [InkstitchPoint(*p) for p in connectedLine] stitch_group = StitchGroup( diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py index 61598b58..78213384 100644 --- a/lib/stitches/tangential_fill_stitch_line_creator.py +++ b/lib/stitches/tangential_fill_stitch_line_creator.py @@ -8,12 +8,12 @@ from shapely.geometry.polygon import LinearRing 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 ..stitch_plan import Stitch from ..utils import DotDict - -from .running_stitch import running_stitch +from ..utils.geometry import reverse_line_string class Tree(nx.DiGraph): @@ -59,15 +59,26 @@ def take_only_valid_linear_rings(rings): return LinearRing() -def make_tree_uniform_ccw(tree): +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 nx.dfs_preorder_nodes(tree, 'root'): - if tree.nodes[node].type == "hole": - tree.nodes[node].val = LinearRing(reversed(tree.nodes[node].val.coords)) + + for node in tree.nodes.values(): + node.val = orient_linear_ring(node.val, clockwise) # Used to define which stitching strategy shall be used @@ -116,7 +127,7 @@ def check_and_prepare_tree_for_valid_spiral(tree): def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, offset_by_half, strategy, starting_point, # noqa: C901 - avoid_self_crossing): + avoid_self_crossing, clockwise): """ Takes a polygon (which can have holes) as input and creates offsetted versions until the polygon is filled with these smaller offsets. @@ -275,7 +286,7 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, tree.nodes[previous_hole].parent = current_poly tree.add_edge(current_poly, previous_hole) - make_tree_uniform_ccw(tree) + make_tree_uniform(tree, clockwise) if strategy == StitchingStrategy.INNER_TO_OUTER: connected_line = tangential_fill_stitch_pattern_creator.connect_raster_tree_from_inner_to_outer( diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py index 9b59fa07..2556d58c 100644 --- a/lib/stitches/tangential_fill_stitch_pattern_creator.py +++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py @@ -24,7 +24,6 @@ nearest_neighbor_tuple = namedtuple( ) -@debug.time 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. @@ -108,7 +107,6 @@ def create_nearest_points_list( return children_nearest_points -@debug.time 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): """ @@ -213,13 +211,6 @@ def connect_raster_tree_from_inner_to_outer(tree, node, offset, stitch_distance, return LineString(result_coords) -def orient_linear_ring(ring): - if not ring.is_ccw: - return LinearRing(reversed(ring.coords)) - else: - return ring - - def reorder_linear_ring(ring, start): distances = ring - start start_index = np.argmin(np.linalg.norm(distances, axis=1)) @@ -245,9 +236,6 @@ def interpolate_linear_rings(ring1, ring2, max_stitch_length, start=None): Return value: Path interpolated between two LinearRings, as a LineString. """ - ring1 = orient_linear_ring(ring1) - ring2 = orient_linear_ring(ring2) - # 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. diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 3f412c2e..02340aa5 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -57,6 +57,7 @@ inkstitch_attribs = [ 'join_style', 'interlaced', 'avoid_self_crossing', + 'clockwise', 'expand_mm', 'fill_underlay', 'fill_underlay_angle', -- cgit v1.3.1 From e65aaebbcab1ca6fbcf99d9f3665af423e02c2f5 Mon Sep 17 00:00:00 2001 From: Kaalleen Date: Wed, 4 May 2022 20:04:39 +0200 Subject: rebase corrections --- lib/elements/clone.py | 6 ------ lib/extensions/base.py | 15 ++++++++++++--- lib/stitches/fill.py | 1 - lib/svg/tags.py | 10 ++++++++-- 4 files changed, 20 insertions(+), 12 deletions(-) (limited to 'lib/svg') diff --git a/lib/elements/clone.py b/lib/elements/clone.py index 303c1c2f..d9185012 100644 --- a/lib/elements/clone.py +++ b/lib/elements/clone.py @@ -5,13 +5,7 @@ from math import atan, degrees -<<<<<<< HEAD -from ..commands import is_command, is_command_symbol -======= -import inkex - from ..commands import is_command_symbol ->>>>>>> c69b6f5a (* autofill to fillstitch) from ..i18n import _ from ..svg.path import get_node_transform from ..svg.svg import find_elements diff --git a/lib/extensions/base.py b/lib/extensions/base.py index 949f947e..cf94714c 100644 --- a/lib/extensions/base.py +++ b/lib/extensions/base.py @@ -8,10 +8,12 @@ import os import re from collections.abc import MutableMapping -import inkex from lxml import etree +from lxml.etree import Comment from stringcase import snakecase +import inkex + from ..commands import is_command, layer_commands from ..elements import EmbroideryElement, nodes_to_elements from ..elements.clone import is_clone @@ -19,7 +21,8 @@ from ..i18n import _ from ..marker import has_marker from ..svg import generate_unique_id from ..svg.tags import (CONNECTOR_TYPE, EMBROIDERABLE_TAGS, INKSCAPE_GROUPMODE, - NOT_EMBROIDERABLE_TAGS, SVG_DEFS_TAG, SVG_GROUP_TAG) + NOT_EMBROIDERABLE_TAGS, SVG_CLIPPATH_TAG, SVG_DEFS_TAG, + SVG_GROUP_TAG, SVG_MASK_TAG) SVG_METADATA_TAG = inkex.addNS("metadata", "svg") @@ -129,6 +132,10 @@ class InkstitchExtension(inkex.Effect): def descendants(self, node, selected=False, troubleshoot=False): # noqa: C901 nodes = [] + + if node.tag == Comment: + return [] + element = EmbroideryElement(node) if element.has_command('ignore_object'): @@ -141,7 +148,9 @@ class InkstitchExtension(inkex.Effect): if (node.tag in EMBROIDERABLE_TAGS or node.tag == SVG_GROUP_TAG) and element.get_style('display', 'inline') is None: return [] - if node.tag == SVG_DEFS_TAG: + # defs, masks and clippaths can contain embroiderable elements + # but should never be rendered directly. + if node.tag in [SVG_DEFS_TAG, SVG_MASK_TAG, SVG_CLIPPATH_TAG]: return [] # command connectors with a fill color set, will glitch into the elements list diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index a09b93b1..94df3f77 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -11,7 +11,6 @@ from ..stitch_plan import Stitch from ..svg import PIXELS_PER_MM from ..utils import Point as InkstitchPoint from ..utils import cache -from ..stitch_plan import Stitch def legacy_fill(shape, angle, row_spacing, end_row_spacing, max_stitch_length, flip, staggers, skip_last): diff --git a/lib/svg/tags.py b/lib/svg/tags.py index 02340aa5..0c5ffd3d 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -3,14 +3,16 @@ # Copyright (c) 2010 Authors # Licensed under the GNU GPL version 3.0 or later. See the file LICENSE for details. -import inkex from lxml import etree +import inkex + etree.register_namespace("inkstitch", "http://inkstitch.org/namespace") inkex.NSS['inkstitch'] = 'http://inkstitch.org/namespace' SVG_PATH_TAG = inkex.addNS('path', 'svg') SVG_POLYLINE_TAG = inkex.addNS('polyline', 'svg') +SVG_POLYGON_TAG = inkex.addNS('polygon', 'svg') SVG_RECT_TAG = inkex.addNS('rect', 'svg') SVG_ELLIPSE_TAG = inkex.addNS('ellipse', 'svg') SVG_CIRCLE_TAG = inkex.addNS('circle', 'svg') @@ -22,12 +24,15 @@ SVG_LINK_TAG = inkex.addNS('a', 'svg') SVG_SYMBOL_TAG = inkex.addNS('symbol', 'svg') SVG_USE_TAG = inkex.addNS('use', 'svg') SVG_IMAGE_TAG = inkex.addNS('image', 'svg') +SVG_CLIPPATH_TAG = inkex.addNS('clipPath', 'svg') +SVG_MASK_TAG = inkex.addNS('mask', 'svg') INKSCAPE_LABEL = inkex.addNS('label', 'inkscape') INKSCAPE_GROUPMODE = inkex.addNS('groupmode', 'inkscape') CONNECTION_START = inkex.addNS('connection-start', 'inkscape') CONNECTION_END = inkex.addNS('connection-end', 'inkscape') CONNECTOR_TYPE = inkex.addNS('connector-type', 'inkscape') +INKSCAPE_DOCUMENT_UNITS = inkex.addNS('document-units', 'inkscape') XLINK_HREF = inkex.addNS('href', 'xlink') @@ -37,7 +42,8 @@ SODIPODI_ROLE = inkex.addNS('role', 'sodipodi') INKSTITCH_LETTERING = inkex.addNS('lettering', 'inkstitch') -EMBROIDERABLE_TAGS = (SVG_PATH_TAG, SVG_POLYLINE_TAG, SVG_RECT_TAG, SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG) +EMBROIDERABLE_TAGS = (SVG_PATH_TAG, SVG_POLYLINE_TAG, SVG_POLYGON_TAG, + SVG_RECT_TAG, SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG) NOT_EMBROIDERABLE_TAGS = (SVG_IMAGE_TAG, SVG_TEXT_TAG) SVG_OBJECT_TAGS = (SVG_ELLIPSE_TAG, SVG_CIRCLE_TAG, SVG_RECT_TAG) -- cgit v1.3.1 From a275d49a24dc91b734c6dbee1e29157bfd0d59d5 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Thu, 5 May 2022 22:53:31 -0400 Subject: tangential->contour, fix legacy, remove unused params --- lib/elements/element.py | 4 +- lib/elements/fill_stitch.py | 76 ++---- lib/stitches/auto_fill.py | 6 +- lib/stitches/contour_fill.py | 536 +++++++++++++++++++++++++++++++++++++++ lib/stitches/fill.py | 3 +- lib/stitches/tangential_fill.py | 537 ---------------------------------------- lib/svg/tags.py | 4 +- 7 files changed, 572 insertions(+), 594 deletions(-) create mode 100644 lib/stitches/contour_fill.py delete mode 100644 lib/stitches/tangential_fill.py (limited to 'lib/svg') diff --git a/lib/elements/element.py b/lib/elements/element.py index ee4eadbb..3f5c6f4a 100644 --- a/lib/elements/element.py +++ b/lib/elements/element.py @@ -208,7 +208,7 @@ class EmbroideryElement(object): # L10N options to allow lock stitch before and after objects options=[_("Both"), _("Before"), _("After"), _("Neither")], default=0, - sort_index=4) + sort_index=10) @cache def ties(self): return self.get_int_param("ties", 0) @@ -220,7 +220,7 @@ class EmbroideryElement(object): 'even if the distance to the next object is shorter than defined by the collapse length value in the Ink/Stitch preferences.'), type='boolean', default=False, - sort_index=5) + sort_index=10) @cache def force_lock_stitches(self): return self.get_boolean_param('force_lock_stitches', False) diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py index d7b859b5..c1bba7b8 100644 --- a/lib/elements/fill_stitch.py +++ b/lib/elements/fill_stitch.py @@ -15,7 +15,7 @@ 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, auto_fill, legacy_fill, guided_fill +from ..stitches import contour_fill, auto_fill, legacy_fill, guided_fill from ..svg import PIXELS_PER_MM from ..svg.tags import INKSCAPE_LABEL from ..utils import cache, version @@ -96,34 +96,29 @@ class FillStitch(EmbroideryElement): @property @param('fill_method', _('Fill method'), type='dropdown', default=0, - options=[_("Auto Fill"), _("Tangential"), _("Guided Fill"), _("Legacy Fill")], sort_index=2) + options=[_("Auto Fill"), _("Contour Fill"), _("Guided Fill"), _("Legacy Fill")], sort_index=2) def fill_method(self): return self.get_int_param('fill_method', 0) @property - @param('tangential_strategy', _('Tangential strategy'), type='dropdown', default=1, - options=[_("Inner to Outer"), _("Single spiral"), _("Double spiral")], select_items=[('fill_method', 1)], sort_index=2) - def tangential_strategy(self): - return self.get_int_param('tangential_strategy', 1) + @param('contour_strategy', _('Contour Fill Strategy'), type='dropdown', default=1, + options=[_("Inner to Outer"), _("Single spiral"), _("Double spiral")], select_items=[('fill_method', 1)], sort_index=3) + def contour_strategy(self): + return self.get_int_param('contour_strategy', 1) @property @param('join_style', _('Join Style'), type='dropdown', default=0, - options=[_("Round"), _("Mitered"), _("Beveled")], select_items=[('fill_method', 1)], sort_index=2) + options=[_("Round"), _("Mitered"), _("Beveled")], select_items=[('fill_method', 1)], sort_index=4) def join_style(self): return self.get_int_param('join_style', 0) @property - @param('interlaced', _('Interlaced'), type='boolean', default=True, select_items=[('fill_method', 1), ('fill_method', 2)], sort_index=2) - def interlaced(self): - return self.get_boolean_param('interlaced', True) - - @property - @param('avoid_self_crossing', _('Avoid self-crossing'), type='boolean', default=False, select_items=[('fill_method', 1)], sort_index=2) + @param('avoid_self_crossing', _('Avoid self-crossing'), type='boolean', default=False, select_items=[('fill_method', 1)], sort_index=5) def avoid_self_crossing(self): return self.get_boolean_param('avoid_self_crossing', False) @property - @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 1), ('fill_method', 2)], sort_index=2) + @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 1)], sort_index=5) def clockwise(self): return self.get_boolean_param('clockwise', True) @@ -133,7 +128,7 @@ class FillStitch(EmbroideryElement): tooltip=_('The angle increases in a counter-clockwise direction. 0 is horizontal. Negative angles are allowed.'), unit='deg', type='float', - sort_index=4, + sort_index=6, select_items=[('fill_method', 0), ('fill_method', 3)], default=0) @cache @@ -152,7 +147,7 @@ class FillStitch(EmbroideryElement): tooltip=_('The last stitch in each row is quite close to the first stitch in the next row. ' 'Skipping it decreases stitch count and density.'), type='boolean', - sort_index=4, + sort_index=6, select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 3)], default=False) @@ -166,7 +161,7 @@ class FillStitch(EmbroideryElement): tooltip=_('The flip option can help you with routing your stitch path. ' 'When you enable flip, stitching goes from right-to-left instead of left-to-right.'), type='boolean', - sort_index=4, + sort_index=7, select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 3)], default=False) @@ -178,7 +173,7 @@ class FillStitch(EmbroideryElement): _('Spacing between rows'), tooltip=_('Distance between rows of stitches.'), unit='mm', - sort_index=4, + sort_index=6, type='float', default=0.25) def row_spacing(self): @@ -194,32 +189,18 @@ class FillStitch(EmbroideryElement): tooltip=_( 'The length of each stitch in a row. Shorter stitch may be used at the start or end of a row.'), unit='mm', - sort_index=4, + sort_index=6, type='float', default=3.0) def max_stitch_length(self): return max(self.get_float_param("max_stitch_length_mm", 3.0), 0.1 * PIXELS_PER_MM) - @property - @param('min_stitch_length_mm', - _('Minimum fill stitch length'), - tooltip=_( - 'The minimum length of a stitches in a row. Larger values might introduce deviations from the desired path.' - 'Shorter stitch may be used at the start or end of a row.'), - unit='mm', - sort_index=4, - select_items=[('fill_method', 1), ('fill_method', 2)], - type='float', - default=0.0) - def min_stitch_length(self): - return self.get_float_param("min_stitch_length_mm", 0.0) - @property @param('staggers', _('Stagger rows this many times before repeating'), tooltip=_('Setting this dictates how many rows apart the stitches will be before they fall in the same column position.'), type='int', - sort_index=4, + sort_index=6, select_items=[('fill_method', 0), ('fill_method', 3)], default=4) def staggers(self): @@ -339,7 +320,7 @@ class FillStitch(EmbroideryElement): type='float', default=1.5, select_items=[('fill_method', 0), ('fill_method', 2)], - sort_index=4) + sort_index=6) def running_stitch_length(self): return max(self.get_float_param("running_stitch_length_mm", 1.5), 0.01) @@ -505,14 +486,11 @@ class FillStitch(EmbroideryElement): underlay_stitch_groups, start = self.do_underlay(start) stitch_groups.extend(underlay_stitch_groups) if self.fill_method == 0: - stitch_groups.extend( - self.do_auto_fill(last_patch, start, end)) + stitch_groups.extend(self.do_auto_fill(last_patch, start, end)) if self.fill_method == 1: - stitch_groups.extend( - self.do_tangential_fill(last_patch, start)) + stitch_groups.extend(self.do_contour_fill(last_patch, start)) elif self.fill_method == 2: - stitch_groups.extend( - self.do_guided_fill(last_patch, start, end)) + stitch_groups.extend(self.do_guided_fill(last_patch, start, end)) except Exception: self.fatal_fill_error() @@ -569,32 +547,32 @@ class FillStitch(EmbroideryElement): self.underpath)) return [stitch_group] - def do_tangential_fill(self, last_patch, starting_point): + def do_contour_fill(self, last_patch, starting_point): if not starting_point: starting_point = (0, 0) 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) + tree = contour_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( + if self.contour_strategy == 0: + stitches = contour_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( + elif self.contour_strategy == 1: + stitches = contour_fill.single_spiral( tree, self.max_stitch_length, starting_point ) - elif self.tangential_strategy == 2: - stitches = tangential_fill.double_spiral( + elif self.contour_strategy == 2: + stitches = contour_fill.double_spiral( tree, self.max_stitch_length, starting_point diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 630178c4..b3b9434f 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -59,7 +59,8 @@ def auto_fill(shape, ending_point=None, underpath=True): try: - segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) + rows = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) + segments = [segment for row in rows for segment in row] fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point) except ValueError: # Small shapes will cause the graph to fail - min() arg is an empty sequence through insert node @@ -390,7 +391,8 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): def travel_grating(shape, angle, row_spacing): - segments = intersect_region_with_grating(shape, angle, row_spacing) + rows = intersect_region_with_grating(shape, angle, row_spacing) + segments = [segment for row in rows for segment in row] return shgeo.MultiLineString(list(segments)) diff --git a/lib/stitches/contour_fill.py b/lib/stitches/contour_fill.py new file mode 100644 index 00000000..916285d8 --- /dev/null +++ b/lib/stitches/contour_fill.py @@ -0,0 +1,536 @@ +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: + # Projecting with 0 lets us avoid distinguishing between LineString and + # MultiLineString. + parent_point = Point(portion_within_threshold.interpolate(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 innermost ring gives a nicer visual appearance. + if not avoid_self_crossing: + current_ring = reverse_line_string(current_ring) + 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) + + 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/fill.py b/lib/stitches/fill.py index 94df3f77..d5a983f9 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -162,7 +162,7 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non runs.reverse() runs = [tuple(reversed(run)) for run in runs] - yield from runs + yield runs if end_row_spacing: current_row_y += row_spacing + \ @@ -225,6 +225,7 @@ def pull_runs(rows, shape, row_spacing): # print >>sys.stderr, "\n".join(str(len(row)) for row in rows) + rows = list(rows) runs = [] count = 0 while (len(rows) > 0): diff --git a/lib/stitches/tangential_fill.py b/lib/stitches/tangential_fill.py deleted file mode 100644 index 833f9db3..00000000 --- a/lib/stitches/tangential_fill.py +++ /dev/null @@ -1,537 +0,0 @@ -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: - # Projecting with 0 lets us avoid distinguishing between LineString and - # MultiLineString. - parent_point = Point(portion_within_threshold.interpolate(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 innermost ring gives a nicer visual appearance. - if not avoid_self_crossing: - current_ring = reverse_line_string(current_ring) - 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/svg/tags.py b/lib/svg/tags.py index 0c5ffd3d..d78ba678 100644 --- a/lib/svg/tags.py +++ b/lib/svg/tags.py @@ -59,9 +59,8 @@ inkstitch_attribs = [ 'angle', 'auto_fill', 'fill_method', - 'tangential_strategy', + 'contour_strategy', 'join_style', - 'interlaced', 'avoid_self_crossing', 'clockwise', 'expand_mm', @@ -72,7 +71,6 @@ inkstitch_attribs = [ 'fill_underlay_row_spacing_mm', 'fill_underlay_skip_last', 'max_stitch_length_mm', - 'min_stitch_length_mm', 'row_spacing_mm', 'end_row_spacing_mm', 'skip_last', -- cgit v1.3.1