diff options
Diffstat (limited to 'lib/stitches/point_transfer.py')
| -rw-r--r-- | lib/stitches/point_transfer.py | 495 |
1 files changed, 495 insertions, 0 deletions
diff --git a/lib/stitches/point_transfer.py b/lib/stitches/point_transfer.py new file mode 100644 index 00000000..a01e69cd --- /dev/null +++ b/lib/stitches/point_transfer.py @@ -0,0 +1,495 @@ +from shapely.geometry import Point, MultiPoint +from shapely.geometry.polygon import LineString, LinearRing +from collections import namedtuple +from shapely.ops import nearest_points +import math +from ..stitches import constants +from ..stitches import sample_linestring + +"""This file contains routines which shall project already selected points for stitching to remaining +unstitched lines in the neighborhood to create a regular pattern of points.""" + +projected_point_tuple = namedtuple( + 'projected_point_tuple', ['point', 'point_source']) + + +def calc_transferred_point(bisectorline, child): + """ + Calculates the nearest interserction point of "bisectorline" with the coordinates of child (child.val). + It returns the intersection point and its distance along the coordinates of the child or "None, None" if no + intersection was found. + """ + result = bisectorline.intersection(child.val) + if result.is_empty: + return None, None + desired_point = Point() + if result.geom_type == 'Point': + desired_point = result + elif result.geom_type == 'LineString': + desired_point = Point(result.coords[0]) + else: + resultlist = list(result) + desired_point = resultlist[0] + if len(resultlist) > 1: + desired_point = nearest_points( + result, Point(bisectorline.coords[0]))[0] + + priority = child.val.project(desired_point) + point = desired_point + return point, priority + + +def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_transfer_points, to_transfer_points_origin=[], # noqa: C901 + 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)) + + if len(to_transfer_points) == 0: + return + + # Get a list of all possible adjacent nodes which will be considered for transferring the points of treenode: + childs_tuple = treenode.children + siblings_tuple = treenode.siblings + # Take only neighbors which have not rastered before + # We need to distinguish between childs (project towards inner) and parent/siblings (project towards outer) + child_list = [] + child_list_forbidden = [] + neighbor_list = [] + neighbor_list_forbidden = [] + + if transfer_to_child: + for child in childs_tuple: + 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 not subchild.already_rastered: + child_list.append(subchild) + + if transfer_to_sibling: + for sibling in siblings_tuple: + 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 not subchild.already_rastered: + neighbor_list.append(subchild) + + 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) + if transfer_forbidden_points: + neighbor_list_forbidden.append(treenode.parent) + if overnext_neighbor: + 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: + return + + # Go through all rastered points of treenode and check where they should be transferred to its neighbar + point_list = list(MultiPoint(to_transfer_points)) + point_source_list = to_transfer_points_origin.copy() + + # For a linear ring the last point is the same as the starting point which we delete + # since we do not want to transfer the starting and end point twice + closed_line = LineString(to_transfer_points) + if point_list[0].distance(point_list[-1]) < constants.point_spacing_to_be_considered_equal: + point_list.pop() + if(point_source_list): + point_source_list.pop() + if len(point_list) == 0: + return + else: + # closed line is needed if we offset by half since we need to determine the line + # length including the closing segment + closed_line = LinearRing(to_transfer_points) + + bisectorline_length = abs(used_offset) * 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] != + sample_linestring.PointSource.ENTER_LEAVING_POINT) + + # We create a bisecting line through the current point + normalized_vector_prev_x = ( + point_list[i].coords[0][0]-point_list[i-1].coords[0][0]) # makes use of closed shape + normalized_vector_prev_y = ( + point_list[i].coords[0][1]-point_list[i-1].coords[0][1]) + prev_spacing = math.sqrt(normalized_vector_prev_x*normalized_vector_prev_x + + normalized_vector_prev_y*normalized_vector_prev_y) + + 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: + normalized_vector_next_x = ( + point_list[i].coords[0][0]-point_list[(i+1) % len(point_list)].coords[0][0]) + normalized_vector_next_y = ( + point_list[i].coords[0][1]-point_list[(i+1) % len(point_list)].coords[0][1]) + next_spacing = math.sqrt(normalized_vector_next_x*normalized_vector_next_x + + normalized_vector_next_y*normalized_vector_next_y) + if next_spacing < constants.line_lengh_seen_as_one_point: + point_list.pop(i) + if(point_source_list): + point_source_list.pop(i) + currentDistance += next_spacing + continue + + normalized_vector_next_x /= next_spacing + normalized_vector_next_y /= next_spacing + break + + vecx = (normalized_vector_next_x+normalized_vector_prev_x) + vecy = (normalized_vector_next_y+normalized_vector_prev_y) + vec_length = math.sqrt(vecx*vecx+vecy*vecy) + + vecx_forbidden_point = vecx + vecy_forbidden_point = vecy + + # The two sides are (anti)parallel - construct normal vector (bisector) manually: + # If we offset by half we are offseting normal to the next segment + if(vec_length < constants.line_lengh_seen_as_one_point or offset_by_half): + vecx = linesign_child*bisectorline_length*normalized_vector_next_y + 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 + + 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 + vecx_forbidden_point = vecx + vecy_forbidden_point = vecy + + assert((vecx*normalized_vector_next_y-vecy * + normalized_vector_next_x)*linesign_child >= 0) + + originPoint = point_list[i] + originPoint_forbidden_point = point_list[i] + if(offset_by_half): + off = currentDistance+next_spacing/2 + if off > closed_line.length: + off -= closed_line.length + 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)]) + + bisectorline_neighbor = LineString([(originPoint.coords[0][0], + 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)]) + + 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)]) + + for child in child_list: + 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=sample_linestring.PointSource.OVERNEXT if overnext_neighbor + else sample_linestring.PointSource.DIRECT), priority) + for child in child_list_forbidden: + 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=sample_linestring.PointSource.FORBIDDEN_POINT), priority) + + for neighbor in neighbor_list: + 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=sample_linestring.PointSource.OVERNEXT if overnext_neighbor + else sample_linestring.PointSource.DIRECT), priority) + for neighbor in neighbor_list_forbidden: + 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=sample_linestring.PointSource.FORBIDDEN_POINT), priority) + + i += 1 + currentDistance += next_spacing + + assert(len(point_list) == len(point_source_list)) + + +# Calculates the nearest interserction point of "bisectorline" with the coordinates of child. +# It returns the intersection point and its distance along the coordinates of the child or "None, None" if no +# intersection was found. +def calc_transferred_point_graph(bisectorline, edge_geometry): + result = bisectorline.intersection(edge_geometry) + if result.is_empty: + return None, None + desired_point = Point() + if result.geom_type == 'Point': + desired_point = result + elif result.geom_type == 'LineString': + desired_point = Point(result.coords[0]) + else: + resultlist = list(result) + desired_point = resultlist[0] + if len(resultlist) > 1: + desired_point = nearest_points( + result, Point(bisectorline.coords[0]))[0] + + priority = edge_geometry.project(desired_point) + point = desired_point + return point, priority + + +def transfer_points_to_surrounding_graph(fill_stitch_graph, current_edge, used_offset, offset_by_half, to_transfer_points, # noqa: C901 + 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)) + + 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 = [] + previous_edge_list_forbidden = [] + next_edge_list = [] + next_edge_list_forbidden = [] + + 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'] + if not neighbor_edge['already_rastered']: + if not overnext_neighbor: + previous_edge_list.append(neighbor_edge) + if transfer_forbidden_points: + previous_edge_list_forbidden.append(neighbor_edge) + 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'] + 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'] + if not neighbor_edge['already_rastered']: + if not overnext_neighbor: + next_edge_list.append(neighbor_edge) + if transfer_forbidden_points: + next_edge_list_forbidden.append(neighbor_edge) + 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'] + 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 + + # Go through all rastered points of treenode and check where they should be transferred to its neighbar + point_list = list(MultiPoint(to_transfer_points)) + line = LineString(to_transfer_points) + + bisectorline_length = abs(used_offset) * \ + 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): + + # We create a bisecting line through the current point + normalized_vector_prev_x = ( + point_list[i].coords[0][0]-point_list[i-1].coords[0][0]) # makes use of closed shape + normalized_vector_prev_y = ( + point_list[i].coords[0][1]-point_list[i-1].coords[0][1]) + prev_spacing = math.sqrt(normalized_vector_prev_x*normalized_vector_prev_x + + normalized_vector_prev_y*normalized_vector_prev_y) + + 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: + normalized_vector_next_x = ( + point_list[i].coords[0][0]-point_list[(i+1) % len(point_list)].coords[0][0]) + normalized_vector_next_y = ( + point_list[i].coords[0][1]-point_list[(i+1) % len(point_list)].coords[0][1]) + next_spacing = math.sqrt(normalized_vector_next_x*normalized_vector_next_x + + normalized_vector_next_y*normalized_vector_next_y) + if next_spacing < constants.line_lengh_seen_as_one_point: + point_list.pop(i) + currentDistance += next_spacing + continue + + normalized_vector_next_x /= next_spacing + normalized_vector_next_y /= next_spacing + break + + vecx = (normalized_vector_next_x+normalized_vector_prev_x) + vecy = (normalized_vector_next_y+normalized_vector_prev_y) + vec_length = math.sqrt(vecx*vecx+vecy*vecy) + + vecx_forbidden_point = vecx + vecy_forbidden_point = vecy + + # The two sides are (anti)parallel - construct normal vector (bisector) manually: + # If we offset by half we are offseting normal to the next segment + if(vec_length < constants.line_lengh_seen_as_one_point or offset_by_half): + vecx = linesign_child*bisectorline_length*normalized_vector_next_y + 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 + + 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 + vecx_forbidden_point = vecx + vecy_forbidden_point = vecy + + assert((vecx*normalized_vector_next_y-vecy * + normalized_vector_next_x)*linesign_child >= 0) + + originPoint = point_list[i] + originPoint_forbidden_point = point_list[i] + if(offset_by_half): + off = currentDistance+next_spacing/2 + if off > line.length: + break + originPoint = line.interpolate(off) + + bisectorline = LineString([(originPoint.coords[0][0]-vecx, + originPoint.coords[0][1]-vecy), + (originPoint.coords[0][0]+vecx, + 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)]) + + for edge in previous_edge_list+next_edge_list: + 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=sample_linestring.PointSource.OVERNEXT if overnext_neighbor + else sample_linestring.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 is None: + continue + edge_forbidden['projected_points'].insert(projected_point_tuple( + point=point, point_source=sample_linestring.PointSource.FORBIDDEN_POINT), priority) + + i += 1 + currentDistance += next_spacing |