diff options
Diffstat (limited to 'lib/stitches')
| -rw-r--r-- | lib/stitches/ConnectAndSamplePattern.py | 834 | ||||
| -rw-r--r-- | lib/stitches/DebuggingMethods.py | 56 | ||||
| -rw-r--r-- | lib/stitches/LineStringSampling.py | 446 | ||||
| -rw-r--r-- | lib/stitches/PointTransfer.py | 277 | ||||
| -rw-r--r-- | lib/stitches/StitchPattern.py | 266 | ||||
| -rw-r--r-- | lib/stitches/auto_fill.py | 140 | ||||
| -rw-r--r-- | lib/stitches/constants.py | 53 | ||||
| -rw-r--r-- | lib/stitches/fill.py | 53 |
8 files changed, 1324 insertions, 801 deletions
diff --git a/lib/stitches/ConnectAndSamplePattern.py b/lib/stitches/ConnectAndSamplePattern.py index 21a56cd6..9b3572d9 100644 --- a/lib/stitches/ConnectAndSamplePattern.py +++ b/lib/stitches/ConnectAndSamplePattern.py @@ -1,6 +1,6 @@ from shapely.geometry.polygon import LineString, LinearRing -from shapely.geometry import Point, MultiPoint, linestring -from shapely.ops import nearest_points, polygonize +from shapely.geometry import Point, MultiPoint +from shapely.ops import nearest_points from collections import namedtuple from depq import DEPQ import math @@ -8,11 +8,22 @@ from ..stitches import LineStringSampling from ..stitches import PointTransfer from ..stitches import constants -nearest_neighbor_tuple = namedtuple('nearest_neighbor_tuple', ['nearest_point_parent', 'nearest_point_child', 'projected_distance_parent', 'child_node']) +nearest_neighbor_tuple = namedtuple( + "nearest_neighbor_tuple", + [ + "nearest_point_parent", + "nearest_point_child", + "proj_distance_parent", + "child_node", + ], +) -# Cuts a closed line so that the new closed line starts at the point with "distance" to the beginning of the old line. def cut(line, distance): + """ + Cuts a closed line so that the new closed line starts at the + point with "distance" to the beginning of the old line. + """ if distance <= 0.0 or distance >= line.length: return [LineString(line)] coords = list(line.coords) @@ -23,29 +34,41 @@ def cut(line, distance): pd = line.project(Point(p)) if pd == distance: if coords[0] == coords[-1]: - return LineString(coords[i:]+coords[1:i+1]) + return LineString(coords[i:] + coords[1: i + 1]) else: - return LineString(coords[i:]+coords[:i]) + return LineString(coords[i:] + coords[:i]) if pd > distance: cp = line.interpolate(distance) if coords[0] == coords[-1]: - return LineString([(cp.x, cp.y)] + coords[i:]+coords[1:i]+[(cp.x, cp.y)]) + return LineString( + [(cp.x, cp.y)] + coords[i:] + coords[1:i] + [(cp.x, cp.y)] + ) else: - return LineString([(cp.x, cp.y)] + coords[i:]+coords[:i]) - - -#Takes the offsetted curves organized as tree, connects and samples them. -#Strategy: A connection from parent to child is made where both curves come closest together. -#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 line and sampled with points obeying stitch_distance and offset_by_half -#-Tag (origin) of each point to analyze why a point was placed at this position -def connect_raster_tree_nearest_neighbor(tree, used_offset, stitch_distance, close_point, offset_by_half): + return LineString([(cp.x, cp.y)] + coords[i:] + coords[:i]) + + +def connect_raster_tree_nearest_neighbor( + 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 + come closest together. + 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 line and sampled with + points obeying stitch_distance and offset_by_half + -Tag (origin) of each point to analyze why a point was + placed at this position + """ current_coords = tree.val abs_offset = abs(used_offset) @@ -60,176 +83,285 @@ def connect_raster_tree_nearest_neighbor(tree, used_offset, stitch_distance, clo if not tree.transferred_point_priority_deque.is_empty(): new_DEPQ = DEPQ(iterable=None, maxlen=None) - for item,priority in tree.transferred_point_priority_deque: - new_DEPQ.insert(item, math.fmod( - priority-start_distance+current_coords.length, current_coords.length)) + for item, priority in tree.transferred_point_priority_deque: + new_DEPQ.insert( + item, + math.fmod( + priority - start_distance + current_coords.length, + current_coords.length, + ), + ) tree.transferred_point_priority_deque = new_DEPQ - #print("Gecutted") stitching_direction = 1 - # This list should contain a tuple of nearest points between the current geometry - # and the subgeometry, the projected distance along the current geometry, - # and the belonging subtree node + # This list should contain a tuple of nearest points between + # the current geometry and the subgeometry, the projected + # distance along the current geometry, and the belonging subtree node nearest_points_list = [] - + for subnode in tree.children: point_parent, point_child = nearest_points(current_coords, subnode.val) proj_distance = current_coords.project(point_parent) - nearest_points_list.append(nearest_neighbor_tuple(nearest_point_parent = point_parent, - nearest_point_child = point_child, - projected_distance_parent = proj_distance, - child_node=subnode)) - nearest_points_list.sort(reverse=False, key=lambda tup: tup.projected_distance_parent) + nearest_points_list.append( + nearest_neighbor_tuple( + nearest_point_parent=point_parent, + nearest_point_child=point_child, + proj_distance_parent=proj_distance, + child_node=subnode, + ) + ) + nearest_points_list.sort( + reverse=False, key=lambda tup: tup.proj_distance_parent) if nearest_points_list: - start_distance = min(abs_offset*constants.factor_offset_starting_points, nearest_points_list[0].projected_distance_parent) - end_distance = max(current_coords.length-abs_offset*constants.factor_offset_starting_points, nearest_points_list[-1].projected_distance_parent) + start_distance = min( + abs_offset * constants.factor_offset_starting_points, + nearest_points_list[0].proj_distance_parent, + ) + end_distance = max( + current_coords.length + - abs_offset * constants.factor_offset_starting_points, + nearest_points_list[-1].proj_distance_parent, + ) else: - start_distance = abs_offset*constants.factor_offset_starting_points - end_distance = current_coords.length-abs_offset*constants.factor_offset_starting_points - - own_coords, own_coords_origin = LineStringSampling.raster_line_string_with_priority_points(current_coords, start_distance, # We add/subtract an offset to not sample the same point again (avoid double points for start and end) - end_distance, stitch_distance, stitching_direction, tree.transferred_point_priority_deque, abs_offset) - assert(len(own_coords) == len(own_coords_origin)) + start_distance = abs_offset * constants.factor_offset_starting_points + end_distance = ( + current_coords.length - abs_offset * constants.factor_offset_starting_points + ) + + ( + own_coords, + own_coords_origin, + ) = LineStringSampling.raster_line_string_with_priority_points( + current_coords, + start_distance, # We add/subtract an offset to not sample + # the same point again (avoid double + # points for start and end) + end_distance, + stitch_distance, + stitching_direction, + tree.transferred_point_priority_deque, + abs_offset, + ) + assert len(own_coords) == len(own_coords_origin) own_coords_origin[0] = LineStringSampling.PointSource.ENTER_LEAVING_POINT own_coords_origin[-1] = LineStringSampling.PointSource.ENTER_LEAVING_POINT - - #tree.val = LineString(own_coords) - #tree.pointsourcelist = own_coords_origin tree.stitching_direction = stitching_direction tree.already_rastered = True - #Next we need to transfer our rastered points to siblings and childs + # Next we need to transfer our rastered points to siblings and childs to_transfer_point_list = [] to_transfer_point_list_origin = [] - for k in range(1, len(own_coords)-1): #Do not take the first and the last since they are ENTER_LEAVING_POINT points for sure - # if abs(temp[k][0]-5.25) < 0.5 and abs(temp[k][1]-42.9) < 0.5: - # print("HIER gefunden!") - if (not offset_by_half and own_coords_origin[k] == LineStringSampling.PointSource.EDGE_NEEDED): + for k in range(1, len(own_coords) - 1): + # Do not take the first and the last since they are ENTER_LEAVING_POINT + # points for sure + + if ( + not offset_by_half + and own_coords_origin[k] == LineStringSampling.PointSource.EDGE_NEEDED + ): continue - if own_coords_origin[k] == LineStringSampling.PointSource.ENTER_LEAVING_POINT or own_coords_origin[k] == LineStringSampling.PointSource.FORBIDDEN_POINT: + if ( + own_coords_origin[k] == LineStringSampling.PointSource.ENTER_LEAVING_POINT + or own_coords_origin[k] == LineStringSampling.PointSource.FORBIDDEN_POINT + ): continue to_transfer_point_list.append(Point(own_coords[k])) - point_origin = own_coords_origin[k] + point_origin = own_coords_origin[k] to_transfer_point_list_origin.append(point_origin) - - #since the projection is only in ccw direction towards inner we need to use "-used_offset" for stitching_direction==-1 - PointTransfer.transfer_points_to_surrounding(tree,stitching_direction*used_offset,offset_by_half,stitch_distance, - to_transfer_point_list,to_transfer_point_list_origin,overnext_neighbor=False, - transfer_forbidden_points=False,transfer_to_parent=False,transfer_to_sibling=True,transfer_to_child=True) - - - #We transfer also to the overnext child to get a more straight arrangement of points perpendicular to the stitching lines + # Since the projection is only in ccw direction towards inner we need + # to use "-used_offset" for stitching_direction==-1 + PointTransfer.transfer_points_to_surrounding( + tree, + stitching_direction * used_offset, + offset_by_half, + to_transfer_point_list, + to_transfer_point_list_origin, + overnext_neighbor=False, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=True, + 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(tree,stitching_direction*used_offset,False,stitch_distance, - to_transfer_point_list,to_transfer_point_list_origin,overnext_neighbor=True, - transfer_forbidden_points=False,transfer_to_parent=False,transfer_to_sibling=True,transfer_to_child=True) + PointTransfer.transfer_points_to_surrounding( + tree, + stitching_direction * used_offset, + False, + to_transfer_point_list, + to_transfer_point_list_origin, + overnext_neighbor=True, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=True, + transfer_to_child=True, + ) if not nearest_points_list: - #If there is no child (inner geometry) we can simply take our own rastered coords as result + # If there is no child (inner geometry) we can simply take + # our own rastered coords as result result_coords = own_coords result_coords_origin = own_coords_origin else: - #There are childs so we need to merge their coordinates with our own rastered coords + # There are childs so we need to merge their coordinates + + # with our own rastered coords - #To create a closed ring + # To create a closed ring own_coords.append(own_coords[0]) own_coords_origin.append(own_coords_origin[0]) - - #own_coords does not start with current_coords but has an offset (see call of raster_line_string_with_priority_points) + # own_coords does not start with current_coords but has an offset + # (see call of raster_line_string_with_priority_points) total_distance = start_distance - current_item_index = 0 + cur_item = 0 result_coords = [own_coords[0]] - result_coords_origin = [LineStringSampling.PointSource.ENTER_LEAVING_POINT] + result_coords_origin = [ + LineStringSampling.PointSource.ENTER_LEAVING_POINT] for i in range(1, len(own_coords)): - next_distance = math.sqrt((own_coords[i][0]-own_coords[i-1][0])**2 + - (own_coords[i][1]-own_coords[i-1][1])**2) - while (current_item_index < len(nearest_points_list) and - total_distance+next_distance+constants.eps > nearest_points_list[current_item_index].projected_distance_parent): - - item = nearest_points_list[current_item_index] - child_coords, child_coords_origin = connect_raster_tree_nearest_neighbor( - item.child_node, used_offset, stitch_distance, item.nearest_point_child, offset_by_half) - - delta = item.nearest_point_parent.distance(Point(own_coords[i-1])) - if delta > abs_offset*constants.factor_offset_starting_points: + next_distance = math.sqrt( + (own_coords[i][0] - own_coords[i - 1][0]) ** 2 + + (own_coords[i][1] - own_coords[i - 1][1]) ** 2 + ) + while ( + cur_item < len(nearest_points_list) + and total_distance + next_distance + constants.eps + > nearest_points_list[cur_item].proj_distance_parent + ): + + item = nearest_points_list[cur_item] + ( + child_coords, + child_coords_origin, + ) = connect_raster_tree_nearest_neighbor( + item.child_node, + used_offset, + stitch_distance, + item.nearest_point_child, + offset_by_half, + ) + + d = item.nearest_point_parent.distance( + Point(own_coords[i - 1])) + if d > abs_offset * constants.factor_offset_starting_points: result_coords.append(item.nearest_point_parent.coords[0]) - result_coords_origin.append(LineStringSampling.PointSource.ENTER_LEAVING_POINT) - # reversing avoids crossing when entering and leaving the child segment + result_coords_origin.append( + LineStringSampling.PointSource.ENTER_LEAVING_POINT + ) + # reversing avoids crossing when entering and + # leaving the child segment result_coords.extend(child_coords[::-1]) result_coords_origin.extend(child_coords_origin[::-1]) - - #And here we calculate the point for the leaving - delta = item.nearest_point_parent.distance(Point(own_coords[i])) - if current_item_index < len(nearest_points_list)-1: - delta = min(delta, abs( - nearest_points_list[current_item_index+1].projected_distance_parent-item.projected_distance_parent)) - - if delta > abs_offset*constants.factor_offset_starting_points: - result_coords.append(current_coords.interpolate( - item.projected_distance_parent+abs_offset*constants.factor_offset_starting_points).coords[0]) - result_coords_origin.append(LineStringSampling.PointSource.ENTER_LEAVING_POINT) - - current_item_index += 1 - if i < len(own_coords)-1: - if(Point(result_coords[-1]).distance(Point(own_coords[i])) > abs_offset*constants.factor_offset_remove_points): + # And here we calculate the point for the leaving + d = item.nearest_point_parent.distance(Point(own_coords[i])) + 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 + ), + ) + + if d > abs_offset * constants.factor_offset_starting_points: + result_coords.append( + current_coords.interpolate( + item.proj_distance_parent + + abs_offset * constants.factor_offset_starting_points + ).coords[0] + ) + result_coords_origin.append( + LineStringSampling.PointSource.ENTER_LEAVING_POINT + ) + + cur_item += 1 + if i < len(own_coords) - 1: + if ( + Point(result_coords[-1]).distance(Point(own_coords[i])) + > abs_offset * constants.factor_offset_remove_points + ): result_coords.append(own_coords[i]) result_coords_origin.append(own_coords_origin[i]) - # Since current_coords and temp are rastered differently there accumulate errors regarding the current distance. - # Since a projection of each point in temp would be very time consuming we project only every n-th point which resets the accumulated error every n-th point. + # Since current_coords and temp are rastered differently + # there accumulate errors regarding the current distance. + # Since a projection of each point in temp would be very time + # consuming we project only every n-th point which resets + # the accumulated error every n-th point. if i % 20 == 0: total_distance = current_coords.project(Point(own_coords[i])) else: total_distance += next_distance - assert(len(result_coords) == len(result_coords_origin)) + assert len(result_coords) == len(result_coords_origin) return result_coords, result_coords_origin -#Takes a line and calculates the nearest distance along this line to enter the 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 -#-thresh: The distance between travel_line and next_line needs to below thresh to be a valid point for entering -#Output: -#-tuple - the tuple structure is: (nearest point in travel_line, nearest point in next_line) -def get_nearest_points_closer_than_thresh(travel_line, next_line,thresh): - point_list = list(MultiPoint(travel_line.coords)) + +def get_nearest_points_closer_than_thresh(travel_line, next_line, thresh): + """ + Takes a line and calculates the nearest distance along this + line to enter the 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 + -thresh: The distance between travel_line and next_line needs + to below thresh to be a valid point for entering + Output: + -tuple - the tuple structure is: + (nearest point in travel_line, nearest point in next_line) + """ + point_list = list(MultiPoint(travel_line.coords)) if point_list[0].distance(next_line) < thresh: return nearest_points(point_list[0], next_line) - for i in range(len(point_list)-1): - line_segment = LineString([point_list[i], point_list[i+1]]) - result = nearest_points(line_segment,next_line) + for i in range(len(point_list) - 1): + line_segment = LineString([point_list[i], point_list[i + 1]]) + result = nearest_points(line_segment, next_line) - if result[0].distance(result[1])< thresh: + if result[0].distance(result[1]) < thresh: return result line_segment = LineString([point_list[-1], point_list[0]]) - result = nearest_points(line_segment,next_line) + result = nearest_points(line_segment, next_line) - if result[0].distance(result[1])< thresh: + if result[0].distance(result[1]) < thresh: return result else: return None -#Takes a line and calculates the nearest distance along this line to enter the childs in children_list -#The method calculates the distances along the line and along the reversed line to find the best direction -#which minimizes the overall distance for all childs. -#Input: -#-travel_line: The "parent" line for which the distance should be minimized to enter the childs -#-children_list: contains the childs of travel_line which need to be entered -#-threshold: The distance between travel_line and a child needs to below threshold to be a valid point for entering -#-preferred_direction: Put a bias on the desired travel direction along travel_line. If equals zero no bias is applied. -# preferred_direction=1 means we prefer the direction of travel_line; preferred_direction=-1 means we prefer the opposite direction. -#Output: -#-stitching direction for travel_line -#-list of tuples (one tuple per child). The tuple structure is: ((nearest point in travel_line, nearest point in child), distance along travel_line, belonging child) -def create_nearest_points_list(travel_line, children_list, threshold, threshold_hard,preferred_direction=0): +def create_nearest_points_list( + 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 + The method calculates the distances along the line and along the + reversed line to find the best direction which minimizes the overall + distance for all childs. + Input: + -travel_line: The "parent" line for which the distance should + be minimized to enter the childs + -children_list: contains the childs of travel_line which need to be entered + -threshold: The distance between travel_line and a child needs to be + below threshold to be a valid point for entering + -preferred_direction: Put a bias on the desired travel direction along + travel_line. If equals zero no bias is applied. + preferred_direction=1 means we prefer the direction of travel_line; + preferred_direction=-1 means we prefer the opposite direction. + Output: + -stitching direction for travel_line + -list of tuples (one tuple per child). The tuple structure is: + ((nearest point in travel_line, nearest point in child), + distance along travel_line, belonging child) + """ + result_list_in_order = [] result_list_reversed_order = [] @@ -238,67 +370,113 @@ def create_nearest_points_list(travel_line, children_list, threshold, threshold_ weight_in_order = 0 weight_reversed_order = 0 for child in children_list: - result = get_nearest_points_closer_than_thresh(travel_line, child.val, threshold) - if result == None: #where holes meet outer borders a distance up to 2*used offset can arise - result = get_nearest_points_closer_than_thresh(travel_line, child.val, threshold_hard) - assert(result != None) + result = get_nearest_points_closer_than_thresh( + travel_line, 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, child.val, threshold_hard + ) + assert result is not None proj = travel_line.project(result[0]) weight_in_order += proj - result_list_in_order.append(nearest_neighbor_tuple(nearest_point_parent = result[0], - nearest_point_child = result[1], - projected_distance_parent = proj, - child_node = child)) - - result = get_nearest_points_closer_than_thresh(travel_line_reversed, child.val, threshold) - if result == None: #where holes meet outer borders a distance up to 2*used offset can arise - result = get_nearest_points_closer_than_thresh(travel_line_reversed, child.val, threshold_hard) - assert(result != None) + result_list_in_order.append( + nearest_neighbor_tuple( + nearest_point_parent=result[0], + nearest_point_child=result[1], + proj_distance_parent=proj, + child_node=child, + ) + ) + + result = get_nearest_points_closer_than_thresh( + travel_line_reversed, 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_reversed, child.val, threshold_hard + ) + assert result is not None proj = travel_line_reversed.project(result[0]) weight_reversed_order += proj - result_list_reversed_order.append(nearest_neighbor_tuple(nearest_point_parent = result[0], - nearest_point_child = result[1], - projected_distance_parent = proj, - child_node = child)) + result_list_reversed_order.append( + nearest_neighbor_tuple( + nearest_point_parent=result[0], + nearest_point_child=result[1], + proj_distance_parent=proj, + child_node=child, + ) + ) if preferred_direction == 1: - weight_in_order=min(weight_in_order/2, max(0, weight_in_order-10*threshold)) + # Reduce weight_in_order to make in order stitching more preferred + weight_in_order = min( + weight_in_order / 2, max(0, weight_in_order - 10 * threshold) + ) if weight_in_order == weight_reversed_order: return (1, result_list_in_order) elif preferred_direction == -1: - weight_reversed_order=min(weight_reversed_order/2, max(0, weight_reversed_order-10*threshold)) + # Reduce weight_reversed_order to make reversed + # stitching more preferred + weight_reversed_order = min( + weight_reversed_order / + 2, max(0, weight_reversed_order - 10 * threshold) + ) if weight_in_order == weight_reversed_order: return (-1, result_list_reversed_order) - if weight_in_order < weight_reversed_order: return (1, result_list_in_order) else: return (-1, result_list_reversed_order) -def calculate_replacing_middle_point(line_segment, abs_offset,max_stich_distance): +def calculate_replacing_middle_point(line_segment, abs_offset, max_stitch_distance): + """ + Takes a line segment (consisting of 3 points!) + and calculates a new middle point if the line_segment is + straight enough to be resampled by points max_stitch_distance apart. + Returns None if the middle point is not needed. + """ angles = LineStringSampling.calculate_line_angles(line_segment) - if angles[1] < abs_offset*constants.limiting_angle_straight: - if line_segment.length < max_stich_distance: + if angles[1] < abs_offset * constants.limiting_angle_straight: + if line_segment.length < max_stitch_distance: return None else: - return line_segment.interpolate(line_segment.length-max_stich_distance).coords[0] + return line_segment.interpolate( + line_segment.length - max_stitch_distance + ).coords[0] else: return line_segment.coords[1] -#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 reach the innermost child as fast as possible in order -# to stich afterwards from inner to outer. -#Input: -#-tree: contains the offsetted curves in a hierachical organized data structure. -#-used_offset: used offset when the offsetted curves were generated -#-stitch_distance: maximum allowed distance between two points after sampling -#-close_point: defines the beginning point for stitching (stitching starts always from the undisplaced curve) -#-offset_by_half: If true the resulting points are interlaced otherwise not. -#Returnvalues: -#-All offsetted curves connected to one line and sampled with points obeying stitch_distance and offset_by_half -#-Tag (origin) of each point to analyze why a point was placed at this position -def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, close_point, offset_by_half): + +def connect_raster_tree_from_inner_to_outer( + 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 + reach the innermost child as fast as possible in order to stitch afterwards + from inner to outer. + Input: + -tree: contains the offsetted curves in a hierachical organized + data structure. + -used_offset: used offset when the offsetted curves were generated + -stitch_distance: maximum allowed distance between two points + after sampling + -close_point: defines the beginning point for stitching + (stitching starts always from the undisplaced curve) + -offset_by_half: If true the resulting points are interlaced otherwise not. + Returnvalues: + -All offsetted curves connected to one line and sampled with points obeying + stitch_distance and offset_by_half + -Tag (origin) of each point to analyze why a point was placed + at this position + """ current_coords = tree.val abs_offset = abs(used_offset) @@ -314,164 +492,280 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, if not tree.transferred_point_priority_deque.is_empty(): new_DEPQ = DEPQ(iterable=None, maxlen=None) for item, priority in tree.transferred_point_priority_deque: - new_DEPQ.insert(item, math.fmod( - priority-start_distance+current_coords.length, current_coords.length)) + new_DEPQ.insert( + item, + math.fmod( + priority - start_distance + current_coords.length, + current_coords.length, + ), + ) tree.transferred_point_priority_deque = new_DEPQ - #We try to use always the opposite stitching direction with respect to the parent to avoid crossings when entering and leaving the child + # We try to use always the opposite stitching direction with respect to the + # parent to avoid crossings when entering and leaving the child parent_stitching_direction = -1 - if tree.parent != None: + if tree.parent is not None: parent_stitching_direction = tree.parent.stitching_direction - #find the nearest point in current_coords and its children and sort it along the stitching direction - stitching_direction, nearest_points_list = create_nearest_points_list(current_coords, tree.children, 1.5*abs_offset,2.05*abs_offset,parent_stitching_direction) - nearest_points_list.sort(reverse=False, key=lambda tup: tup.projected_distance_parent) - - #Have a small offset for the starting and ending to avoid double points at start and end point (since the paths are closed rings) + # Find the nearest point in current_coords and its children and + # sort it along the stitching direction + stitching_direction, nearest_points_list = create_nearest_points_list( + current_coords, + tree.children, + 1.5 * abs_offset, + 2.05 * abs_offset, + parent_stitching_direction, + ) + nearest_points_list.sort( + reverse=False, key=lambda tup: tup.proj_distance_parent) + + # Have a small offset for the starting and ending to avoid double points + # at start and end point (since the paths are closed rings) if nearest_points_list: - start_offset = min(abs_offset*constants.factor_offset_starting_points, nearest_points_list[0].projected_distance_parent) - end_offset = max(current_coords.length-abs_offset*constants.factor_offset_starting_points, nearest_points_list[-1].projected_distance_parent) + start_offset = min( + abs_offset * constants.factor_offset_starting_points, + nearest_points_list[0].proj_distance_parent, + ) + end_offset = max( + current_coords.length + - abs_offset * constants.factor_offset_starting_points, + nearest_points_list[-1].proj_distance_parent, + ) else: - start_offset = abs_offset*constants.factor_offset_starting_points - end_offset = current_coords.length-abs_offset*constants.factor_offset_starting_points - + start_offset = abs_offset * constants.factor_offset_starting_points + end_offset = ( + current_coords.length - abs_offset * constants.factor_offset_starting_points + ) if stitching_direction == 1: - own_coords, own_coords_origin = LineStringSampling.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 and end) - end_offset, stitch_distance, stitching_direction, tree.transferred_point_priority_deque, abs_offset) + ( + own_coords, + own_coords_origin, + ) = LineStringSampling.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 + # and end) + end_offset, + stitch_distance, + stitching_direction, + tree.transferred_point_priority_deque, + abs_offset, + ) else: - own_coords, own_coords_origin = LineStringSampling.raster_line_string_with_priority_points(current_coords, current_coords.length-start_offset, # We subtract start_offset to not sample the same point again (avoid double points for start and end) - current_coords.length-end_offset, stitch_distance, stitching_direction, tree.transferred_point_priority_deque, abs_offset) - current_coords.coords = current_coords.coords[::-1] - - #Adjust the points origin for start and end (so that they might not be transferred to childs) - #if own_coords_origin[-1] != LineStringSampling.PointSource.HARD_EDGE: - # own_coords_origin[-1] = LineStringSampling.PointSource.ENTER_LEAVING_POINT - #if own_coords_origin[0] != LineStringSampling.PointSource.HARD_EDGE: - # own_coords_origin[0] = LineStringSampling.PointSource.ENTER_LEAVING_POINT - assert(len(own_coords) == len(own_coords_origin)) - - #tree.val = LineString(own_coords) - #tree.pointsourcelist = own_coords_origin + ( + own_coords, + own_coords_origin, + ) = LineStringSampling.raster_line_string_with_priority_points( + current_coords, + current_coords.length - start_offset, # We subtract + # start_offset to not + # sample the same point + # again (avoid double + # points for start + # and end) + current_coords.length - end_offset, + stitch_distance, + stitching_direction, + tree.transferred_point_priority_deque, + abs_offset, + ) + current_coords.coords = current_coords.coords[::-1] + + assert len(own_coords) == len(own_coords_origin) + tree.stitching_direction = stitching_direction tree.already_rastered = True - to_transfer_point_list = [] to_transfer_point_list_origin = [] - for k in range(0, len(own_coords)): #TODO: maybe do not take the first and the last since they are ENTER_LEAVING_POINT points for sure - if (not offset_by_half and own_coords_origin[k] == LineStringSampling.PointSource.EDGE_NEEDED or own_coords_origin[k] == LineStringSampling.PointSource.FORBIDDEN_POINT): + for k in range(0, len(own_coords)): + # TODO: maybe do not take the first and the last + # since they are ENTER_LEAVING_POINT points for sure + if ( + not offset_by_half + and own_coords_origin[k] == LineStringSampling.PointSource.EDGE_NEEDED + or own_coords_origin[k] == LineStringSampling.PointSource.FORBIDDEN_POINT + ): continue if own_coords_origin[k] == LineStringSampling.PointSource.ENTER_LEAVING_POINT: continue to_transfer_point_list.append(Point(own_coords[k])) to_transfer_point_list_origin.append(own_coords_origin[k]) - assert(len(to_transfer_point_list) == len(to_transfer_point_list_origin)) - - - #Next we need to transfer our rastered points to siblings and childs - - - #since the projection is only in ccw direction towards inner we need to use "-used_offset" for stitching_direction==-1 - PointTransfer.transfer_points_to_surrounding(tree,stitching_direction*used_offset,offset_by_half,stitch_distance, - to_transfer_point_list,to_transfer_point_list_origin,overnext_neighbor=False, - transfer_forbidden_points=False,transfer_to_parent=False,transfer_to_sibling=True,transfer_to_child=True) - - - #We transfer also to the overnext child to get a more straight arrangement of points perpendicular to the stitching lines + assert len(to_transfer_point_list) == len(to_transfer_point_list_origin) + + # Next we need to transfer our rastered points to siblings and childs + # Since the projection is only in ccw direction towards inner we + # need to use "-used_offset" for stitching_direction==-1 + PointTransfer.transfer_points_to_surrounding( + tree, + stitching_direction * used_offset, + offset_by_half, + to_transfer_point_list, + to_transfer_point_list_origin, + overnext_neighbor=False, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=True, + 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(tree,stitching_direction*used_offset,False,stitch_distance, - to_transfer_point_list,to_transfer_point_list_origin,overnext_neighbor=True, - transfer_forbidden_points=False,transfer_to_parent=False,transfer_to_sibling=True,transfer_to_child=True) - + PointTransfer.transfer_points_to_surrounding( + tree, + stitching_direction * used_offset, + False, + to_transfer_point_list, + to_transfer_point_list_origin, + overnext_neighbor=True, + transfer_forbidden_points=False, + transfer_to_parent=False, + transfer_to_sibling=True, + transfer_to_child=True, + ) + if not nearest_points_list: - #If there is no child (inner geometry) we can simply take our own rastered coords as result + # If there is no child (inner geometry) we can simply + # take our own rastered coords as result result_coords = own_coords result_coords_origin = own_coords_origin else: - #There are childs so we need to merge their coordinates with our own rastered coords + # There are childs so we need to merge their coordinates + # with our own rastered coords - #Create a closed ring for the following code + # Create a closed ring for the following code own_coords.append(own_coords[0]) own_coords_origin.append(own_coords_origin[0]) - # own_coords does not start with current_coords but has an offset (see call of raster_line_string_with_priority_points) + # own_coords does not start with current_coords but has an offset + # (see call of raster_line_string_with_priority_points) total_distance = start_offset - current_item_index = 0 + cur_item = 0 result_coords = [own_coords[0]] result_coords_origin = [own_coords_origin[0]] for i in range(1, len(own_coords)): - next_distance = math.sqrt((own_coords[i][0]-own_coords[i-1][0])**2 + - (own_coords[i][1]-own_coords[i-1][1])**2) - while (current_item_index < len(nearest_points_list) and - total_distance+next_distance+constants.eps > nearest_points_list[current_item_index].projected_distance_parent): - #The current and the next point in own_coords enclose the nearest point tuple between this geometry and the child geometry. - #Hence we need to insert the child geometry points here before the next point of own_coords. - item = nearest_points_list[current_item_index] - child_coords, child_coords_origin = connect_raster_tree_from_inner_to_outer( - item.child_node, used_offset, stitch_distance, item.nearest_point_child, offset_by_half) - - #Imagine the nearest point of the child is within a long segment of the parent. Without additonal points - #on the parent side this would cause noticeable deviations. Hence we add here points shortly before and after - #the entering of the child to have only minor deviations to the desired shape. - #Here is the point for the entering: - if(Point(result_coords[-1]).distance(item.nearest_point_parent) > constants.factor_offset_starting_points*abs_offset): + next_distance = math.sqrt( + (own_coords[i][0] - own_coords[i - 1][0]) ** 2 + + (own_coords[i][1] - own_coords[i - 1][1]) ** 2 + ) + while ( + cur_item < len(nearest_points_list) + and total_distance + next_distance + constants.eps + > nearest_points_list[cur_item].proj_distance_parent + ): + # The current and the next point in own_coords enclose the + # nearest point tuple between this geometry and child + # geometry. Hence we need to insert the child geometry points + # here before the next point of own_coords. + item = nearest_points_list[cur_item] + ( + child_coords, + child_coords_origin, + ) = connect_raster_tree_from_inner_to_outer( + item.child_node, + used_offset, + stitch_distance, + item.nearest_point_child, + offset_by_half, + ) + + # Imagine the nearest point of the child is within a long + # segment of the parent. Without additonal points + # on the parent side this would cause noticeable deviations. + # Hence we add here points shortly before and after + # the entering of the child to have only minor deviations to + # the desired shape. + # Here is the point for the entering: + if ( + Point(result_coords[-1] + ).distance(item.nearest_point_parent) + > constants.factor_offset_starting_points * abs_offset + ): result_coords.append(item.nearest_point_parent.coords[0]) - result_coords_origin.append(LineStringSampling.PointSource.ENTER_LEAVING_POINT) - #if (abs(result_coords[-1][0]-61.7) < 0.2 and abs(result_coords[-1][1]-105.1) < 0.2): - # print("HIIER FOUNDED3") - - #Check whether the number of points of the connecting lines from child to child can be reduced + result_coords_origin.append( + LineStringSampling.PointSource.ENTER_LEAVING_POINT + ) + + # Check whether the number of points of the connecting lines + # from child to child can be reduced if len(child_coords) > 1: - point = calculate_replacing_middle_point(LineString([result_coords[-1],child_coords[0],child_coords[1]]),abs_offset,stitch_distance) - #if (abs(result_coords[-1][0]-8.9) < 0.2 and abs(result_coords[-1][1]-8.9) < 0.2): - # print("HIIER FOUNDED3") - if point != None: - #if (abs(point[0]-17.8) < 0.2 and abs(point[1]-17.8) < 0.2): - # print("HIIER FOUNDED3") + point = calculate_replacing_middle_point( + LineString( + [result_coords[-1], child_coords[0], child_coords[1]] + ), + abs_offset, + stitch_distance, + ) + + if point is not None: result_coords.append(point) result_coords_origin.append(child_coords_origin[0]) - + result_coords.extend(child_coords[1:]) result_coords_origin.extend(child_coords_origin[1:]) else: result_coords.extend(child_coords) result_coords_origin.extend(child_coords_origin) - #And here is the point for the leaving of the child (distance to the own following point should not be too large) - delta = item.nearest_point_parent.distance(Point(own_coords[i])) - if current_item_index < len(nearest_points_list)-1: - delta = min(delta, abs( - nearest_points_list[current_item_index+1].projected_distance_parent-item.projected_distance_parent)) - - if delta > constants.factor_offset_starting_points*abs_offset: - result_coords.append(current_coords.interpolate( - item.projected_distance_parent+2*constants.factor_offset_starting_points*abs_offset).coords[0]) - result_coords_origin.append(LineStringSampling.PointSource.ENTER_LEAVING_POINT) - #check whether this additional point makes the last point of the child unnecessary - point = calculate_replacing_middle_point(LineString([result_coords[-3],result_coords[-2],result_coords[-1]]),abs_offset,stitch_distance) - if point == None: + # And here is the point for the leaving of the child + # (distance to the own following point should not be too large) + d = item.nearest_point_parent.distance(Point(own_coords[i])) + 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 + ), + ) + + 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] + ) + result_coords_origin.append( + LineStringSampling.PointSource.ENTER_LEAVING_POINT + ) + # Check whether this additional point makes the last point + # of the child unnecessary + point = calculate_replacing_middle_point( + LineString( + [result_coords[-3], result_coords[-2], result_coords[-1]] + ), + abs_offset, + stitch_distance, + ) + if point is None: result_coords.pop(-2) result_coords_origin.pop(-2) - #if (abs(result_coords[-1][0]-61.7) < 0.2 and abs(result_coords[-1][1]-105.1) < 0.2): - # print("HIIER FOUNDED3") - - current_item_index += 1 - if i < len(own_coords)-1: - if(Point(result_coords[-1]).distance(Point(own_coords[i])) > abs_offset*constants.factor_offset_remove_points): + cur_item += 1 + if i < len(own_coords) - 1: + if ( + Point(result_coords[-1]).distance(Point(own_coords[i])) + > abs_offset * constants.factor_offset_remove_points + ): result_coords.append(own_coords[i]) result_coords_origin.append(own_coords_origin[i]) - # Since current_coords and own_coords are rastered differently there accumulate errors regarding the current distance. - # Since a projection of each point in own_coords would be very time consuming we project only every n-th point which resets the accumulated error every n-th point. + # Since current_coords and own_coords are rastered differently + # there accumulate errors regarding the current distance. + # Since a projection of each point in own_coords would be very + # time consuming we project only every n-th point which resets + # the accumulated error every n-th point. if i % 20 == 0: total_distance = current_coords.project(Point(own_coords[i])) else: total_distance += next_distance - assert(len(result_coords) == len(result_coords_origin)) + assert len(result_coords) == len(result_coords_origin) return result_coords, result_coords_origin diff --git a/lib/stitches/DebuggingMethods.py b/lib/stitches/DebuggingMethods.py index d0f65576..e239edba 100644 --- a/lib/stitches/DebuggingMethods.py +++ b/lib/stitches/DebuggingMethods.py @@ -1,14 +1,11 @@ - import matplotlib.pyplot as plt from shapely.geometry import Polygon -from shapely.ops import nearest_points, substring, polygonize from anytree import PreOrderIter -from shapely.geometry.polygon import orient -#import LineStringSampling as Sampler + +# import LineStringSampling as Sampler import numpy as np import matplotlib.collections as mcoll -import matplotlib.path as mpath # def offset_polygons(polys, offset,joinstyle): # if polys.geom_type == 'Polygon': @@ -40,7 +37,7 @@ import matplotlib.path as mpath def plot_MultiPolygon(MultiPoly, plt, colorString): if MultiPoly.is_empty: return - if MultiPoly.geom_type == 'Polygon': + if MultiPoly.geom_type == "Polygon": x2, y2 = MultiPoly.exterior.xy plt.plot(x2, y2, colorString) @@ -56,6 +53,7 @@ def plot_MultiPolygon(MultiPoly, plt, colorString): x2, y2 = inners.coords.xy plt.plot(x2, y2, colorString) + # Test whether there are areas which would currently not be stitched but should be stitched @@ -65,12 +63,13 @@ def subtractResult(poly, rootPoly, offsetThresh): poly2 = poly2.difference(node.val.buffer(offsetThresh, 5, 3, 3)) return poly2 + # Used for debugging - plots all polygon exteriors within an AnyTree which is provided by the root node rootPoly. def drawPoly(rootPoly, colorString): fig, axs = plt.subplots(1, 1) - axs.axis('equal') + axs.axis("equal") plt.gca().invert_yaxis() for node in PreOrderIter(rootPoly): # if(node.id == "hole"): @@ -84,15 +83,26 @@ def drawPoly(rootPoly, colorString): def drawresult(resultcoords, resultcoords_Origin, colorString): fig, axs = plt.subplots(1, 1) - axs.axis('equal') + axs.axis("equal") plt.gca().invert_yaxis() plt.plot(*zip(*resultcoords), colorString) - colormap = np.array(['r', 'g', 'b', 'c', 'm', 'y', 'k', 'gray', 'm']) - labelmap = np.array(['MUST_USE', 'REGULAR_SPACING', 'INITIAL_RASTERING', 'EDGE_NEEDED', 'NOT_NEEDED', - 'ALREADY_TRANSFERRED', 'ADDITIONAL_TRACKING_POINT_NOT_NEEDED', 'EDGE_RASTERING_ALLOWED', 'EDGE_PREVIOUSLY_SHIFTED']) - - for i in range(0, 8+1): + colormap = np.array(["r", "g", "b", "c", "m", "y", "k", "gray", "m"]) + labelmap = np.array( + [ + "MUST_USE", + "REGULAR_SPACING", + "INITIAL_RASTERING", + "EDGE_NEEDED", + "NOT_NEEDED", + "ALREADY_TRANSFERRED", + "ADDITIONAL_TRACKING_POINT_NOT_NEEDED", + "EDGE_RASTERING_ALLOWED", + "EDGE_PREVIOUSLY_SHIFTED", + ] + ) + + for i in range(0, 8 + 1): # if i != Sampler.PointSource.EDGE_NEEDED and i != Sampler.PointSource.INITIAL_RASTERING: # continue selection = [] @@ -102,8 +112,8 @@ def drawresult(resultcoords, resultcoords_Origin, colorString): if len(selection) > 0: plt.scatter(*zip(*selection), c=colormap[i], label=labelmap[i]) - # plt.scatter(*zip(*resultcoords), - # c=colormap[resultcoords_Origin]) + # plt.scatter(*zip(*resultcoords), + # c=colormap[resultcoords_Origin]) axs.legend() plt.show(block=True) @@ -112,8 +122,14 @@ def drawresult(resultcoords, resultcoords_Origin, colorString): def colorline( - x, y, z=None, cmap=plt.get_cmap('copper'), norm=plt.Normalize(0.0, 1.0), - linewidth=3, alpha=1.0): + x, + y, + z=None, + cmap=plt.get_cmap("copper"), + norm=plt.Normalize(0.0, 1.0), + linewidth=3, + alpha=1.0, +): """ http://nbviewer.ipython.org/github/dpsanders/matplotlib-examples/blob/master/colorline.ipynb http://matplotlib.org/examples/pylab_examples/multicolored_line.html @@ -133,14 +149,16 @@ def colorline( z = np.asarray(z) segments = make_segments(x, y) - lc = mcoll.LineCollection(segments, array=z, cmap=cmap, norm=norm, - linewidth=linewidth, alpha=alpha) + lc = mcoll.LineCollection( + segments, array=z, cmap=cmap, norm=norm, linewidth=linewidth, alpha=alpha + ) ax = plt.gca() ax.add_collection(lc) return lc + # Used by colorline diff --git a/lib/stitches/LineStringSampling.py b/lib/stitches/LineStringSampling.py index 434c6bbf..07106515 100644 --- a/lib/stitches/LineStringSampling.py +++ b/lib/stitches/LineStringSampling.py @@ -1,4 +1,3 @@ -from sys import path from shapely.geometry.polygon import LineString from shapely.geometry import Point from shapely.ops import substring @@ -8,33 +7,41 @@ from enum import IntEnum from ..stitches import constants from ..stitches import PointTransfer -#Used to tag the origin of a rastered point +# Used to tag the origin of a rastered point + + class PointSource(IntEnum): - #MUST_USE = 0 # Legacy + # MUST_USE = 0 # Legacy REGULAR_SPACING = 1 # introduced to not exceed maximal stichting distance - #INITIAL_RASTERING = 2 #Legacy - EDGE_NEEDED = 3 # point which must be stitched to avoid to large deviations to the desired path - #NOT_NEEDED = 4 #Legacy - #ALREADY_TRANSFERRED = 5 #Legacy - #ADDITIONAL_TRACKING_POINT_NOT_NEEDED = 6 #Legacy - #EDGE_RASTERING_ALLOWED = 7 #Legacy - #EDGE_PREVIOUSLY_SHIFTED = 8 #Legacy - ENTER_LEAVING_POINT = 9 #Whether this point is used to enter or leave a child - SOFT_EDGE_INTERNAL = 10 #If the angle at a point is <= constants.limiting_angle this point is marked as SOFT_EDGE - HARD_EDGE_INTERNAL = 11 #If the angle at a point is > constants.limiting_angle this point is marked as HARD_EDGE (HARD_EDGES will always be stitched) - PROJECTED_POINT = 12 #If the point was created by a projection (transferred point) of a neighbor it is marked as PROJECTED_POINT - REGULAR_SPACING_INTERNAL = 13 # introduced to not exceed maximal stichting distance - #FORBIDDEN_POINT_INTERNAL=14 #Legacy - SOFT_EDGE = 15 #If the angle at a point is <= constants.limiting_angle this point is marked as SOFT_EDGE - HARD_EDGE = 16 #If the angle at a point is > constants.limiting_angle this point is marked as HARD_EDGE (HARD_EDGES will always be stitched) - FORBIDDEN_POINT=17 #Only relevant for desired interlacing - non-shifted point positions at the next neighbor are marked as forbidden - REPLACED_FORBIDDEN_POINT=18 #If one decides to avoid forbidden points new points to the left and to the right as replacement are created - DIRECT = 19 #Calculated by next neighbor projection - OVERNEXT = 20 #Calculated by overnext neighbor projection + # INITIAL_RASTERING = 2 #Legacy + # point which must be stitched to avoid to large deviations to the desired path + EDGE_NEEDED = 3 + # NOT_NEEDED = 4 #Legacy + # ALREADY_TRANSFERRED = 5 #Legacy + # ADDITIONAL_TRACKING_POINT_NOT_NEEDED = 6 #Legacy + # EDGE_RASTERING_ALLOWED = 7 #Legacy + # EDGE_PREVIOUSLY_SHIFTED = 8 #Legacy + ENTER_LEAVING_POINT = 9 # Whether this point is used to enter or leave a child + # If the angle at a point is <= constants.limiting_angle this point is marked as SOFT_EDGE + SOFT_EDGE_INTERNAL = 10 + # If the angle at a point is > constants.limiting_angle this point is marked as HARD_EDGE (HARD_EDGES will always be stitched) + HARD_EDGE_INTERNAL = 11 + # If the point was created by a projection (transferred point) of a neighbor it is marked as PROJECTED_POINT + PROJECTED_POINT = 12 + REGULAR_SPACING_INTERNAL = 13 # introduced to not exceed maximal stichting distance + # FORBIDDEN_POINT_INTERNAL=14 #Legacy + SOFT_EDGE = 15 # If the angle at a point is <= constants.limiting_angle this point is marked as SOFT_EDGE + # If the angle at a point is > constants.limiting_angle this point is marked as HARD_EDGE (HARD_EDGES will always be stitched) + HARD_EDGE = 16 + FORBIDDEN_POINT = 17 # Only relevant for desired interlacing - non-shifted point positions at the next neighbor are marked as forbidden + # If one decides to avoid forbidden points new points to the left and to the right as replacement are created + REPLACED_FORBIDDEN_POINT = 18 + DIRECT = 19 # Calculated by next neighbor projection + OVERNEXT = 20 # Calculated by overnext neighbor projection # Calculates the angles between adjacent edges at each interior point -#Note that the first and last values in the return array are zero since for the boundary points no angle calculations were possible +# Note that the first and last values in the return array are zero since for the boundary points no angle calculations were possible def calculate_line_angles(line): Angles = np.zeros(len(line.coords)) for i in range(1, len(line.coords)-1): @@ -42,44 +49,47 @@ def calculate_line_angles(line): vec2 = np.array(line.coords[i+1])-np.array(line.coords[i]) vec1length = np.linalg.norm(vec1) vec2length = np.linalg.norm(vec2) - #if vec1length <= 0: + # if vec1length <= 0: # print("HIER FEHLER") - - #if vec2length <=0: + + # if vec2length <=0: # print("HIER FEHLEr") - assert(vec1length >0) - assert(vec2length >0) - scalar_prod=np.dot(vec1, vec2)/(vec1length*vec2length) - scalar_prod = min(max(scalar_prod,-1),1) - #if scalar_prod > 1.0: + assert(vec1length > 0) + assert(vec2length > 0) + scalar_prod = np.dot(vec1, vec2)/(vec1length*vec2length) + scalar_prod = min(max(scalar_prod, -1), 1) + # if scalar_prod > 1.0: # scalar_prod = 1.0 - #elif scalar_prod < -1.0: + # elif scalar_prod < -1.0: # scalar_prod = -1.0 Angles[i] = math.acos(scalar_prod) return Angles -#Rasters a line between start_distance and end_distance. -#Input: -#-line: The line to be rastered -#-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 -#-stitching_direction: =1 is stitched along line direction, =-1 if stitched in reversed order. Note that +# Rasters a line between start_distance and end_distance. +# Input: +# -line: The line to be rastered +# -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 +# -stitching_direction: =1 is stitched along line direction, =-1 if stitched in reversed order. 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) -#index of point_origin is the index of the point in the neighboring line -#-abs_offset: used offset between to offsetted curves -#Output: -#-List of tuples with the rastered point coordinates -#-List which defines the point origin for each point according to the PointSource enum. -def raster_line_string_with_priority_points(line, start_distance, end_distance, maxstitch_distance, stitching_direction, must_use_points_deque, abs_offset): +# -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) +# index of point_origin is the index of the point in the neighboring line +# -abs_offset: used offset between to offsetted curves +# Output: +# -List of tuples with the rastered point coordinates +# -List which defines the point origin for each point according to the PointSource enum. + + +def raster_line_string_with_priority_points(line, start_distance, end_distance, maxstitch_distance, + stitching_direction, must_use_points_deque, abs_offset): if (abs(end_distance-start_distance) < constants.line_lengh_seen_as_one_point): return [line.interpolate(start_distance).coords[0]], [PointSource.HARD_EDGE] assert (stitching_direction == -1 and start_distance >= end_distance) or ( stitching_direction == 1 and start_distance <= end_distance) - + deque_points = list(must_use_points_deque) linecoords = line.coords @@ -92,7 +102,8 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, deque_points[i] = (deque_points[i][0], line.length-deque_points[i][1]) else: - deque_points = deque_points[::-1] #Since points with highest priority (=distance along line) are first (descending sorted) + # Since points with highest priority (=distance along line) are first (descending sorted) + 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)): @@ -107,95 +118,109 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, path_coords = substring(aligned_line, start_distance, end_distance) - #aligned line is a line without doubled points. I had the strange situation in which the offset "start_distance" from the line beginning resulted in a starting point which was - # already present in aligned_line causing a doubled point. A double point is not allowed in the following calculations so we need to remove it: - if abs(path_coords.coords[0][0]-path_coords.coords[1][0])<constants.eps and abs(path_coords.coords[0][1]-path_coords.coords[1][1])<constants.eps: + # aligned line is a line without doubled points. + # I had the strange situation in which the offset "start_distance" from the line beginning + # resulted in a starting point which was already present in aligned_line causing a doubled point. + # A double point is not allowed in the following calculations so we need to remove it: + if (abs(path_coords.coords[0][0]-path_coords.coords[1][0]) < constants.eps and + abs(path_coords.coords[0][1]-path_coords.coords[1][1]) < constants.eps): path_coords.coords = path_coords.coords[1:] - if abs(path_coords.coords[-1][0]-path_coords.coords[-2][0])<constants.eps and abs(path_coords.coords[-1][1]-path_coords.coords[-2][1])<constants.eps: + if (abs(path_coords.coords[-1][0]-path_coords.coords[-2][0]) < constants.eps and + abs(path_coords.coords[-1][1]-path_coords.coords[-2][1]) < constants.eps): path_coords.coords = path_coords.coords[:-1] angles = calculate_line_angles(path_coords) current_distance = start_distance - #Next we merge the line points and the projected (deque) points into one list + # 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(path_coords.coords,angles): - #if abs(point[0]-40.4) < 0.2 and abs(point[1]-2.3)< 0.2: + for point, angle in zip(path_coords.coords, angles): + # if abs(point[0]-40.4) < 0.2 and abs(point[1]-2.3)< 0.2: # print("GEFUNDEN") current_distance = start_distance+path_coords.project(Point(point)) while dq_iter < len(deque_points) and deque_points[dq_iter][1] < current_distance: - #We want to avoid setting points at soft edges close to forbidden points + # 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 + # 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)): item = merged_point_list.pop() - merged_point_list.append((PointTransfer.projected_point_tuple(point=item[0].point, point_source=\ - PointSource.FORBIDDEN_POINT),item[1])) + merged_point_list.append((PointTransfer.projected_point_tuple( + point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1])) else: 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 + 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) < abs_offset*constants.factor_offset_forbidden_point): point_source = PointSource.FORBIDDEN_POINT else: if angle < constants.limiting_angle: point_source = PointSource.SOFT_EDGE_INTERNAL else: point_source = PointSource.HARD_EDGE_INTERNAL - merged_point_list.append((PointTransfer.projected_point_tuple(point=Point(point), point_source=point_source),current_distance)) + merged_point_list.append((PointTransfer.projected_point_tuple( + point=Point(point), point_source=point_source), current_distance)) result_list = [merged_point_list[0]] - - #General idea: Take one point of merged_point_list after another into the current segment until this segment is not simplified to a straight line by shapelys simplify method. - #Then, look at the points within this segment and choose the best fitting one (HARD_EDGE > OVERNEXT projected point > DIRECT projected point) as termination of this segment + + # General idea: Take one point of merged_point_list after another into the current segment until this segment is not simplified + # to a straight line by shapelys simplify method. + # Then, look at the points within this segment and choose the best fitting one + # (HARD_EDGE > OVERNEXT projected point > DIRECT projected point) as termination of this segment # and start point for the next segment (so we do not always take the maximum possible length for a segment) segment_start_index = 0 segment_end_index = 1 forbidden_point_list = [] - while segment_end_index < len(merged_point_list): - #if abs(merged_point_list[segment_end_index-1][0].point.coords[0][0]-67.9) < 0.2 and abs(merged_point_list[segment_end_index-1][0].point.coords[0][1]-161.0)< 0.2: + while segment_end_index < len(merged_point_list): + # if abs(merged_point_list[segment_end_index-1][0].point.coords[0][0]-67.9) < 0.2 and + # abs(merged_point_list[segment_end_index-1][0].point.coords[0][1]-161.0)< 0.2: # print("GEFUNDEN") - #Collection of points for the current segment + # Collection of points for the current segment current_point_list = [merged_point_list[segment_start_index][0].point] - + while segment_end_index < len(merged_point_list): - segment_length = merged_point_list[segment_end_index][1]-merged_point_list[segment_start_index][1] + segment_length = merged_point_list[segment_end_index][1] - \ + merged_point_list[segment_start_index][1] if segment_length > maxstitch_distance+constants.point_spacing_to_be_considered_equal: - new_distance = merged_point_list[segment_start_index][1]+maxstitch_distance - merged_point_list.insert(segment_end_index,(PointTransfer.projected_point_tuple(point=aligned_line.interpolate(new_distance), point_source=\ - PointSource.REGULAR_SPACING_INTERNAL),new_distance)) - if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-12.2) < 0.2 and abs(merged_point_list[segment_end_index][0].point.coords[0][1]-0.9)< 0.2: - print("GEFUNDEN") - segment_end_index+=1 + new_distance = merged_point_list[segment_start_index][1] + \ + maxstitch_distance + merged_point_list.insert(segment_end_index, (PointTransfer.projected_point_tuple( + point=aligned_line.interpolate(new_distance), point_source=PointSource.REGULAR_SPACING_INTERNAL), new_distance)) + # if (abs(merged_point_list[segment_end_index][0].point.coords[0][0]-12.2) < 0.2 and + # abs(merged_point_list[segment_end_index][0].point.coords[0][1]-0.9) < 0.2): + # print("GEFUNDEN") + segment_end_index += 1 break - #if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-93.6) < 0.2 and abs(merged_point_list[segment_end_index][0].point.coords[0][1]-122.7)< 0.2: + # if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-93.6) < 0.2 and + # abs(merged_point_list[segment_end_index][0].point.coords[0][1]-122.7)< 0.2: # print("GEFUNDEN") - - current_point_list.append(merged_point_list[segment_end_index][0].point) - simplified_len = len(LineString(current_point_list).simplify(constants.factor_offset_remove_dense_points*abs_offset,preserve_topology=False).coords) - if simplified_len > 2: #not all points have been simplified - so we need to add it + + current_point_list.append( + merged_point_list[segment_end_index][0].point) + simplified_len = len(LineString(current_point_list).simplify( + constants.factor_offset_remove_dense_points*abs_offset, preserve_topology=False).coords) + if simplified_len > 2: # not all points have been simplified - so we need to add it break - if merged_point_list[segment_end_index][0].point_source ==PointSource.HARD_EDGE_INTERNAL: - segment_end_index+=1 + if merged_point_list[segment_end_index][0].point_source == PointSource.HARD_EDGE_INTERNAL: + segment_end_index += 1 break - segment_end_index+=1 + segment_end_index += 1 - segment_end_index-=1 + segment_end_index -= 1 - #Now we choose the best fitting point within this segment + # Now we choose the best fitting point within this segment index_overnext = -1 index_direct = -1 index_hard_edge = -1 - iter = segment_start_index+1 + iter = segment_start_index+1 while (iter <= segment_end_index): if merged_point_list[iter][0].point_source == PointSource.OVERNEXT: index_overnext = iter @@ -208,48 +233,48 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, segment_end_index = index_hard_edge else: if index_overnext != -1: - if (index_direct != -1 and index_direct > index_overnext and - (merged_point_list[index_direct][1]-merged_point_list[index_overnext][1]) >= - constants.factor_segment_length_direct_preferred_over_overnext* + if (index_direct != -1 and index_direct > index_overnext and + (merged_point_list[index_direct][1]-merged_point_list[index_overnext][1]) >= + constants.factor_segment_length_direct_preferred_over_overnext * (merged_point_list[index_overnext][1]-merged_point_list[segment_start_index][1])): - #We allow to take the direct projected point instead of the overnext projected point if it would result in a - #significant longer segment length + # We allow to take the direct projected point instead of the overnext projected point if it would result in a + # significant longer segment length segment_end_index = index_direct else: segment_end_index = index_overnext elif index_direct != -1: segment_end_index = index_direct - #Usually OVERNEXT and DIRECT points are close to each other and in some cases both were selected as segment edges - #If they are too close (<abs_offset) we remove one of it + # Usually OVERNEXT and DIRECT points are close to each other and in some cases both were selected as segment edges + # If they are too close (<abs_offset) we remove one of it if (((merged_point_list[segment_start_index][0].point_source == PointSource.OVERNEXT and merged_point_list[segment_end_index][0].point_source == PointSource.DIRECT) or (merged_point_list[segment_start_index][0].point_source == PointSource.DIRECT and merged_point_list[segment_end_index][0].point_source == PointSource.OVERNEXT)) and - abs(merged_point_list[segment_end_index][1] - merged_point_list[segment_start_index][1]) < abs_offset): + abs(merged_point_list[segment_end_index][1] - merged_point_list[segment_start_index][1]) < abs_offset): result_list.pop() result_list.append(merged_point_list[segment_end_index]) - #To have a chance to replace all forbidden points afterwards + # To have a chance to replace all forbidden points afterwards if merged_point_list[segment_end_index][0].point_source == PointSource.FORBIDDEN_POINT: forbidden_point_list.append(len(result_list)-1) segment_start_index = segment_end_index - segment_end_index+=1 + segment_end_index += 1 - return_point_list = [] #[result_list[0][0].point.coords[0]] - return_point_source_list = []#[result_list[0][0].point_source] + return_point_list = [] # [result_list[0][0].point.coords[0]] + return_point_source_list = [] # [result_list[0][0].point_source] - #Currently replacement of forbidden points not satisfying - #result_list = replace_forbidden_points(aligned_line, result_list, forbidden_point_list,abs_offset) + # Currently replacement of forbidden points not satisfying + # result_list = replace_forbidden_points(aligned_line, result_list, forbidden_point_list,abs_offset) - #Finally we create the final return_point_list and return_point_source_list + # Finally we create the final return_point_list and return_point_source_list for i in range(len(result_list)): return_point_list.append(result_list[i][0].point.coords[0]) - #if abs(result_list[i][0].point.coords[0][0]-91.7) < 0.2 and abs(result_list[i][0].point.coords[0][1]-106.15)< 0.2: + # if abs(result_list[i][0].point.coords[0][0]-91.7) < 0.2 and abs(result_list[i][0].point.coords[0][1]-106.15)< 0.2: # print("GEFUNDEN") if result_list[i][0].point_source == PointSource.HARD_EDGE_INTERNAL: - point_source = PointSource.HARD_EDGE + point_source = PointSource.HARD_EDGE elif result_list[i][0].point_source == PointSource.SOFT_EDGE_INTERNAL: point_source = PointSource.SOFT_EDGE elif result_list[i][0].point_source == PointSource.REGULAR_SPACING_INTERNAL: @@ -261,132 +286,145 @@ def raster_line_string_with_priority_points(line, start_distance, end_distance, return_point_source_list.append(point_source) - assert(len(return_point_list) == len(return_point_source_list)) - #return remove_dense_points(returnpointlist, returnpointsourcelist, maxstitch_distance,abs_offset) + # return remove_dense_points(returnpointlist, returnpointsourcelist, maxstitch_distance,abs_offset) return return_point_list, return_point_source_list -#Rasters a line between start_distance and end_distance. -#Input: -#-line: The line to be rastered -#-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 -#-stitching_direction: =1 is stitched along line direction, =-1 if stitched in reversed order. Note that +# Rasters a line between start_distance and end_distance. +# Input: +# -line: The line to be rastered +# -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 +# -stitching_direction: =1 is stitched along line direction, =-1 if stitched in reversed order. 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) -#index of point_origin is the index of the point in the neighboring line -#-abs_offset: used offset between to offsetted curves -#Output: -#-List of tuples with the rastered point coordinates -#-List which defines the point origin for each point according to the PointSource enum. +# -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) +# index of point_origin is the index of the point in the neighboring line +# -abs_offset: used offset between to offsetted curves +# Output: +# -List of tuples with the rastered point coordinates +# -List which defines the point origin for each point according to the PointSource enum. + + def raster_line_string_with_priority_points_graph(line, maxstitch_distance, stitching_direction, must_use_points_deque, abs_offset, offset_by_half): if (line.length < constants.line_lengh_seen_as_one_point): return [line.coords[0]], [PointSource.HARD_EDGE] - + deque_points = list(must_use_points_deque) linecoords = line.coords - if stitching_direction==-1: + if stitching_direction == -1: linecoords = linecoords[::-1] for i in range(len(deque_points)): deque_points[i] = (deque_points[i][0], line.length-deque_points[i][1]) else: - deque_points = deque_points[::-1] #Since points with highest priority (=distance along line) are first (descending sorted) + # Since points with highest priority (=distance along line) are first (descending sorted) + deque_points = deque_points[::-1] # Ordering in priority queue: # (point, LineStringSampling.PointSource), priority) - aligned_line = LineString(linecoords) #might be different from line for stitching_direction=-1 + # might be different from line for stitching_direction=-1 + aligned_line = LineString(linecoords) angles = calculate_line_angles(aligned_line) - #For the first and last point we cannot calculate an angle. Set it to above the limit to make it a hard edge + # For the first and last point we cannot calculate an angle. Set it to above the limit to make it a hard edge angles[0] = 1.1*constants.limiting_angle - angles[-1] = 1.1*constants.limiting_angle + angles[-1] = 1.1*constants.limiting_angle current_distance = 0.0 - #Next we merge the line points and the projected (deque) points into one list + # 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(aligned_line.coords, angles): + # if abs(point[0]-52.9) < 0.2 and abs(point[1]-183.4)< 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: - #We want to avoid setting points at soft edges close to forbidden points + # 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 + # 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)): item = merged_point_list.pop() - merged_point_list.append((PointTransfer.projected_point_tuple(point=item[0].point, point_source=\ - PointSource.FORBIDDEN_POINT),item[1])) + merged_point_list.append((PointTransfer.projected_point_tuple( + point=item[0].point, point_source=PointSource.FORBIDDEN_POINT), item[1])) else: 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 + 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) < abs_offset*constants.factor_offset_forbidden_point): point_source = PointSource.FORBIDDEN_POINT else: if angle < constants.limiting_angle: point_source = PointSource.SOFT_EDGE_INTERNAL else: point_source = PointSource.HARD_EDGE_INTERNAL - merged_point_list.append((PointTransfer.projected_point_tuple(point=Point(point), point_source=point_source),current_distance)) + merged_point_list.append((PointTransfer.projected_point_tuple( + point=Point(point), point_source=point_source), current_distance)) result_list = [merged_point_list[0]] - - #General idea: Take one point of merged_point_list after another into the current segment until this segment is not simplified to a straight line by shapelys simplify method. - #Then, look at the points within this segment and choose the best fitting one (HARD_EDGE > OVERNEXT projected point > DIRECT projected point) as termination of this segment + + # General idea: Take one point of merged_point_list after another into the current segment until this segment is not simplified + # to a straight line by shapelys simplify method. + # Then, look at the points within this segment and choose the best fitting one + # (HARD_EDGE > OVERNEXT projected point > DIRECT projected point) as termination of this segment # and start point for the next segment (so we do not always take the maximum possible length for a segment) segment_start_index = 0 segment_end_index = 1 forbidden_point_list = [] - while segment_end_index < len(merged_point_list): - #if abs(merged_point_list[segment_end_index-1][0].point.coords[0][0]-67.9) < 0.2 and abs(merged_point_list[segment_end_index-1][0].point.coords[0][1]-161.0)< 0.2: + while segment_end_index < len(merged_point_list): + # if abs(merged_point_list[segment_end_index-1][0].point.coords[0][0]-67.9) < 0.2 and + # abs(merged_point_list[segment_end_index-1][0].point.coords[0][1]-161.0)< 0.2: # print("GEFUNDEN") - #Collection of points for the current segment + # Collection of points for the current segment current_point_list = [merged_point_list[segment_start_index][0].point] - + while segment_end_index < len(merged_point_list): - segment_length = merged_point_list[segment_end_index][1]-merged_point_list[segment_start_index][1] + segment_length = merged_point_list[segment_end_index][1] - \ + merged_point_list[segment_start_index][1] if segment_length > maxstitch_distance+constants.point_spacing_to_be_considered_equal: - new_distance = merged_point_list[segment_start_index][1]+maxstitch_distance - merged_point_list.insert(segment_end_index,(PointTransfer.projected_point_tuple(point=aligned_line.interpolate(new_distance), point_source=\ - PointSource.REGULAR_SPACING_INTERNAL),new_distance)) - #if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-12.2) < 0.2 and abs(merged_point_list[segment_end_index][0].point.coords[0][1]-0.9)< 0.2: + new_distance = merged_point_list[segment_start_index][1] + \ + maxstitch_distance + merged_point_list.insert(segment_end_index, (PointTransfer.projected_point_tuple( + point=aligned_line.interpolate(new_distance), point_source=PointSource.REGULAR_SPACING_INTERNAL), new_distance)) + # if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-12.2) < 0.2 and 7 + # abs(merged_point_list[segment_end_index][0].point.coords[0][1]-0.9)< 0.2: # print("GEFUNDEN") - segment_end_index+=1 + segment_end_index += 1 break - #if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-34.4) < 0.2 and abs(merged_point_list[segment_end_index][0].point.coords[0][1]-6.2)< 0.2: + # if abs(merged_point_list[segment_end_index][0].point.coords[0][0]-34.4) < 0.2 and + # abs(merged_point_list[segment_end_index][0].point.coords[0][1]-6.2)< 0.2: # print("GEFUNDEN") - - current_point_list.append(merged_point_list[segment_end_index][0].point) - simplified_len = len(LineString(current_point_list).simplify(constants.factor_offset_remove_dense_points*abs_offset,preserve_topology=False).coords) - if simplified_len > 2: #not all points have been simplified - so we need to add it + + current_point_list.append( + merged_point_list[segment_end_index][0].point) + simplified_len = len(LineString(current_point_list).simplify( + constants.factor_offset_remove_dense_points*abs_offset, preserve_topology=False).coords) + if simplified_len > 2: # not all points have been simplified - so we need to add it break - if merged_point_list[segment_end_index][0].point_source ==PointSource.HARD_EDGE_INTERNAL: - segment_end_index+=1 + if merged_point_list[segment_end_index][0].point_source == PointSource.HARD_EDGE_INTERNAL: + segment_end_index += 1 break - segment_end_index+=1 + segment_end_index += 1 - segment_end_index-=1 + segment_end_index -= 1 - #Now we choose the best fitting point within this segment + # Now we choose the best fitting point within this segment index_overnext = -1 index_direct = -1 index_hard_edge = -1 - iter = segment_start_index+1 + iter = segment_start_index+1 while (iter <= segment_end_index): if merged_point_list[iter][0].point_source == PointSource.OVERNEXT: index_overnext = iter @@ -406,48 +444,49 @@ def raster_line_string_with_priority_points_graph(line, maxstitch_distance, stit index_less_preferred = index_overnext if index_preferred != -1: - if (index_less_preferred != -1 and index_less_preferred > index_preferred and - (merged_point_list[index_less_preferred][1]-merged_point_list[index_preferred][1]) >= - constants.factor_segment_length_direct_preferred_over_overnext* + if (index_less_preferred != -1 and index_less_preferred > index_preferred and + (merged_point_list[index_less_preferred][1]-merged_point_list[index_preferred][1]) >= + constants.factor_segment_length_direct_preferred_over_overnext * (merged_point_list[index_preferred][1]-merged_point_list[segment_start_index][1])): - #We allow to take the direct projected point instead of the overnext projected point if it would result in a - #significant longer segment length + # We allow to take the direct projected point instead of the overnext projected point if it would result in a + # significant longer segment length segment_end_index = index_less_preferred else: segment_end_index = index_preferred elif index_less_preferred != -1: segment_end_index = index_less_preferred - #Usually OVERNEXT and DIRECT points are close to each other and in some cases both were selected as segment edges - #If they are too close (<abs_offset) we remove one of it + # Usually OVERNEXT and DIRECT points are close to each other and in some cases both were selected as segment edges + # If they are too close (<abs_offset) we remove one of it if (((merged_point_list[segment_start_index][0].point_source == PointSource.OVERNEXT and merged_point_list[segment_end_index][0].point_source == PointSource.DIRECT) or (merged_point_list[segment_start_index][0].point_source == PointSource.DIRECT and merged_point_list[segment_end_index][0].point_source == PointSource.OVERNEXT)) and - abs(merged_point_list[segment_end_index][1] - merged_point_list[segment_start_index][1]) < abs_offset): + abs(merged_point_list[segment_end_index][1] - merged_point_list[segment_start_index][1]) < abs_offset): result_list.pop() result_list.append(merged_point_list[segment_end_index]) - #To have a chance to replace all forbidden points afterwards + # To have a chance to replace all forbidden points afterwards if merged_point_list[segment_end_index][0].point_source == PointSource.FORBIDDEN_POINT: forbidden_point_list.append(len(result_list)-1) segment_start_index = segment_end_index - segment_end_index+=1 + segment_end_index += 1 - return_point_list = [] #[result_list[0][0].point.coords[0]] - return_point_source_list = []#[result_list[0][0].point_source] + return_point_list = [] # [result_list[0][0].point.coords[0]] + return_point_source_list = [] # [result_list[0][0].point_source] - #Currently replacement of forbidden points not satisfying - result_list = replace_forbidden_points(aligned_line, result_list, forbidden_point_list,abs_offset) + # Currently replacement of forbidden points not satisfying + result_list = replace_forbidden_points( + aligned_line, result_list, forbidden_point_list, abs_offset) - #Finally we create the final return_point_list and return_point_source_list + # Finally we create the final return_point_list and return_point_source_list for i in range(len(result_list)): return_point_list.append(result_list[i][0].point.coords[0]) - #if abs(result_list[i][0].point.coords[0][0]-91.7) < 0.2 and abs(result_list[i][0].point.coords[0][1]-106.15)< 0.2: + # if abs(result_list[i][0].point.coords[0][0]-91.7) < 0.2 and abs(result_list[i][0].point.coords[0][1]-106.15)< 0.2: # print("GEFUNDEN") if result_list[i][0].point_source == PointSource.HARD_EDGE_INTERNAL: - point_source = PointSource.HARD_EDGE + point_source = PointSource.HARD_EDGE elif result_list[i][0].point_source == PointSource.SOFT_EDGE_INTERNAL: point_source = PointSource.SOFT_EDGE elif result_list[i][0].point_source == PointSource.REGULAR_SPACING_INTERNAL: @@ -459,44 +498,49 @@ def raster_line_string_with_priority_points_graph(line, maxstitch_distance, stit return_point_source_list.append(point_source) - assert(len(return_point_list) == len(return_point_source_list)) - #return remove_dense_points(returnpointlist, returnpointsourcelist, maxstitch_distance,abs_offset) + # return remove_dense_points(returnpointlist, returnpointsourcelist, maxstitch_distance,abs_offset) return return_point_list, return_point_source_list + def replace_forbidden_points(line, result_list, forbidden_point_list_indices, abs_offset): - current_index_shift = 0 #since we add and remove points in the result_list, we need to adjust the indices stored in forbidden_point_list_indices + # since we add and remove points in the result_list, we need to adjust the indices stored in forbidden_point_list_indices + current_index_shift = 0 for index in forbidden_point_list_indices: - #if abs(result_list[index][0].point.coords[0][0]-40.7) < 0.2 and abs(result_list[index][0].point.coords[0][1]-1.3)< 0.2: + # if abs(result_list[index][0].point.coords[0][0]-40.7) < 0.2 and abs(result_list[index][0].point.coords[0][1]-1.3)< 0.2: # print("GEFUNDEN") - index+=current_index_shift - distance_left = result_list[index][0].point.distance(result_list[index-1][0].point)/2.0 - distance_right = result_list[index][0].point.distance(result_list[(index+1)%len(result_list)][0].point)/2.0 + index += current_index_shift + distance_left = result_list[index][0].point.distance( + result_list[index-1][0].point)/2.0 + distance_right = result_list[index][0].point.distance( + result_list[(index+1) % len(result_list)][0].point)/2.0 while distance_left > constants.point_spacing_to_be_considered_equal and distance_right > constants.point_spacing_to_be_considered_equal: new_point_left_proj = result_list[index][1]-distance_left if new_point_left_proj < 0: new_point_left_proj += line.length new_point_right_proj = result_list[index][1]+distance_right if new_point_right_proj > line.length: - new_point_right_proj-=line.length + new_point_right_proj -= line.length point_left = line.interpolate(new_point_left_proj) point_right = line.interpolate(new_point_right_proj) - forbidden_point_distance = result_list[index][0].point.distance(LineString([point_left, point_right])) + forbidden_point_distance = result_list[index][0].point.distance( + LineString([point_left, point_right])) if forbidden_point_distance < constants.factor_offset_remove_dense_points*abs_offset: del result_list[index] - result_list.insert(index, (PointTransfer.projected_point_tuple(point=point_right, point_source=\ - PointSource.REPLACED_FORBIDDEN_POINT),new_point_right_proj)) - result_list.insert(index, (PointTransfer.projected_point_tuple(point=point_left, point_source=\ - PointSource.REPLACED_FORBIDDEN_POINT),new_point_left_proj)) - current_index_shift+=1 + result_list.insert(index, (PointTransfer.projected_point_tuple( + point=point_right, point_source=PointSource.REPLACED_FORBIDDEN_POINT), new_point_right_proj)) + result_list.insert(index, (PointTransfer.projected_point_tuple( + point=point_left, point_source=PointSource.REPLACED_FORBIDDEN_POINT), new_point_left_proj)) + current_index_shift += 1 break else: - distance_left/=2.0 - distance_right/=2.0 + distance_left /= 2.0 + distance_right /= 2.0 return result_list + if __name__ == "__main__": - line = LineString([(0,0), (1,0), (2,1),(3,0),(4,0)]) + line = LineString([(0, 0), (1, 0), (2, 1), (3, 0), (4, 0)]) print(calculate_line_angles(line)*180.0/math.pi) diff --git a/lib/stitches/PointTransfer.py b/lib/stitches/PointTransfer.py index 998282a3..b4c6c004 100644 --- a/lib/stitches/PointTransfer.py +++ b/lib/stitches/PointTransfer.py @@ -1,4 +1,4 @@ -from shapely.geometry import Point, MultiPoint +from shapely.geometry import Point, MultiPoint from shapely.geometry.polygon import LineString, LinearRing from collections import namedtuple from shapely.ops import nearest_points @@ -6,11 +6,14 @@ import math from ..stitches import constants from ..stitches import LineStringSampling -projected_point_tuple = namedtuple('projected_point_tuple', ['point', 'point_source']) +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. + -#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): result = bisectorline.intersection(child.val) if result.is_empty: @@ -24,37 +27,44 @@ def calc_transferred_point(bisectorline, child): resultlist = list(result) desired_point = resultlist[0] if len(resultlist) > 1: - desired_point = nearest_points(result, Point(bisectorline.coords[0]))[0] + desired_point = nearest_points( + result, Point(bisectorline.coords[0]))[0] priority = child.val.project(desired_point) point = desired_point return point, priority -#Takes the current tree item and its rastered points (to_transfer_points) and transfers these points to its parent, siblings and childs -# To do so it calculates the current normal and determines its intersection with the neighbors which gives the transferred points. -#Input: -#-treenode: Tree node whose points stored in "to_transfer_points" shall be transferred to its neighbors. -#-used_offset: The used offset when the curves where offsetted -#-offset_by_half: True if the transferred points shall be interlaced with respect to the points in "to_transfer_points" -#-max_stitching_distance: The maximum allowed stitch distance between two points -#-to_transfer_points: List of points belonging to treenode which shall be transferred - it is assumed that to_transfer_points can be handled as closed ring -#-to_transfer_points_origin: The origin tag of each point in to_transfer_points -#-overnext_neighbor: Transfer the points to the overnext neighbor (gives a more stable interlacing) -#-transfer_forbidden_points: Only allowed for interlacing (offset_by_half): Might be used to transfer points unshifted as forbidden points to the neighbor to avoid a point placing there -#-transfer_to_parent: If True, points will be transferred to the parent -#-transfer_to_sibling: If True, points will be transferred to the siblings -#-transfer_to_child: If True, points will be transferred to the childs -#Output: -#-Fills the attribute "transferred_point_priority_deque" of the siblings and parent in the tree datastructure. An item of the deque -#is setup as follows: ((projected point on line, LineStringSampling.PointSource), priority=distance along line) -#index of point_origin is the index of the point in the neighboring line -def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_stitching_distance, to_transfer_points, to_transfer_points_origin=[], - overnext_neighbor = False, transfer_forbidden_points = False, transfer_to_parent=True, transfer_to_sibling=True, transfer_to_child=True): - - assert(len(to_transfer_points)==len(to_transfer_points_origin) or len(to_transfer_points_origin) == 0) +def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_transfer_points, to_transfer_points_origin=[], + overnext_neighbor=False, transfer_forbidden_points=False, + transfer_to_parent=True, transfer_to_sibling=True, transfer_to_child=True): + """ + Takes the current tree item and its rastered points (to_transfer_points) and transfers these points to its parent, siblings and childs + To do so it calculates the current normal and determines its intersection with the neighbors which gives the transferred points. + Input: + -treenode: Tree node whose points stored in "to_transfer_points" shall be transferred to its neighbors. + -used_offset: The used offset when the curves where offsetted + -offset_by_half: True if the transferred points shall be interlaced with respect to the points in "to_transfer_points" + -to_transfer_points: List of points belonging to treenode which shall be transferred - it is assumed that to_transfer_points + can be handled as closed ring + -to_transfer_points_origin: The origin tag of each point in to_transfer_points + -overnext_neighbor: Transfer the points to the overnext neighbor (gives a more stable interlacing) + -transfer_forbidden_points: Only allowed for interlacing (offset_by_half): Might be used to transfer points unshifted as + forbidden points to the neighbor to avoid a point placing there + -transfer_to_parent: If True, points will be transferred to the parent + -transfer_to_sibling: If True, points will be transferred to the siblings + -transfer_to_child: If True, points will be transferred to the childs + Output: + -Fills the attribute "transferred_point_priority_deque" of the siblings and parent in the tree datastructure. An item of the deque + is setup as follows: ((projected point on line, LineStringSampling.PointSource), priority=distance along line) + index of point_origin is the index of the point in the neighboring line + """ + + assert(len(to_transfer_points) == len(to_transfer_points_origin) + or len(to_transfer_points_origin) == 0) assert((overnext_neighbor and not offset_by_half) or not overnext_neighbor) - assert(not transfer_forbidden_points or transfer_forbidden_points and (offset_by_half or not offset_by_half and overnext_neighbor)) + 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: return @@ -71,37 +81,37 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_st if transfer_to_child: for child in childs_tuple: - if child.already_rastered == False: + if not child.already_rastered: if not overnext_neighbor: child_list.append(child) if transfer_forbidden_points: child_list_forbidden.append(child) if overnext_neighbor: for subchild in child.children: - if subchild.already_rastered == False: + if not subchild.already_rastered: child_list.append(subchild) if transfer_to_sibling: for sibling in siblings_tuple: - if sibling.already_rastered == False: + if not sibling.already_rastered: if not overnext_neighbor: neighbor_list.append(sibling) if transfer_forbidden_points: neighbor_list_forbidden.append(sibling) if overnext_neighbor: for subchild in sibling.children: - if subchild.already_rastered == False: + if not subchild.already_rastered: neighbor_list.append(subchild) - if transfer_to_parent and treenode.parent != None: - if treenode.parent.already_rastered == False: + if transfer_to_parent and treenode.parent is not None: + if not treenode.parent.already_rastered: if not overnext_neighbor: - neighbor_list.append(treenode.parent) + neighbor_list.append(treenode.parent) if transfer_forbidden_points: - neighbor_list_forbidden.append(treenode.parent) + neighbor_list_forbidden.append(treenode.parent) if overnext_neighbor: - if treenode.parent.parent != None: - if treenode.parent.parent.already_rastered == False: + if treenode.parent.parent is not None: + if not treenode.parent.parent.already_rastered: neighbor_list.append(treenode.parent.parent) if not neighbor_list and not child_list: @@ -126,19 +136,20 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_st closed_line = LinearRing(to_transfer_points) bisectorline_length = abs(used_offset) * \ - constants.transfer_point_distance_factor*(2.0 if overnext_neighbor else 1.0) + constants.transfer_point_distance_factor * \ + (2.0 if overnext_neighbor else 1.0) bisectorline_length_forbidden_points = abs(used_offset) * \ constants.transfer_point_distance_factor linesign_child = math.copysign(1, used_offset) - i = 0 currentDistance = 0 while i < len(point_list): - assert(point_source_list[i] != LineStringSampling.PointSource.ENTER_LEAVING_POINT) - #if abs(point_list[i].coords[0][0]-47) < 0.3 and abs(point_list[i].coords[0][1]-4.5) < 0.3: + assert(point_source_list[i] != + LineStringSampling.PointSource.ENTER_LEAVING_POINT) + # if abs(point_list[i].coords[0][0]-47) < 0.3 and abs(point_list[i].coords[0][1]-4.5) < 0.3: # print("HIIIIIIIIIIIERRR") # We create a bisecting line through the current point @@ -152,7 +163,6 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_st normalized_vector_prev_x /= prev_spacing normalized_vector_prev_y /= prev_spacing - normalized_vector_next_x = normalized_vector_next_y = 0 next_spacing = 0 while True: @@ -187,13 +197,15 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_st vecy = -linesign_child*bisectorline_length*normalized_vector_next_x if transfer_forbidden_points: - vecx_forbidden_point = linesign_child*bisectorline_length_forbidden_points*normalized_vector_next_y - vecy_forbidden_point = -linesign_child*bisectorline_length_forbidden_points*normalized_vector_next_x + vecx_forbidden_point = linesign_child * \ + bisectorline_length_forbidden_points*normalized_vector_next_y + vecy_forbidden_point = -linesign_child * \ + bisectorline_length_forbidden_points*normalized_vector_next_x else: vecx *= bisectorline_length/vec_length vecy *= bisectorline_length/vec_length - + if (vecx*normalized_vector_next_y-vecy * normalized_vector_next_x)*linesign_child < 0: vecx = -vecx vecy = -vecy @@ -212,55 +224,66 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, max_st originPoint = closed_line.interpolate(off) bisectorline_child = LineString([(originPoint.coords[0][0], - originPoint.coords[0][1]), - (originPoint.coords[0][0]+vecx, - originPoint.coords[0][1]+vecy)]) + originPoint.coords[0][1]), + (originPoint.coords[0][0]+vecx, + originPoint.coords[0][1]+vecy)]) bisectorline_neighbor = LineString([(originPoint.coords[0][0], - originPoint.coords[0][1]), - (originPoint.coords[0][0]-vecx, - originPoint.coords[0][1]-vecy)]) + originPoint.coords[0][1]), + (originPoint.coords[0][0]-vecx, + originPoint.coords[0][1]-vecy)]) bisectorline_forbidden_point_child = LineString([(originPoint_forbidden_point.coords[0][0], - originPoint_forbidden_point.coords[0][1]), - (originPoint_forbidden_point.coords[0][0]+vecx_forbidden_point, - originPoint_forbidden_point.coords[0][1]+vecy_forbidden_point)]) + originPoint_forbidden_point.coords[0][1]), + (originPoint_forbidden_point.coords[0][0]+vecx_forbidden_point, + originPoint_forbidden_point.coords[0][1]+vecy_forbidden_point)]) bisectorline_forbidden_point_neighbor = LineString([(originPoint_forbidden_point.coords[0][0], - originPoint_forbidden_point.coords[0][1]), - (originPoint_forbidden_point.coords[0][0]-vecx_forbidden_point, - originPoint_forbidden_point.coords[0][1]-vecy_forbidden_point)]) + originPoint_forbidden_point.coords[0][1]), + (originPoint_forbidden_point.coords[0][0]-vecx_forbidden_point, + originPoint_forbidden_point.coords[0][1]-vecy_forbidden_point)]) for child in child_list: - point, priority = calc_transferred_point(bisectorline_child,child) - if point==None: + point, priority = calc_transferred_point(bisectorline_child, child) + if point is None: continue - child.transferred_point_priority_deque.insert(projected_point_tuple(point = point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor else LineStringSampling.PointSource.DIRECT), priority) + child.transferred_point_priority_deque.insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor + else LineStringSampling.PointSource.DIRECT), priority) for child in child_list_forbidden: - point, priority = calc_transferred_point(bisectorline_forbidden_point_child,child) - if point == None: + point, priority = calc_transferred_point( + bisectorline_forbidden_point_child, child) + if point is None: continue - child.transferred_point_priority_deque.insert(projected_point_tuple(point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) - + child.transferred_point_priority_deque.insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) + for neighbor in neighbor_list: - point, priority = calc_transferred_point(bisectorline_neighbor,neighbor) - if point==None: + point, priority = calc_transferred_point( + bisectorline_neighbor, neighbor) + if point is None: continue - neighbor.transferred_point_priority_deque.insert(projected_point_tuple(point = point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor else LineStringSampling.PointSource.DIRECT), priority) + neighbor.transferred_point_priority_deque.insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor + else LineStringSampling.PointSource.DIRECT), priority) for neighbor in neighbor_list_forbidden: - point, priority = calc_transferred_point(bisectorline_forbidden_point_neighbor,neighbor) - if point == None: + point, priority = calc_transferred_point( + bisectorline_forbidden_point_neighbor, neighbor) + if point is None: continue - neighbor.transferred_point_priority_deque.insert(projected_point_tuple(point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) + neighbor.transferred_point_priority_deque.insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) i += 1 currentDistance += next_spacing assert(len(point_list) == len(point_source_list)) -#Calculated 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. +# Calculated 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: @@ -274,41 +297,44 @@ def calc_transferred_point_graph(bisectorline, edge_geometry): resultlist = list(result) desired_point = resultlist[0] if len(resultlist) > 1: - desired_point = nearest_points(result, Point(bisectorline.coords[0]))[0] + desired_point = nearest_points( + result, Point(bisectorline.coords[0]))[0] priority = edge_geometry.project(desired_point) point = desired_point return point, priority -#Takes the current tree item and its rastered points (to_transfer_points) and transfers these points to its parent, siblings and childs -# To do so it calculates the current normal and determines its intersection with the neighbors which gives the transferred points. -#Input: -#-treenode: Tree node whose points stored in "to_transfer_points" shall be transferred to its neighbors. -#-used_offset: The used offset when the curves where offsetted -#-offset_by_half: True if the transferred points shall be interlaced with respect to the points in "to_transfer_points" -#-max_stitching_distance: The maximum allowed stitch distance between two points -#-to_transfer_points: List of points belonging to treenode which shall be transferred - it is assumed that to_transfer_points can be handled as closed ring -#-to_transfer_points_origin: The origin tag of each point in to_transfer_points -#-overnext_neighbor: Transfer the points to the overnext neighbor (gives a more stable interlacing) -#-transfer_forbidden_points: Only allowed for interlacing (offset_by_half): Might be used to transfer points unshifted as forbidden points to the neighbor to avoid a point placing there -#-transfer_to_parent: If True, points will be transferred to the parent -#-transfer_to_sibling: If True, points will be transferred to the siblings -#-transfer_to_child: If True, points will be transferred to the childs -#Output: -#-Fills the attribute "transferred_point_priority_deque" of the siblings and parent in the tree datastructure. An item of the deque -#is setup as follows: ((projected point on line, LineStringSampling.PointSource), priority=distance along line) -#index of point_origin is the index of the point in the neighboring line def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_offset, offset_by_half, to_transfer_points, - overnext_neighbor = False, transfer_forbidden_points = False, transfer_to_previous=True, transfer_to_next=True): + overnext_neighbor=False, transfer_forbidden_points=False, transfer_to_previous=True, transfer_to_next=True): + """ + Takes the current graph edge and its rastered points (to_transfer_points) and transfers these points to its previous and next edges (if selected) + To do so it calculates the current normal and determines its intersection with the neighbors which gives the transferred points. + Input: + -fill_stitch_graph: Graph data structure of the stitching lines + -current_edge: Current graph edge whose neighbors in fill_stitch_graph shall be considered + -used_offset: The used offset when the curves where offsetted + -offset_by_half: True if the transferred points shall be interlaced with respect to the points in "to_transfer_points" + -to_transfer_points: List of points belonging to treenode which shall be transferred - it is assumed that to_transfer_points + can be handled as closed ring + -overnext_neighbor: Transfer the points to the overnext neighbor (gives a more stable interlacing) + -transfer_forbidden_points: Only allowed for interlacing (offset_by_half): Might be used to transfer points unshifted as + forbidden points to the neighbor to avoid a point placing there + -transfer_to_previous: If True, points will be transferred to the previous edge in the graph + -transfer_to_next: If True, points will be transferred to the next edge in the graph + Output: + -Fills the attribute "transferred_point_priority_deque" of the next/previous edges. An item of the deque + is setup as follows: ((projected point on line, LineStringSampling.PointSource), priority=distance along line) + index of point_origin is the index of the point in the neighboring line + """ assert((overnext_neighbor and not offset_by_half) or not overnext_neighbor) - assert(not transfer_forbidden_points or transfer_forbidden_points and (offset_by_half or not offset_by_half and overnext_neighbor)) + 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: return - # Take only neighbors which have not rastered before # We need to distinguish between childs (project towards inner) and parent/siblings (project towards outer) previous_edge_list = [] @@ -319,7 +345,8 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o if transfer_to_previous: previous_neighbors_tuples = current_edge['previous_neighbors'] for neighbor in previous_neighbors_tuples: - neighbor_edge = fill_stitch_graph[neighbor[0]][neighbor[-1]]['segment'] + neighbor_edge = fill_stitch_graph[neighbor[0] + ][neighbor[-1]]['segment'] if not neighbor_edge['already_rastered']: if not overnext_neighbor: previous_edge_list.append(neighbor_edge) @@ -328,14 +355,16 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o if overnext_neighbor: overnext_previous_neighbors_tuples = neighbor_edge['previous_neighbors'] for overnext_neighbor in overnext_previous_neighbors_tuples: - overnext_neighbor_edge = fill_stitch_graph[overnext_neighbor[0]][overnext_neighbor[-1]]['segment'] + overnext_neighbor_edge = fill_stitch_graph[overnext_neighbor[0] + ][overnext_neighbor[-1]]['segment'] if not overnext_neighbor_edge['already_rastered']: previous_edge_list.append(overnext_neighbor_edge) if transfer_to_next: next_neighbors_tuples = current_edge['next_neighbors'] for neighbor in next_neighbors_tuples: - neighbor_edge = fill_stitch_graph[neighbor[0]][neighbor[-1]]['segment'] + neighbor_edge = fill_stitch_graph[neighbor[0] + ][neighbor[-1]]['segment'] if not neighbor_edge['already_rastered']: if not overnext_neighbor: next_edge_list.append(neighbor_edge) @@ -344,11 +373,11 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o if overnext_neighbor: overnext_next_neighbors_tuples = neighbor_edge['next_neighbors'] for overnext_neighbor in overnext_next_neighbors_tuples: - overnext_neighbor_edge = fill_stitch_graph[overnext_neighbor[0]][overnext_neighbor[-1]]['segment'] + overnext_neighbor_edge = fill_stitch_graph[overnext_neighbor[0] + ][overnext_neighbor[-1]]['segment'] if not overnext_neighbor_edge['already_rastered']: next_edge_list.append(overnext_neighbor_edge) - if not previous_edge_list and not next_edge_list: return @@ -357,19 +386,19 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o line = LineString(to_transfer_points) bisectorline_length = abs(used_offset) * \ - constants.transfer_point_distance_factor*(2.0 if overnext_neighbor else 1.0) + constants.transfer_point_distance_factor * \ + (2.0 if overnext_neighbor else 1.0) bisectorline_length_forbidden_points = abs(used_offset) * \ constants.transfer_point_distance_factor linesign_child = math.copysign(1, used_offset) - i = 0 currentDistance = 0 while i < len(point_list): - - #if abs(point_list[i].coords[0][0]-47) < 0.3 and abs(point_list[i].coords[0][1]-4.5) < 0.3: + + # if abs(point_list[i].coords[0][0]-47) < 0.3 and abs(point_list[i].coords[0][1]-4.5) < 0.3: # print("HIIIIIIIIIIIERRR") # We create a bisecting line through the current point @@ -383,7 +412,6 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o normalized_vector_prev_x /= prev_spacing normalized_vector_prev_y /= prev_spacing - normalized_vector_next_x = normalized_vector_next_y = 0 next_spacing = 0 while True: @@ -416,13 +444,15 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o vecy = -linesign_child*bisectorline_length*normalized_vector_next_x if transfer_forbidden_points: - vecx_forbidden_point = linesign_child*bisectorline_length_forbidden_points*normalized_vector_next_y - vecy_forbidden_point = -linesign_child*bisectorline_length_forbidden_points*normalized_vector_next_x + vecx_forbidden_point = linesign_child * \ + bisectorline_length_forbidden_points*normalized_vector_next_y + vecy_forbidden_point = -linesign_child * \ + bisectorline_length_forbidden_points*normalized_vector_next_x else: vecx *= bisectorline_length/vec_length vecy *= bisectorline_length/vec_length - + if (vecx*normalized_vector_next_y-vecy * normalized_vector_next_x)*linesign_child < 0: vecx = -vecx vecy = -vecy @@ -446,22 +476,25 @@ def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_o originPoint.coords[0][1]+vecy)]) bisectorline_forbidden_point = LineString([(originPoint_forbidden_point.coords[0][0]-vecx_forbidden_point, - originPoint_forbidden_point.coords[0][1]-vecy_forbidden_point), - (originPoint_forbidden_point.coords[0][0]+vecx_forbidden_point, - originPoint_forbidden_point.coords[0][1]+vecy_forbidden_point)]) - + originPoint_forbidden_point.coords[0][1]-vecy_forbidden_point), + (originPoint_forbidden_point.coords[0][0]+vecx_forbidden_point, + originPoint_forbidden_point.coords[0][1]+vecy_forbidden_point)]) for edge in previous_edge_list+next_edge_list: - point, priority = calc_transferred_point_graph(bisectorline,edge['geometry']) - if point==None: + point, priority = calc_transferred_point_graph( + bisectorline, edge['geometry']) + if point is None: continue - edge['projected_points'].insert(projected_point_tuple(point = point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor else LineStringSampling.PointSource.DIRECT), priority) + edge['projected_points'].insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.OVERNEXT if overnext_neighbor + else LineStringSampling.PointSource.DIRECT), priority) for edge_forbidden in previous_edge_list_forbidden+next_edge_list_forbidden: - point, priority = calc_transferred_point_graph(bisectorline_forbidden_point,edge_forbidden['geometry']) - if point == None: + point, priority = calc_transferred_point_graph( + bisectorline_forbidden_point, edge_forbidden['geometry']) + if point is None: continue - edge_forbidden['projected_points'].insert(projected_point_tuple(point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) - - + edge_forbidden['projected_points'].insert(projected_point_tuple( + point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority) + i += 1 currentDistance += next_spacing diff --git a/lib/stitches/StitchPattern.py b/lib/stitches/StitchPattern.py index d0a3f7aa..ba3e3031 100644 --- a/lib/stitches/StitchPattern.py +++ b/lib/stitches/StitchPattern.py @@ -1,6 +1,6 @@ from shapely.geometry.polygon import LinearRing, LineString from shapely.geometry import Polygon, MultiLineString -from shapely.ops import polygonize +from shapely.ops import polygonize from shapely.geometry import MultiPolygon from anytree import AnyNode, PreOrderIter from shapely.geometry.polygon import orient @@ -10,68 +10,90 @@ from ..stitches import ConnectAndSamplePattern from ..stitches import constants - -# Problem: When shapely offsets a LinearRing the start/end point might be handled wrongly since they are only treated as LineString. -# (See e.g. https://i.stack.imgur.com/vVh56.png as a problematic example) -# This method checks first whether the start/end point form a problematic edge with respect to the offset side. If it is not a problematic -# edge we can use the normal offset_routine. Otherwise we need to perform two offsets: -# -offset the ring -# -offset the start/end point + its two neighbors left and right -# Finally both offsets are merged together to get the correct offset of a LinearRing def offset_linear_ring(ring, offset, side, resolution, join_style, mitre_limit): + """ + Solves following problem: When shapely offsets a LinearRing the + start/end point might be handled wrongly since they + are only treated as LineString. + (See e.g. https://i.stack.imgur.com/vVh56.png as a problematic example) + This method checks first whether the start/end point form a problematic + edge with respect to the offset side. If it is not a problematic + edge we can use the normal offset_routine. Otherwise we need to + perform two offsets: + -offset the ring + -offset the start/end point + its two neighbors left and right + Finally both offsets are merged together to get the correct + offset of a LinearRing + """ + coords = ring.coords[:] - # check whether edge at index 0 is concave or convex. Only for concave edges we need to spend additional effort + # check whether edge at index 0 is concave or convex. Only for + # concave edges we need to spend additional effort dx_seg1 = dy_seg1 = 0 if coords[0] != coords[-1]: - dx_seg1 = coords[0][0]-coords[-1][0] - dy_seg1 = coords[0][1]-coords[-1][1] + dx_seg1 = coords[0][0] - coords[-1][0] + dy_seg1 = coords[0][1] - coords[-1][1] else: - dx_seg1 = coords[0][0]-coords[-2][0] - dy_seg1 = coords[0][1]-coords[-2][1] - dx_seg2 = coords[1][0]-coords[0][0] - dy_seg2 = coords[1][1]-coords[0][1] + dx_seg1 = coords[0][0] - coords[-2][0] + dy_seg1 = coords[0][1] - coords[-2][1] + dx_seg2 = coords[1][0] - coords[0][0] + dy_seg2 = coords[1][1] - coords[0][1] # use cross product: - crossvalue = dx_seg1*dy_seg2-dy_seg1*dx_seg2 + crossvalue = dx_seg1 * dy_seg2 - dy_seg1 * dx_seg2 sidesign = 1 - if side == 'left': + if side == "left": sidesign = -1 - # We do not need to take care of the joint n-0 since we offset along a concave edge: - if sidesign*offset*crossvalue <= 0: + # We do not need to take care of the joint n-0 since we + # offset along a concave edge: + if sidesign * offset * crossvalue <= 0: return ring.parallel_offset(offset, side, resolution, join_style, mitre_limit) # We offset along a convex edge so we offset the joint n-0 separately: if coords[0] != coords[-1]: coords.append(coords[0]) offset_ring1 = ring.parallel_offset( - offset, side, resolution, join_style, mitre_limit) + offset, side, resolution, join_style, mitre_limit + ) offset_ring2 = LineString((coords[-2], coords[0], coords[1])).parallel_offset( - offset, side, resolution, join_style, mitre_limit) + offset, side, resolution, join_style, mitre_limit + ) # Next we need to merge the results: - if offset_ring1.geom_type == 'LineString': - return LinearRing(offset_ring2.coords[:]+offset_ring1.coords[1:-1]) + if offset_ring1.geom_type == "LineString": + return LinearRing(offset_ring2.coords[:] + offset_ring1.coords[1:-1]) else: - # We have more than one resulting LineString for offset of the geometry (ring) = offset_ring1. - # Hence we need to find the LineString which belongs to the offset of element 0 in coords =offset_ring2 + # We have more than one resulting LineString for offset of + # the geometry (ring) = offset_ring1. + # Hence we need to find the LineString which belongs to the + # offset of element 0 in coords =offset_ring2 # in order to add offset_ring2 geometry to it: result_list = [] - thresh = constants.offset_factor_for_adjacent_geometry*abs(offset) + thresh = constants.offset_factor_for_adjacent_geometry * abs(offset) for offsets in offset_ring1: - if(abs(offsets.coords[0][0]-coords[0][0]) < thresh and abs(offsets.coords[0][1]-coords[0][1]) < thresh): - result_list.append(LinearRing( - offset_ring2.coords[:]+offsets.coords[1:-1])) + if ( + abs(offsets.coords[0][0] - coords[0][0]) < thresh + and abs(offsets.coords[0][1] - coords[0][1]) < thresh + ): + result_list.append( + LinearRing(offset_ring2.coords[:] + offsets.coords[1:-1]) + ) else: result_list.append(LinearRing(offsets)) return MultiLineString(result_list) -# Removes all geometries which do not form a "valid" LinearRing (meaning a ring which does not form a straight line) def take_only_valid_linear_rings(rings): - if(rings.geom_type == 'MultiLineString'): + """ + Removes all geometries which do not form a "valid" LinearRing + (meaning a ring which does not form a straight line) + """ + if rings.geom_type == "MultiLineString": new_list = [] for ring in rings: - if len(ring.coords) > 3 or (len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1]): + if len(ring.coords) > 3 or ( + len(ring.coords) == 3 and ring.coords[0] != ring.coords[-1] + ): new_list.append(ring) if len(new_list) == 1: return LinearRing(new_list[0]) @@ -86,138 +108,184 @@ def take_only_valid_linear_rings(rings): return rings -#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) def make_tree_uniform_ccw(root): + """ + 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 PreOrderIter(root): - if(node.id == 'hole'): + if node.id == "hole": node.val.coords = list(node.val.coords)[::-1] -#Used to define which stitching strategy shall be used +# Used to define which stitching strategy shall be used class StitchingStrategy(IntEnum): CLOSEST_POINT = 0 INNER_TO_OUTER = 1 -# Takes a polygon (which can have holes) as input and creates offsetted versions until the polygon is filled with these smaller offsets. -# These created geometries are afterwards connected to each other and resampled with a maximum stitch_distance. -# The return value is a LineString which should cover the full polygon. -#Input: -#-poly: The shapely polygon which can have holes -#-offset: The used offset for the curves -#-join_style: Join style for the offset - can be round, mitered or bevel (https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE) -#For examples look at https://shapely.readthedocs.io/en/stable/_images/parallel_offset.png -#-stitch_distance maximum allowed stitch distance between two points -#-offset_by_half: True if the points shall be interlaced -#-strategy: According to StitchingStrategy you can select between different strategies for the connection between parent and childs -#Output: -#-List of point coordinate tuples -#-Tag (origin) of each point to analyze why a point was placed at this position -def offset_poly(poly, offset, join_style, stitch_distance, offset_by_half, strategy, starting_point): + +def offset_poly( + poly, offset, join_style, stitch_distance, offset_by_half, strategy, starting_point +): + """ + Takes a polygon (which can have holes) as input and creates offsetted + versions until the polygon is filled with these smaller offsets. + These created geometries are afterwards connected to each other and + resampled with a maximum stitch_distance. + The return value is a LineString which should cover the full polygon. + Input: + -poly: The shapely polygon which can have holes + -offset: The used offset for the curves + -join_style: Join style for the offset - can be round, mitered or bevel + (https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.JOIN_STYLE) + For examples look at + https://shapely.readthedocs.io/en/stable/_images/parallel_offset.png + -stitch_distance maximum allowed stitch distance between two points + -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 + -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 + """ ordered_poly = orient(poly, -1) - ordered_poly = ordered_poly.simplify( - constants.simplification_threshold, False) - root = AnyNode(id="node", val=ordered_poly.exterior, already_rastered=False, transferred_point_priority_deque=DEPQ( - iterable=None, maxlen=None)) + ordered_poly = ordered_poly.simplify(constants.simplification_threshold, False) + root = AnyNode( + id="node", + val=ordered_poly.exterior, + already_rastered=False, + transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), + ) active_polys = [root] active_holes = [[]] for holes in ordered_poly.interiors: - #print("hole: - is ccw: ", LinearRing(holes).is_ccw) active_holes[0].append( - AnyNode(id="hole", val=holes, already_rastered=False, transferred_point_priority_deque=DEPQ( - iterable=None, maxlen=None))) + AnyNode( + id="hole", + val=holes, + already_rastered=False, + transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None), + ) + ) - # counter = 0 - while len(active_polys) > 0: # and counter < 20: - # counter += 1 - # print("New iter") + while len(active_polys) > 0: current_poly = active_polys.pop() current_holes = active_holes.pop() poly_inners = [] - # outer = current_poly.val.parallel_offset(offset,'left', 5, join_style, 10) - outer = offset_linear_ring(current_poly.val, offset, 'left', 5, join_style, 10) + outer = offset_linear_ring( + current_poly.val, + offset, + "left", + resolution=5, + joint_style=join_style, + mitre_limit=10, + ) outer = outer.simplify(constants.simplification_threshold, False) outer = take_only_valid_linear_rings(outer) for j in range(len(current_holes)): - # inner = closeLinearRing(current_holes[j].val,offset/2.0).parallel_offset(offset,'left', 5, join_style, 10) inner = offset_linear_ring( - current_holes[j].val, offset, 'left', 5, join_style, 10) + current_holes[j].val, + offset, + "left", + resolution=5, + joint_style=join_style, + mitre_limit=10, + ) inner = inner.simplify(constants.simplification_threshold, False) inner = take_only_valid_linear_rings(inner) if not inner.is_empty: poly_inners.append(Polygon(inner)) if not outer.is_empty: if len(poly_inners) == 0: - if outer.geom_type == 'LineString': + if outer.geom_type == "LineString": result = Polygon(outer) else: result = MultiPolygon(polygonize(outer)) else: - if outer.geom_type == 'LineString': - result = Polygon(outer).difference( - MultiPolygon(poly_inners)) + if outer.geom_type == "LineString": + result = Polygon(outer).difference(MultiPolygon(poly_inners)) else: - result = MultiPolygon(outer).difference( - MultiPolygon(poly_inners)) + result = MultiPolygon(outer).difference(MultiPolygon(poly_inners)) - if not result.is_empty and result.area > offset*offset/10: + if not result.is_empty and result.area > offset * offset / 10: result_list = [] - if result.geom_type == 'Polygon': + if result.geom_type == "Polygon": result_list = [result] else: result_list = list(result) - # print("New result_list: ", len(result_list)) + for polygon in result_list: polygon = orient(polygon, -1) - if polygon.area < offset*offset/10: + if polygon.area < offset * offset / 10: continue - polygon = polygon.simplify(constants.simplification_threshold, False) + polygon = polygon.simplify( + constants.simplification_threshold, False + ) poly_coords = polygon.exterior - # if polygon.exterior.is_ccw: - # hole.coords = list(hole.coords)[::-1] - #poly_coords = polygon.exterior.simplify(constants.simplification_threshold, False) poly_coords = take_only_valid_linear_rings(poly_coords) if poly_coords.is_empty: continue - #print("node: - is ccw: ", LinearRing(poly_coords).is_ccw) - # if(LinearRing(poly_coords).is_ccw): - # print("Fehler!") - node = AnyNode(id="node", parent=current_poly, - val=poly_coords, already_rastered=False, transferred_point_priority_deque=DEPQ( - iterable=None, maxlen=None)) + + node = AnyNode( + id="node", + parent=current_poly, + val=poly_coords, + already_rastered=False, + transferred_point_priority_deque=DEPQ( + iterable=None, maxlen=None + ), + ) active_polys.append(node) hole_node_list = [] for hole in polygon.interiors: hole_node = AnyNode( - id="hole", val=hole, already_rastered=False, transferred_point_priority_deque=DEPQ( - iterable=None, maxlen=None)) + id="hole", + val=hole, + already_rastered=False, + transferred_point_priority_deque=DEPQ( + iterable=None, maxlen=None + ), + ) for previous_hole in current_holes: if Polygon(hole).contains(Polygon(previous_hole.val)): previous_hole.parent = hole_node hole_node_list.append(hole_node) active_holes.append(hole_node_list) - 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 previous_hole.parent == None: + 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 previous_hole.parent is None: previous_hole.parent = current_poly - - #DebuggingMethods.drawPoly(root, 'r-') + # DebuggingMethods.drawPoly(root, 'r-') 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 + ) else: - print("Invalid strategy!") - assert(0) + raise ValueError("Invalid stitching stratety!") return connected_line, connected_line_origin diff --git a/lib/stitches/auto_fill.py b/lib/stitches/auto_fill.py index 71cfd80f..1331ecb2 100644 --- a/lib/stitches/auto_fill.py +++ b/lib/stitches/auto_fill.py @@ -16,7 +16,6 @@ from depq import DEPQ from ..debug import debug from ..stitch_plan import Stitch from ..svg import PIXELS_PER_MM -from ..utils import geometry from ..utils.geometry import Point as InkstitchPoint from ..utils.geometry import line_string_to_point_list from .fill import intersect_region_with_grating, intersect_region_with_grating_line, stitch_row @@ -64,11 +63,12 @@ def auto_fill(shape, ending_point=None, underpath=True, offset_by_half=True): - #offset_by_half only relevant for line != None; staggers only relevant for line == None! + # offset_by_half only relevant for line != None; staggers only relevant for line == None! fill_stitch_graph = [] try: - fill_stitch_graph = build_fill_stitch_graph(shape, line, angle, row_spacing, end_row_spacing, starting_point, ending_point) + fill_stitch_graph = build_fill_stitch_graph( + shape, line, angle, row_spacing, end_row_spacing, 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) @@ -76,10 +76,12 @@ def auto_fill(shape, if not graph_is_valid(fill_stitch_graph, shape, max_stitch_length): return fallback(shape, running_stitch_length) - travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath) - path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point) + 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, staggers, skip_last,line!=None,offset_by_half) + max_stitch_length, running_stitch_length, staggers, skip_last, line is not None, offset_by_half) return result @@ -97,7 +99,8 @@ def which_outline(shape, coords): point = shgeo.Point(*coords) outlines = list(shape.boundary) outline_indices = list(range(len(outlines))) - closest = min(outline_indices, key=lambda index: outlines[index].distance(point)) + closest = min(outline_indices, + key=lambda index: outlines[index].distance(point)) return closest @@ -148,17 +151,18 @@ def build_fill_stitch_graph(shape, line, angle, row_spacing, end_row_spacing, st debug.add_layer("auto-fill fill stitch") - if line == None: + if line is None: # Convert the shape into a set of parallel line segments. - rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing) + rows_of_segments = intersect_region_with_grating( + shape, angle, row_spacing, end_row_spacing) else: - rows_of_segments = intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing) + rows_of_segments = intersect_region_with_grating_line( + shape, line, row_spacing, end_row_spacing) - #segments = [segment for row in rows_of_segments for segment in row] + # 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 @@ -166,16 +170,18 @@ def build_fill_stitch_graph(shape, line, angle, row_spacing, end_row_spacing, st # 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, 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=shgeo.LineString(segment), previous_neighbors = previous_neighbors_, next_neighbors = next_neighbors_, - projected_points=DEPQ(iterable=None, maxlen=None), already_rastered=False) + graph.add_edge(segment[0], segment[-1], key="segment", underpath_edges=[], + geometry=shgeo.LineString(segment), previous_neighbors=previous_neighbors_, next_neighbors=next_neighbors_, + projected_points=DEPQ(iterable=None, maxlen=None), already_rastered=False) -#fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge) +# fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge) tag_nodes_with_outline_and_projection(graph, shape, graph.nodes()) add_edges_between_outline_nodes(graph, duplicate_every_other=True) @@ -205,7 +211,8 @@ def insert_node(graph, shape, point): if key == "outline": edges.append(((start, end), data)) - edge, data = min(edges, key=lambda edge_data: shgeo.LineString(edge_data[0]).distance(projected_point)) + edge, data = min(edges, key=lambda edge_data: shgeo.LineString( + edge_data[0]).distance(projected_point)) graph.remove_edge(*edge, key="outline") graph.add_edge(edge[0], node, key="outline", **data) @@ -218,7 +225,8 @@ def tag_nodes_with_outline_and_projection(graph, shape, nodes): outline_index = which_outline(shape, node) outline_projection = project(shape, node, outline_index) - graph.add_node(node, outline=outline_index, projection=outline_projection) + graph.add_node(node, outline=outline_index, + projection=outline_projection) def add_boundary_travel_nodes(graph, shape): @@ -236,9 +244,11 @@ def add_boundary_travel_nodes(graph, shape): # resolution. A pixel is around a quarter of a millimeter. for i in range(1, int(length)): subpoint = segment.interpolate(i) - graph.add_node((subpoint.x, subpoint.y), projection=outline.project(subpoint), outline=outline_index) + graph.add_node((subpoint.x, subpoint.y), projection=outline.project( + subpoint), outline=outline_index) - graph.add_node((point.x, point.y), projection=outline.project(point), outline=outline_index) + graph.add_node((point.x, point.y), projection=outline.project( + point), outline=outline_index) prev = point @@ -253,7 +263,8 @@ def add_edges_between_outline_nodes(graph, duplicate_every_other=False): outline. """ - nodes = list(graph.nodes(data=True)) # returns a list of tuples: [(node, {data}), (node, {data}) ...] + # returns a list of tuples: [(node, {data}), (node, {data}) ...] + nodes = list(graph.nodes(data=True)) nodes.sort(key=lambda node: (node[1]['outline'], node[1]['projection'])) for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['outline']): @@ -318,7 +329,8 @@ def build_travel_graph(fill_stitch_graph, shape, fill_stitch_angle, underpath): graph.add_nodes_from(fill_stitch_graph.nodes(data=True)) if underpath: - boundary_points, travel_edges = build_travel_edges(shape, fill_stitch_angle) + boundary_points, travel_edges = build_travel_edges( + shape, fill_stitch_angle) # This will ensure that a path traveling inside the shape can reach its # target on the outline, which will be one of the points added above. @@ -349,7 +361,7 @@ def get_segments(graph): for start, end, key, data in graph.edges(keys=True, data=True): if key == 'segment': segments.append(data["geometry"]) - #segments.append(shgeo.LineString((start, end))) + # segments.append(shgeo.LineString((start, end))) return segments @@ -371,7 +383,8 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): # This makes the distance calculations below a bit faster. We're # not looking for high precision anyway. - outline = shape.boundary.simplify(0.5 * PIXELS_PER_MM, preserve_topology=False) + outline = shape.boundary.simplify( + 0.5 * PIXELS_PER_MM, preserve_topology=False) for ls in travel_edges: # In most cases, ls will be a simple line segment. If we're @@ -389,7 +402,8 @@ def process_travel_edges(graph, fill_stitch_graph, shape, travel_edges): if segment.crosses(ls): start = segment.coords[0] end = segment.coords[-1] - fill_stitch_graph[start][end]['segment']['underpath_edges'].append(edge) + fill_stitch_graph[start][end]['segment']['underpath_edges'].append( + edge) # The weight of a travel edge is the length of the line segment. weight = p1.distance(p2) @@ -458,9 +472,12 @@ def build_travel_edges(shape, fill_angle): else: scale = 1.0 - grating1 = travel_grating(shape, fill_angle + math.pi / 4, scale * 2 * PIXELS_PER_MM) - grating2 = travel_grating(shape, fill_angle - math.pi / 4, scale * 2 * PIXELS_PER_MM) - grating3 = travel_grating(shape, fill_angle - math.pi / 2, scale * math.sqrt(2) * PIXELS_PER_MM) + grating1 = travel_grating( + shape, fill_angle + math.pi / 4, scale * 2 * PIXELS_PER_MM) + grating2 = travel_grating( + shape, fill_angle - math.pi / 4, scale * 2 * PIXELS_PER_MM) + grating3 = travel_grating( + shape, fill_angle - math.pi / 2, scale * math.sqrt(2) * PIXELS_PER_MM) debug.add_layer("auto-fill travel") debug.log_line_strings(grating1, "grating1") @@ -471,10 +488,12 @@ def build_travel_edges(shape, fill_angle): for ls in mls for coord in ls.coords] - diagonal_edges = ensure_multi_line_string(grating1.symmetric_difference(grating2)) + diagonal_edges = ensure_multi_line_string( + grating1.symmetric_difference(grating2)) # without this, floating point inaccuracies prevent the intersection points from lining up perfectly. - vertical_edges = ensure_multi_line_string(snap(grating3.difference(grating1), diagonal_edges, 0.005)) + vertical_edges = ensure_multi_line_string( + snap(grating3.difference(grating1), diagonal_edges, 0.005)) return endpoints, chain(diagonal_edges, vertical_edges) @@ -536,7 +555,8 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None last_vertex, last_key = current_vertex, current_key vertex_stack.pop() else: - ignore, next_vertex, next_key = pick_edge(graph.edges(current_vertex, keys=True)) + ignore, next_vertex, next_key = pick_edge( + graph.edges(current_vertex, keys=True)) vertex_stack.append((next_vertex, next_key)) graph.remove_edge(current_vertex, next_vertex, next_key) @@ -565,7 +585,8 @@ def find_stitch_path(graph, travel_graph, starting_point=None, ending_point=None # relevant in the case that the user specifies an underlay with an inset # value, because the starting point (and possibly ending point) can be # inside the shape. - outline_nodes = [node for node, outline in travel_graph.nodes(data="outline") if outline is not None] + outline_nodes = [node for node, outline in travel_graph.nodes( + data="outline") if outline is not None] real_end = nearest_node(outline_nodes, ending_point) path.append(PathEdge((ending_node, real_end), key="outline")) @@ -639,28 +660,31 @@ def travel(travel_graph, start, end, running_stitch_length, skip_last): # stitch. return stitches[1:] -def stitch_line(stitches, stitching_direction, geometry,projected_points, max_stitch_length,row_spacing,skip_last,offset_by_half): - #print(start_point) - #print(geometry[0]) - #if stitching_direction == -1: - # geometry.coords = geometry.coords[::-1] - stitched_line, stitched_line_origin = raster_line_string_with_priority_points_graph(geometry,max_stitch_length,stitching_direction,projected_points,abs(row_spacing),offset_by_half) +def stitch_line(stitches, stitching_direction, geometry, projected_points, max_stitch_length, row_spacing, skip_last, offset_by_half): + # print(start_point) + # print(geometry[0]) + # if stitching_direction == -1: + # geometry.coords = geometry.coords[::-1] + stitched_line, stitched_line_origin = raster_line_string_with_priority_points_graph( + geometry, max_stitch_length, stitching_direction, projected_points, abs(row_spacing), offset_by_half) stitches.append(Stitch(*stitched_line[0], tags=('fill_row_start',))) - for i in range(1,len(stitched_line)): + for i in range(1, len(stitched_line)): 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',))) + 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',))) + 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, - running_stitch_length, staggers, skip_last, offsetted_line, offset_by_half): +def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, max_stitch_length, + running_stitch_length, staggers, skip_last, offsetted_line, offset_by_half): path = collapse_sequential_outline_edges(path) stitches = [] @@ -678,18 +702,24 @@ def path_to_stitches(path, travel_graph, fill_stitch_graph, angle, row_spacing, 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])): + 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) + stitch_line(new_stitches, stitching_direction, path_geometry, projected_points, + max_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) + 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) stitches.extend(new_stitches) else: - stitch_row(stitches, edge[0], edge[1], angle, row_spacing, max_stitch_length, staggers, skip_last) - travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', [])) + stitch_row(stitches, edge[0], edge[1], angle, + row_spacing, max_stitch_length, staggers, skip_last) + 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)) + stitches.extend( + travel(travel_graph, edge[0], edge[1], running_stitch_length, skip_last)) return stitches diff --git a/lib/stitches/constants.py b/lib/stitches/constants.py index 63746310..162c4cfb 100644 --- a/lib/stitches/constants.py +++ b/lib/stitches/constants.py @@ -3,39 +3,60 @@ import math # Used in the simplify routine of shapely simplification_threshold = 0.01 -# If a transferred point is closer than this value to one of its neighbors, it will be checked whether it can be removed +# If a transferred point is closer than this value to one of its neighbors, +# it will be checked whether it can be removed distance_thresh_remove_transferred_point = 0.15 # If a line segment is shorter than this threshold it is handled as a single point line_lengh_seen_as_one_point = 0.05 -# E.g. to check whether a point is already present in a point list, the point is allowed to be this value in distance apart +# E.g. to check whether a point is already present in a point list, +# the point is allowed to be this value in distance apart point_spacing_to_be_considered_equal = 0.05 -# Adjacent geometry should have points closer than offset*offset_factor_for_adjacent_geometry to be considered adjacent +# Adjacent geometry should have points closer than +# offset*offset_factor_for_adjacent_geometry to be considered adjacent offset_factor_for_adjacent_geometry = 1.5 -# Transfer point distance is used for projecting points from already rastered geometry to adjacent geometry -# (max spacing transfer_point_distance_factor*offset) to get a more regular pattern +# Transfer point distance is used for projecting points from already +# rastered geometry to adjacent geometry +# (max spacing transfer_point_distance_factor*offset) +# to get a more regular pattern transfer_point_distance_factor = 1.5 # Used to handle numerical inaccuracies during comparisons -eps = 1E-3 +eps = 1e-3 -factor_offset_starting_points=0.5 #When entering and leaving a child from a parent we introduce an offset of abs_offset*factor_offset_starting_points so - #that entering and leaving points are not lying above each other. +# When entering and leaving a child from a parent we introduce an offset of +# abs_offset*factor_offset_starting_points +# so that entering and leaving points are not lying above each other. +factor_offset_starting_points = 0.5 -factor_offset_remove_points=0.5 #if points are closer than abs_offset*factor_offset_remove_points one of it is removed +# if points are closer than abs_offset*factor_offset_remove_points one of it is removed +factor_offset_remove_points = 0.5 -fac_offset_edge_shift = 0.25 #if an unshifted relevant edge is closer than abs_offset*fac_offset_edge_shift to the line segment created by the shifted edge, - #the shift is allowed - otherwise the edge must not be shifted. +# if an unshifted relevant edge is closer than +# abs_offset*fac_offset_edge_shift +# to the line segment created by the shifted edge, +# the shift is allowed - otherwise the edge must not be shifted. +fac_offset_edge_shift = 0.25 -limiting_angle = math.pi*15/180.0 #decides whether the point belongs to a hard edge (must use this point during sampling) or soft edge (do not necessarily need to use this point) -limiting_angle_straight = math.pi*0.5/180.0 #angles straighter (smaller) than this are considered as more or less straight (no concrete edges required for path segments having only angles <= this value) +# decides whether the point belongs to a hard edge (must use this point during sampling) +# or soft edge (do not necessarily need to use this point) +limiting_angle = math.pi * 15 / 180.0 +# angles straighter (smaller) than this are considered as more or less straight +# (no concrete edges required for path segments having only angles <= this value) +limiting_angle_straight = math.pi * 0.5 / 180.0 -factor_offset_remove_dense_points=0.2 #if a point distance to the connected line of its two neighbors is smaller than abs_offset times this factor, this point will be removed if the stitching distance will not be exceeded +# if a point distance to the connected line of its two neighbors is smaller than +# abs_offset times this factor, this point will be removed if the stitching distance will not be exceeded +factor_offset_remove_dense_points = 0.2 -factor_offset_forbidden_point = 1.0 #if a soft edge is closer to a forbidden point than abs_offset*this factor it will be marked as forbidden. +# if a soft edge is closer to a forbidden point than abs_offset*this factor it will be marked as forbidden. +factor_offset_forbidden_point = 1.0 -factor_segment_length_direct_preferred_over_overnext = 0.5 #usually overnext projected points are preferred. If an overnext projected point would create a much smaller segment than a direct projected point we might prefer the direct projected point +# usually overnext projected points are preferred. +# If an overnext projected point would create a much smaller segment than a direct +# projected point we might prefer the direct projected point +factor_segment_length_direct_preferred_over_overnext = 0.5 diff --git a/lib/stitches/fill.py b/lib/stitches/fill.py index 4e1669e9..9a7254e2 100644 --- a/lib/stitches/fill.py +++ b/lib/stitches/fill.py @@ -12,8 +12,10 @@ 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): - rows_of_segments = intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing, flip) + rows_of_segments = intersect_region_with_grating( + shape, angle, row_spacing, end_row_spacing, flip) groups_of_segments = pull_runs(rows_of_segments, shape, row_spacing) return [section_to_stitches(group, angle, row_spacing, max_stitch_length, staggers, skip_last) @@ -73,7 +75,8 @@ def stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, stagge stitches.append(beg) - first_stitch = adjust_stagger(beg, angle, row_spacing, max_stitch_length, staggers) + first_stitch = adjust_stagger( + beg, angle, row_spacing, max_stitch_length, staggers) # we might have chosen our first stitch just outside this row, so move back in if (first_stitch - beg) * row_direction < 0: @@ -82,13 +85,15 @@ def stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, stagge offset = (first_stitch - beg).length() while offset < segment_length: - stitches.append(Stitch(beg + offset * row_direction, tags=('fill_row'))) + stitches.append( + Stitch(beg + offset * row_direction, tags=('fill_row'))) offset += max_stitch_length if (end - stitches[-1]).length() > 0.1 * PIXELS_PER_MM and not skip_last: stitches.append(end) -def extend_line(line, minx,maxx,miny,maxy): + +def extend_line(line, minx, maxx, miny, maxy): line = line.simplify(0.01, False) upper_left = InkstitchPoint(minx, miny) @@ -103,26 +108,30 @@ def extend_line(line, minx,maxx,miny,maxy): point4 = InkstitchPoint(*line.coords[-1]) new_ending_point = point4+(point4-point3).unit()*length - line = LineString([new_starting_point.as_tuple()]+line.coords[1:-1]+[new_ending_point.as_tuple()]) + line = LineString([new_starting_point.as_tuple()] + + line.coords[1:-1]+[new_ending_point.as_tuple()]) 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 = [] - extend_line(line, minx,maxx,miny,maxy) #extend the line towards the ends to increase probability that all offsetted curves cross the shape + # extend the line towards the ends to increase probability that all offsetted curves cross the shape + extend_line(line, minx, maxx, miny, maxy) line_offsetted = line res = line_offsetted.intersection(shape) while isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)) or (not res.is_empty and len(res.coords) > 1): if isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)): - runs = [line_string.coords for line_string in res.geoms if (not line_string.is_empty and len(line_string.coords) > 1)] + runs = [line_string.coords for line_string in res.geoms if ( + 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()) + runs.sort(key=lambda seg: ( + InkstitchPoint(*seg[0]) - upper_left).length()) if flip: runs.reverse() runs = [tuple(reversed(run)) for run in runs] @@ -130,8 +139,8 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing if row_spacing > 0: rows.append(runs) else: - rows.insert(0,runs) - line_offsetted = line_offsetted.parallel_offset(row_spacing,'left',5) + rows.insert(0, runs) + line_offsetted = line_offsetted.parallel_offset(row_spacing, 'left', 5) if row_spacing < 0: line_offsetted.coords = line_offsetted.coords[::-1] line_offsetted = line_offsetted.simplify(0.01, False) @@ -139,12 +148,13 @@ def intersect_region_with_grating_line(shape, line, row_spacing, end_row_spacing if row_spacing > 0 and not isinstance(res, (shapely.geometry.GeometryCollection, shapely.geometry.MultiLineString)): if (res.is_empty or len(res.coords) == 1): row_spacing = -row_spacing - #print("Set to right") - line_offsetted = line.parallel_offset(row_spacing,'left',5) - line_offsetted.coords = line_offsetted.coords[::-1] #using negative row spacing leads as a side effect to reversed offsetted lines - here we undo this + # print("Set to right") + line_offsetted = line.parallel_offset(row_spacing, 'left', 5) + # 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) res = line_offsetted.intersection(shape) - + return rows @@ -174,7 +184,8 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non # angle degrees clockwise and ask for the new bounding box. The max # and min y tell me how far to go. - _, start, _, end = shapely.affinity.rotate(shape, angle, origin='center', use_radians=True).bounds + _, start, _, end = shapely.affinity.rotate( + shape, angle, origin='center', use_radians=True).bounds # convert start and end to be relative to center (simplifies things later) start -= center.y @@ -211,7 +222,8 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non runs = [res.coords] if runs: - runs.sort(key=lambda seg: (InkstitchPoint(*seg[0]) - upper_left).length()) + runs.sort(key=lambda seg: ( + InkstitchPoint(*seg[0]) - upper_left).length()) if flip: runs.reverse() @@ -220,7 +232,9 @@ def intersect_region_with_grating(shape, angle, row_spacing, end_row_spacing=Non rows.append(runs) if end_row_spacing: - current_row_y += row_spacing + (end_row_spacing - row_spacing) * ((current_row_y - start) / height) + current_row_y += row_spacing + \ + (end_row_spacing - row_spacing) * \ + ((current_row_y - start) / height) else: current_row_y += row_spacing @@ -237,7 +251,8 @@ def section_to_stitches(group_of_segments, angle, row_spacing, max_stitch_length if (swap): (beg, end) = (end, beg) - stitch_row(stitches, beg, end, angle, row_spacing, max_stitch_length, staggers, skip_last) + stitch_row(stitches, beg, end, angle, row_spacing, + max_stitch_length, staggers, skip_last) swap = not swap |