diff options
| -rw-r--r-- | lib/elements/auto_fill.py | 2 | ||||
| -rw-r--r-- | lib/stitches/ConnectAndSamplePattern.py | 164 | ||||
| -rw-r--r-- | lib/stitches/LineStringSampling.py | 23 | ||||
| -rw-r--r-- | lib/stitches/PointTransfer.py | 14 | ||||
| -rw-r--r-- | lib/stitches/StitchPattern.py | 154 | ||||
| -rw-r--r-- | lib/stitches/fill.py | 28 | ||||
| -rw-r--r-- | requirements.txt | 2 |
7 files changed, 348 insertions, 39 deletions
diff --git a/lib/elements/auto_fill.py b/lib/elements/auto_fill.py index 094ad91e..dc678087 100644 --- a/lib/elements/auto_fill.py +++ b/lib/elements/auto_fill.py @@ -61,7 +61,7 @@ class AutoFill(EmbroideryElement): @property @param('tangential_strategy', _('Tangential strategy'), type='dropdown', default=1, - options=[_("Closest point"), _("Inner to Outer")], select_items=[('fill_method', 1)], sort_index=2) + options=[_("Closest point"), _("Inner to Outer"), _("single Spiral")], select_items=[('fill_method', 1)], sort_index=2) def tangential_strategy(self): return self.get_int_param('tangential_strategy', 1) diff --git a/lib/stitches/ConnectAndSamplePattern.py b/lib/stitches/ConnectAndSamplePattern.py index e8f1def5..2410f3ca 100644 --- a/lib/stitches/ConnectAndSamplePattern.py +++ b/lib/stitches/ConnectAndSamplePattern.py @@ -3,7 +3,12 @@ from shapely.geometry import Point, MultiPoint from shapely.ops import nearest_points from collections import namedtuple from depq import DEPQ +import trimesh +import numpy as np +from scipy import spatial import math +from shapely.geometry import asLineString +from anytree import PreOrderIter from ..stitches import LineStringSampling from ..stitches import PointTransfer from ..stitches import constants @@ -48,8 +53,7 @@ def cut(line, distance): def connect_raster_tree_nearest_neighbor( - tree, used_offset, stitch_distance, close_point, offset_by_half -): + tree, used_offset, 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 @@ -338,8 +342,7 @@ def get_nearest_points_closer_than_thresh(travel_line, next_line, thresh): def create_nearest_points_list( - travel_line, children_list, threshold, threshold_hard, preferred_direction=0 -): + travel_line, children_list, threshold, threshold_hard, preferred_direction=0): """ Takes a line and calculates the nearest distance along this line to enter the childs in children_list @@ -456,8 +459,7 @@ def calculate_replacing_middle_point(line_segment, abs_offset, max_stitch_distan def connect_raster_tree_from_inner_to_outer( - tree, used_offset, stitch_distance, close_point, offset_by_half -): + tree, used_offset, 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 as fast as possible to @@ -772,3 +774,153 @@ def connect_raster_tree_from_inner_to_outer( assert len(result_coords) == len(result_coords_origin) return result_coords, result_coords_origin + + +# Partly taken from https://github.com/mikedh/pocketing/blob/master/pocketing/polygons.py +def interpolate_LinearRings(a, b, start=None, step=.005): + """ + Interpolate between two LinearRings + Parameters + ------------- + a : shapely.geometry.Polygon.LinearRing + LinearRing start point will lie on + b : shapely.geometry.Polygon.LinearRing + LinearRing end point will lie on + start : (2,) float, or None + Point to start at + step : float + How far apart should points on + the path be. + Returns + ------------- + path : (n, 2) float + Path interpolated between two LinearRings + """ + + # resample the first LinearRing so every sample is spaced evenly + ra = trimesh.path.traversal.resample_path( + a, step=step) + if not a.is_ccw: + ra = ra[::-1] + + assert trimesh.path.util.is_ccw(ra) + if start is not None: + # find the closest index on LinerRing 'a' + # by creating a KDTree + tree_a = spatial.cKDTree(ra) + index = tree_a.query(start)[1] + ra = np.roll(ra, -index, axis=0) + + # resample the second LinearRing for even spacing + rb = trimesh.path.traversal.resample_path(b, + step=step) + if not b.is_ccw: + rb = rb[::-1] + + # we want points on 'b' that correspond index- wise + # the resampled points on 'a' + tree_b = spatial.cKDTree(rb) + # points on b with corresponding indexes to ra + pb = rb[tree_b.query(ra)[1]] + + # linearly interpolate between 'a' and 'b' + weights = np.linspace(0.0, 1.0, len(ra)).reshape((-1, 1)) + + # start on 'a' and end on 'b' + points = (ra * (1.0 - weights)) + (pb * weights) + + result = LineString(points) + + return result.simplify(constants.simplification_threshold, False) + + +def connect_raster_tree_spiral( + tree, used_offset, 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 + Input: + -tree: contains the offsetted curves in a hierachical organized + data structure. + -used_offset: used offset when the offsetted curves were generated + -stitch_distance: maximum allowed distance between two points + after sampling + -close_point: defines the beginning point for stitching + (stitching starts always from the undisplaced curve) + -offset_by_half: If true the resulting points are interlaced otherwise not. + Returnvalues: + -All offsetted curves connected to one spiral and sampled with + points obeying stitch_distance and offset_by_half + -Tag (origin) of each point to analyze why a point was + placed at this position + """ + + abs_offset = abs(used_offset) + if tree.is_leaf: + return LineStringSampling.raster_line_string_with_priority_points( + tree.val, + 0, + tree.val.length, + stitch_distance, + tree.transferred_point_priority_deque, + abs_offset, + offset_by_half, + False) + + result_coords = [] + result_coords_origin = [] + starting_point = close_point.coords[0] + # iterate to the second last level + for node in PreOrderIter(tree, stop=lambda n: n.is_leaf): + ring1 = node.val + ring2 = node.children[0].val + + part_spiral = interpolate_LinearRings( + ring1, ring2, starting_point) + + (own_coords, own_coords_origin) = LineStringSampling.raster_line_string_with_priority_points( + part_spiral, + 0, + part_spiral.length, + stitch_distance, + node.transferred_point_priority_deque, + abs_offset, + offset_by_half, + False) + + PointTransfer.transfer_points_to_surrounding( + node, + used_offset, + offset_by_half, + own_coords, + own_coords_origin, + overnext_neighbor=False, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=False, + transfer_to_child=True) + + # We transfer also to the overnext child to get a more straight + # arrangement of points perpendicular to the stitching lines + if offset_by_half: + PointTransfer.transfer_points_to_surrounding( + node, + used_offset, + False, + own_coords, + own_coords_origin, + overnext_neighbor=True, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=False, + transfer_to_child=True) + + result_coords.extend(own_coords) + result_coords_origin.extend(own_coords_origin) + + # make sure the next section starts where this + # section of the curve ends + starting_point = own_coords[-1] + + assert len(result_coords) == len(result_coords_origin) + return result_coords, result_coords_origin diff --git a/lib/stitches/LineStringSampling.py b/lib/stitches/LineStringSampling.py index bd20f55c..43f650e6 100644 --- a/lib/stitches/LineStringSampling.py +++ b/lib/stitches/LineStringSampling.py @@ -139,32 +139,35 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, angles[0] = 1.1*constants.limiting_angle angles[-1] = 1.1*constants.limiting_angle - current_distance = start_distance - + current_distance = 0 + last_point = Point(path_coords.coords[0]) # Next we merge the line points and the projected (deque) points into one list merged_point_list = [] dq_iter = 0 - for point, angle in zip(aligned_line.coords, angles): - # if abs(point[0]-52.9) < 0.2 and abs(point[1]-183.4)< 0.2: + for point, angle in zip(path_coords.coords, angles): + # if abs(point[0]-7) < 0.2 and abs(point[1]-3.3) < 0.2: # print("GEFUNDEN") - current_distance = aligned_line.project(Point(point)) - while dq_iter < len(deque_points) and deque_points[dq_iter][1] < current_distance: + current_distance += last_point.distance(Point(point)) + last_point = Point(point) + while dq_iter < len(deque_points) and deque_points[dq_iter][1] < current_distance+start_distance: # We want to avoid setting points at soft edges close to forbidden points if deque_points[dq_iter][0].point_source == PointSource.FORBIDDEN_POINT: # Check whether a previous added point is a soft edge close to the forbidden point if (merged_point_list[-1][0].point_source == PointSource.SOFT_EDGE_INTERNAL and - abs(merged_point_list[-1][1]-deque_points[dq_iter][1] < abs_offset*constants.factor_offset_forbidden_point)): + abs(merged_point_list[-1][1]-deque_points[dq_iter][1]+start_distance < abs_offset*constants.factor_offset_forbidden_point)): item = merged_point_list.pop() merged_point_list.append((PointTransfer.projected_point_tuple( - point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1])) + point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1]-start_distance)) else: - merged_point_list.append(deque_points[dq_iter]) + merged_point_list.append( + (deque_points[dq_iter][0], deque_points[dq_iter][1]-start_distance)) + # merged_point_list.append(deque_points[dq_iter]) dq_iter += 1 # Check whether the current point is close to a forbidden point if (dq_iter < len(deque_points) and deque_points[dq_iter-1][0].point_source == PointSource.FORBIDDEN_POINT and angle < constants.limiting_angle and - abs(deque_points[dq_iter-1][1]-current_distance) < abs_offset*constants.factor_offset_forbidden_point): + abs(deque_points[dq_iter-1][1]-current_distance-start_distance) < abs_offset*constants.factor_offset_forbidden_point): point_source = PointSource.FORBIDDEN_POINT else: if angle < constants.limiting_angle: diff --git a/lib/stitches/PointTransfer.py b/lib/stitches/PointTransfer.py index da73aea0..b6e4e026 100644 --- a/lib/stitches/PointTransfer.py +++ b/lib/stitches/PointTransfer.py @@ -9,12 +9,13 @@ from ..stitches import LineStringSampling projected_point_tuple = namedtuple( 'projected_point_tuple', ['point', 'point_source']) -# Calculated the nearest interserction point of "bisectorline" with the coordinates of child (child.val). -# It returns the intersection point and its distance along the coordinates of the child or "None, None" if no -# intersection was found. - def calc_transferred_point(bisectorline, child): + """ + Calculates the nearest interserction point of "bisectorline" with the coordinates of child (child.val). + It returns the intersection point and its distance along the coordinates of the child or "None, None" if no + intersection was found. + """ result = bisectorline.intersection(child.val) if result.is_empty: return None, None @@ -279,11 +280,10 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra assert(len(point_list) == len(point_source_list)) -# Calculated the nearest interserction point of "bisectorline" with the coordinates of child. + +# Calculates the nearest interserction point of "bisectorline" with the coordinates of child. # It returns the intersection point and its distance along the coordinates of the child or "None, None" if no # intersection was found. - - def calc_transferred_point_graph(bisectorline, edge_geometry): result = bisectorline.intersection(edge_geometry) if result.is_empty: diff --git a/lib/stitches/StitchPattern.py b/lib/stitches/StitchPattern.py index 1edfd452..62ef2b0f 100644 --- a/lib/stitches/StitchPattern.py +++ b/lib/stitches/StitchPattern.py @@ -1,8 +1,9 @@ +from anytree.render import RenderTree from shapely.geometry.polygon import LinearRing, LineString from shapely.geometry import Polygon, MultiLineString from shapely.ops import polygonize from shapely.geometry import MultiPolygon -from anytree import AnyNode, PreOrderIter +from anytree import AnyNode, PreOrderIter, LevelOrderGroupIter from shapely.geometry.polygon import orient from depq import DEPQ from enum import IntEnum @@ -126,6 +127,38 @@ class StitchingStrategy(IntEnum): SPIRAL = 2 +def check_and_prepare_tree_for_valid_spiral(root): + """ + Takes a tree consisting of offsetted curves. If a parent has more than one child we + cannot create a spiral. However, to make the routine more robust, we allow more than + one child if only one of the childs has own childs. The other childs are removed in this + routine then. If the routine returns true, the tree will have been cleaned up from unwanted + childs. If the routine returns false even under the mentioned weaker conditions the + tree cannot be connected by one spiral. + """ + for children in LevelOrderGroupIter(root): + if len(children) > 1: + count = 0 + child_with_children = None + for child in children: + if not child.is_leaf: + count += 1 + child_with_children = child + if count > 1: + return False + elif count == 1: + child_with_children.parent.children = [child_with_children] + else: # count == 0 means all childs have no children so we take only the longest child + max_length = 0 + longest_child = None + for child in children: + if child.val.length > max_length: + max_length = child.val.length + longest_child = child + longest_child.parent.children = [longest_child] + return True + + def offset_poly( poly, offset, join_style, stitch_distance, offset_by_half, strategy, starting_point): """ @@ -144,13 +177,21 @@ def offset_poly( -stitch_distance maximum allowed stitch distance between two points -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 + different strategies for the connection between parent and childs. In + addition it offers the option "SPIRAL" which creates a real spiral towards inner. + In contrast to the other two options, "SPIRAL" does not end at the starting point + but at the innermost point -starting_point: Defines the starting point for the stitching Output: -List of point coordinate tuples -Tag (origin) of each point to analyze why a point was placed at this position """ + + if strategy == StitchingStrategy.SPIRAL and len(poly.interiors) > 1: + raise ValueError( + "Single spiral geometry must not have more than one hole!") + ordered_poly = orient(poly, -1) ordered_poly = ordered_poly.simplify( constants.simplification_threshold, False) @@ -276,20 +317,105 @@ def offset_poly( make_tree_uniform_ccw(root) # print(RenderTree(root)) if strategy == StitchingStrategy.CLOSEST_POINT: - ( - connected_line, - connected_line_origin, - ) = ConnectAndSamplePattern.connect_raster_tree_nearest_neighbor( - root, offset, stitch_distance, starting_point, offset_by_half - ) + (connected_line, connected_line_origin) = ConnectAndSamplePattern.connect_raster_tree_nearest_neighbor( + root, offset, stitch_distance, starting_point, offset_by_half) elif strategy == StitchingStrategy.INNER_TO_OUTER: - ( - connected_line, - connected_line_origin, - ) = ConnectAndSamplePattern.connect_raster_tree_from_inner_to_outer( - root, offset, stitch_distance, starting_point, offset_by_half - ) + (connected_line, connected_line_origin) = ConnectAndSamplePattern.connect_raster_tree_from_inner_to_outer( + root, offset, 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) = ConnectAndSamplePattern.connect_raster_tree_spiral( + root, offset, stitch_distance, starting_point, offset_by_half) else: raise ValueError("Invalid stitching stratety!") return connected_line, connected_line_origin + + +if __name__ == "__main__": + line1 = LineString([(0, 0), (1, 0)]) + line2 = LineString([(0, 0), (3, 0)]) + + root = AnyNode( + id="root", + val=line1) + child1 = AnyNode( + id="node", + val=line1, + parent=root) + child2 = AnyNode( + id="node", + val=line1, + parent=root) + child3 = AnyNode( + id="node", + val=line2, + parent=root) + + print(RenderTree(root)) + print(check_and_prepare_tree_for_valid_spiral(root)) + print(RenderTree(root)) + print("---------------------------") + root = AnyNode( + id="root", + val=line1) + child1 = AnyNode( + id="node", + val=line1, + parent=root) + child2 = AnyNode( + id="node", + val=line1, + parent=root) + child3 = AnyNode( + id="node", + val=line2, + parent=child1) + print(RenderTree(root)) + print(check_and_prepare_tree_for_valid_spiral(root)) + print(RenderTree(root)) + + print("---------------------------") + root = AnyNode( + id="root", + val=line1) + child1 = AnyNode( + id="node", + val=line1, + parent=root) + child2 = AnyNode( + id="node", + val=line1, + parent=child1) + child3 = AnyNode( + id="node", + val=line2, + parent=child2) + print(RenderTree(root)) + print(check_and_prepare_tree_for_valid_spiral(root)) + print(RenderTree(root)) + + print("---------------------------") + root = AnyNode( + id="root", + val=line1) + child1 = AnyNode( + id="node", + val=line1, + parent=root) + child2 = AnyNode( + id="node", + val=line1, + parent=root) + child3 = AnyNode( + id="node", + val=line2, + parent=child1) + child4 = AnyNode( + id="node", + val=line2, + parent=child2) + print(RenderTree(root)) + print(check_and_prepare_tree_for_valid_spiral(root)) + print(RenderTree(root)) diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index 01bfdc20..5afcb228 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -7,7 +7,7 @@ import math import shapely from shapely.geometry.linestring import LineString -from shapely.ops import linemerge +from shapely.ops import linemerge, unary_union from ..svg import PIXELS_PER_MM from ..utils import Point as InkstitchPoint from ..utils import cache @@ -126,12 +126,34 @@ def repair_multiple_parallel_offset_curves(multi_line): return lines[max_length_idx].simplify(0.01, False) +def repair_non_simple_lines(line): + repaired = unary_union(line) + counter = 0 + # Do several iterations since we might have several concatenated selfcrossings + while repaired.geom_type != 'LineString' and counter < 4: + line_segments = [] + for line_seg in repaired.geoms: + if not line_seg.is_ring: + line_segments.append(line_seg) + + repaired = unary_union(linemerge(line_segments)) + counter += 1 + if repaired.geom_type != 'LineString': + raise ValueError( + "Guide line (or offsetted instance) is self crossing!") + else: + return repaired + + def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing=None, flip=False): row_spacing = abs(row_spacing) (minx, miny, maxx, maxy) = shape.bounds upper_left = InkstitchPoint(minx, miny) rows = [] + + if line.geom_type != 'LineString' or not line.is_simple: + line = repair_non_simple_lines(line) # extend the line towards the ends to increase probability that all offsetted curves cross the shape line = extend_line(line, minx, maxx, miny, maxy) @@ -160,6 +182,8 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing if line_offsetted.geom_type == 'MultiLineString': # if we got multiple lines take the longest line_offsetted = repair_multiple_parallel_offset_curves( line_offsetted) + if not line_offsetted.is_simple: + line_offsetted = repair_non_simple_lines(line_offsetted) if row_spacing < 0: line_offsetted.coords = line_offsetted.coords[::-1] @@ -173,6 +197,8 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing if line_offsetted.geom_type == 'MultiLineString': # if we got multiple lines take the longest line_offsetted = repair_multiple_parallel_offset_curves( line_offsetted) + if not line_offsetted.is_simple: + line_offsetted = repair_non_simple_lines(line_offsetted) # using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this line_offsetted.coords = line_offsetted.coords[::-1] line_offsetted = line_offsetted.simplify(0.01, False) diff --git a/requirements.txt b/requirements.txt index 309e1be6..09999307 100644 --- a/requirements.txt +++ b/requirements.txt @@ -21,6 +21,8 @@ flask fonttools anytree depq +trimesh +scipy pywinutils; sys.platform == 'win32' pywin32; sys.platform == 'win32' |