1 files changed, 467 insertions, 0 deletions
diff --git a/lib/stitches/PointTransfer.py b/lib/stitches/PointTransfer.py
new file mode 100644
index 00000000..998282a3
--- /dev/null
+++ b/lib/stitches/PointTransfer.py
@@ -0,0 +1,467 @@
+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 LineStringSampling
+
+projected_point_tuple = namedtuple('projected_point_tuple', ['point', 'point_source'])
+
+#Calculated the nearest interserction point of "bisectorline" with the coordinates of child (child.val). 
+#It returns the intersection point and its distance along the coordinates of the child or "None, None" if no
+#intersection was found.
+def calc_transferred_point(bisectorline, child):
+    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
+
+
+#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)
+    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 child.already_rastered == False:
+                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:
+                        child_list.append(subchild)
+
+    if transfer_to_sibling:
+        for sibling in siblings_tuple:
+            if sibling.already_rastered == False:
+                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:
+                        neighbor_list.append(subchild)
+
+    if transfer_to_parent and treenode.parent != None:
+        if treenode.parent.already_rastered == False:
+            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 != None:
+                if treenode.parent.parent.already_rastered == False:
+                    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] != 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
+        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==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)
+        for child in child_list_forbidden:
+            point, priority = calc_transferred_point(bisectorline_forbidden_point_child,child)
+            if point == None:
+                continue
+            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:
+                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)
+        for neighbor in neighbor_list_forbidden:
+            point, priority = calc_transferred_point(bisectorline_forbidden_point_neighbor,neighbor)
+            if point == None:
+                continue
+            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.
+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
+
+
+#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):
+
+    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):
+       
+        #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
+        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==None:
+                continue
+            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:
+                continue
+            edge_forbidden['projected_points'].insert(projected_point_tuple(point=point, point_source=LineStringSampling.PointSource.FORBIDDEN_POINT), priority)
+        
+        
+        i += 1
+        currentDistance += next_spacing