avoid anytree dependency

4 files changed, 261 insertions, 221 deletions

diff --git a/lib/stitches/point_transfer.py b/lib/stitches/point_transfer.py
index 553ffbda..c0d519ef 100644
--- a/lib/stitches/point_transfer.py
+++ b/lib/stitches/point_transfer.py
@@ -15,7 +15,7 @@ projected_point_tuple = namedtuple(
 
 def calc_transferred_point(bisectorline, child):
     """
-    Calculates the nearest interserction point of "bisectorline" with the coordinates of child (child.val).
+    Calculates the nearest intersection 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.
     """
@@ -39,7 +39,7 @@ def calc_transferred_point(bisectorline, child):
     return point, priority
 
 
-def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_transfer_points,  to_transfer_points_origin=[],  # noqa: C901
+def transfer_points_to_surrounding(tree, node, 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):
     """
@@ -64,18 +64,24 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra
     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 (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) < 3:
         return
 
+    current_node = tree.nodes[node]
+
     # 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
+    childs_tuple = tuple(tree.successors(node))
+    if current_node.parent:
+        siblings_tuple = tuple(child for child in tree[current_node.parent] if child != node)
+    else:
+        siblings_tuple = ()
+
     # 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 = []
@@ -85,38 +91,39 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra
 
     if transfer_to_child:
         for child in childs_tuple:
-            if not child.already_rastered:
+            if not tree.nodes[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)
+                for grandchild in tree[child]:
+                    if not tree.nodes[grandchild].already_rastered:
+                        child_list.append(grandchild)
 
     if transfer_to_sibling:
         for sibling in siblings_tuple:
-            if not sibling.already_rastered:
+            if not tree.nodes[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)
+                for nibling in tree[sibling]:
+                    if not tree.nodes[nibling].already_rastered:
+                        neighbor_list.append(nibling)
 
-    if transfer_to_parent and treenode.parent is not None:
-        if not treenode.parent.already_rastered:
+    if transfer_to_parent and current_node.parent is not None:
+        if not tree.nodes[current_node.parent].already_rastered:
             if not overnext_neighbor:
-                neighbor_list.append(treenode.parent)
+                neighbor_list.append(current_node.parent)
             if transfer_forbidden_points:
-                neighbor_list_forbidden.append(treenode.parent)
+                neighbor_list_forbidden.append(current_node.parent)
         if overnext_neighbor:
-            if treenode.parent.parent is not None:
-                if not treenode.parent.parent.already_rastered:
-                    neighbor_list.append(treenode.parent.parent)
+            grandparent = tree.nodes[current_node].parent
+            if grandparent is not None:
+                if not tree.nodes[grandparent].already_rastered:
+                    neighbor_list.append(grandparent)
 
     if not neighbor_list and not child_list:
         return
@@ -130,7 +137,7 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra
     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):
+        if point_source_list:
             point_source_list.pop()
         if len(point_list) == 0:
             return
@@ -243,34 +250,35 @@ def transfer_points_to_surrounding(treenode, used_offset, offset_by_half, to_tra
                                                              originPoint_forbidden_point.coords[0][1]-vecy_forbidden_point)])
 
         for child in child_list:
-            point, priority = calc_transferred_point(bisectorline_child, child)
+            current_child = tree.nodes[child]
+            point, priority = calc_transferred_point(bisectorline_child, current_child)
             if point is None:
                 continue
-            child.transferred_point_priority_deque.insert(projected_point_tuple(
+            current_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)
+            current_child = tree.nodes[child]
+            point, priority = calc_transferred_point(bisectorline_forbidden_point_child, current_child)
             if point is None:
                 continue
-            child.transferred_point_priority_deque.insert(projected_point_tuple(
+            current_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)
+            current_neighbor = tree.nodes[neighbor]
+            point, priority = calc_transferred_point(bisectorline_neighbor, current_neighbor)
             if point is None:
                 continue
-            neighbor.transferred_point_priority_deque.insert(projected_point_tuple(
+            current_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)
+            current_neighbor = tree.nodes[neighbor]
+            point, priority = calc_transferred_point(bisectorline_forbidden_point_neighbor, current_neighbor)
             if point is None:
                 continue
-            neighbor.transferred_point_priority_deque.insert(projected_point_tuple(
+            current_neighbor.transferred_point_priority_deque.insert(projected_point_tuple(
                 point=point, point_source=sample_linestring.PointSource.FORBIDDEN_POINT), priority)
 
         i += 1
diff --git a/lib/stitches/tangential_fill_stitch_line_creator.py b/lib/stitches/tangential_fill_stitch_line_creator.py
index 6b141611..deb87659 100644
--- a/lib/stitches/tangential_fill_stitch_line_creator.py
+++ b/lib/stitches/tangential_fill_stitch_line_creator.py
@@ -1,6 +1,6 @@
 from enum import IntEnum
 
-from anytree import AnyNode, LevelOrderGroupIter, PreOrderIter
+import networkx as nx
 from depq import DEPQ
 from shapely.geometry import MultiLineString, Polygon
 from shapely.geometry import MultiPolygon
@@ -10,6 +10,13 @@ from shapely.ops import polygonize
 
 from ..stitches import constants
 from ..stitches import tangential_fill_stitch_pattern_creator
+from ..utils import DotDict
+
+
+class Tree(nx.DiGraph):
+    # This lets us do tree.nodes['somenode'].parent instead of the default
+    # tree.nodes['somenode']['parent'].
+    node_attr_dict_factory = DotDict
 
 
 def offset_linear_ring(ring, offset, resolution, join_style, mitre_limit):
@@ -126,15 +133,15 @@ def take_only_valid_linear_rings(rings):
         return LinearRing()
 
 
-def make_tree_uniform_ccw(root):
+def make_tree_uniform_ccw(tree):
     """
     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":
-            node.val.coords = list(node.val.coords)[::-1]
+    for node in nx.dfs_preorder_nodes(tree, 'root'):
+        if tree.nodes[node].type == "hole":
+            tree.nodes[node].val = LinearRing(reversed(tree.nodes[node].val.coords))
 
 
 # Used to define which stitching strategy shall be used
@@ -144,7 +151,7 @@ class StitchingStrategy(IntEnum):
     SPIRAL = 2
 
 
-def check_and_prepare_tree_for_valid_spiral(root):
+def check_and_prepare_tree_for_valid_spiral(tree):
     """
     Takes a tree consisting of offsetted curves. If a parent has more than one child we
     cannot create a spiral. However, to make the routine more robust, we allow more than
@@ -153,27 +160,34 @@ def check_and_prepare_tree_for_valid_spiral(root):
     childs. If the routine returns false even under the mentioned weaker conditions the
     tree cannot be connected by one spiral.
     """
-    for children in LevelOrderGroupIter(root):
-        if len(children) > 1:
-            count = 0
-            child_with_children = None
-            for child in children:
-                if not child.is_leaf:
-                    count += 1
-                    child_with_children = child
-            if count > 1:
+
+    def process_node(node):
+        children = set(tree[node])
+
+        if len(children) == 0:
+            return True
+        elif len(children) == 1:
+            child = children.pop()
+            return process_node(child)
+        else:
+            children_with_children = {child for child in children if tree[child]}
+            if len(children_with_children) > 1:
+                # Node has multiple children with children, so a perfect spiral is not possible.
+                # This False value will be returned all the way up the stack.
                 return False
-            elif count == 1:
-                child_with_children.parent.children = [child_with_children]
-            else:  # count == 0 means all childs have no children so we take only the longest child
-                max_length = 0
-                longest_child = None
-                for child in children:
-                    if child.val.length > max_length:
-                        max_length = child.val.length
-                        longest_child = child
-                longest_child.parent.children = [longest_child]
-    return True
+            elif len(children_with_children) == 1:
+                children_without_children = children - children_with_children
+                child = children_with_children.pop()
+                tree.remove_nodes_from(children_without_children)
+                return process_node(child)
+            else:
+                # None of the children has its own children, so we'll just take the longest.
+                longest = max(children, key=lambda child: tree[child]['val'].length)
+                shorter_children = children - {longest}
+                tree.remove_nodes_from(shorter_children)
+                return process_node(longest)
+
+    return process_node('root')
 
 
 def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance, offset_by_half, strategy, starting_point):  # noqa: C901
@@ -213,25 +227,29 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
     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),
-    )
-    active_polys = [root]
+    tree = Tree()
+    tree.add_node('root',
+                  type='node',
+                  parent=None,
+                  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:
-        active_holes[0].append(
-            AnyNode(
-                id="hole",
-                val=holes,
-                already_rastered=False,
-                transferred_point_priority_deque=DEPQ(
-                    iterable=None, maxlen=None),
-            )
-        )
+    # We don't care about the names of the nodes, we just need them to be unique.
+    node_num = 0
+
+    for hole in ordered_poly.interiors:
+        tree.add_node(node_num,
+                      type="hole",
+                      val=hole,
+                      already_rastered=False,
+                      transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None),
+                      )
+        active_holes[0].append(node_num)
+        node_num += 1
 
     while len(active_polys) > 0:
         current_poly = active_polys.pop()
@@ -239,7 +257,7 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
         poly_inners = []
 
         outer = offset_linear_ring(
-            current_poly.val,
+            tree.nodes[current_poly].val,
             offset,
             resolution=5,
             join_style=join_style,
@@ -248,9 +266,9 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
         outer = outer.simplify(constants.simplification_threshold, False)
         outer = take_only_valid_linear_rings(outer)
 
-        for j in range(len(current_holes)):
+        for hole in current_holes:
             inner = offset_linear_ring(
-                current_holes[j].val,
+                tree.nodes[hole].val,
                 -offset,  # take negative offset for holes
                 resolution=5,
                 join_style=join_style,
@@ -275,11 +293,10 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
                         MultiPolygon(poly_inners))
 
             if not result.is_empty and result.area > offset * offset / 10:
-                result_list = []
                 if result.geom_type == "Polygon":
                     result_list = [result]
                 else:
-                    result_list = list(result)
+                    result_list = list(result.geoms)
 
                 for polygon in result_list:
                     polygon = orient(polygon, -1)
@@ -295,29 +312,31 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
                     if poly_coords.is_empty:
                         continue
 
-                    node = AnyNode(
-                        id="node",
-                        parent=current_poly,
-                        val=poly_coords,
-                        already_rastered=False,
-                        transferred_point_priority_deque=DEPQ(
-                            iterable=None, maxlen=None
-                        ),
-                    )
+                    node = node_num
+                    node_num += 1
+                    tree.add_node(node,
+                                  type='node',
+                                  parent=current_poly,
+                                  val=poly_coords,
+                                  already_rastered=False,
+                                  transferred_point_priority_deque=DEPQ(iterable=None, maxlen=None),
+                                  )
+                    tree.add_edge(current_poly, node)
                     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
-                            ),
-                        )
+                        hole_node = node_num
+                        node_num += 1
+                        tree.add_node(hole_node,
+                                      type="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
+                            if Polygon(hole).contains(Polygon(tree.nodes[previous_hole].val)):
+                                tree.nodes[previous_hole].parent = hole_node
+                                tree.add_edge(hole_node, previous_hole)
                         hole_node_list.append(hole_node)
                     active_holes.append(hole_node_list)
         for previous_hole in current_holes:
@@ -325,23 +344,23 @@ def offset_poly(poly, offset, join_style, stitch_distance, min_stitch_distance,
             # contained in the new holes they
             # have been merged with the
             # outer polygon
-            if previous_hole.parent is None:
-                previous_hole.parent = current_poly
+            if tree.nodes[previous_hole].parent is None:
+                tree.nodes[previous_hole].parent = current_poly
+                tree.add_edge(current_poly, previous_hole)
 
-    # print(RenderTree(root))
-    make_tree_uniform_ccw(root)
+    make_tree_uniform_ccw(tree)
 
     if strategy == StitchingStrategy.CLOSEST_POINT:
         (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_nearest_neighbor(
-            root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
+            tree, 'root', offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
     elif strategy == StitchingStrategy.INNER_TO_OUTER:
         (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_from_inner_to_outer(
-            root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
+            tree, 'root', offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
     elif strategy == StitchingStrategy.SPIRAL:
-        if not check_and_prepare_tree_for_valid_spiral(root):
+        if not check_and_prepare_tree_for_valid_spiral(tree):
             raise ValueError("Geometry cannot be filled with one spiral!")
         (connected_line, connected_line_origin) = tangential_fill_stitch_pattern_creator.connect_raster_tree_spiral(
-            root, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
+            tree, offset, stitch_distance, min_stitch_distance, starting_point, offset_by_half)
     else:
         raise ValueError("Invalid stitching stratety!")
 
diff --git a/lib/stitches/tangential_fill_stitch_pattern_creator.py b/lib/stitches/tangential_fill_stitch_pattern_creator.py
index 084b1d01..1b085ed6 100644
--- a/lib/stitches/tangential_fill_stitch_pattern_creator.py
+++ b/lib/stitches/tangential_fill_stitch_pattern_creator.py
@@ -3,7 +3,7 @@ from collections import namedtuple
 
 import numpy as np
 import trimesh
-from anytree import PreOrderIter
+import networkx as nx
 from depq import DEPQ
 from shapely.geometry import MultiPoint, Point
 from shapely.geometry.polygon import LineString, LinearRing
@@ -54,7 +54,7 @@ def cut(line, distance):
 
 
 def connect_raster_tree_nearest_neighbor(  # noqa: C901
-        tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half):
+        tree, node, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half):
     """
     Takes the offsetted curves organized as tree, connects and samples them.
     Strategy: A connection from parent to child is made where both curves
@@ -77,20 +77,21 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
      placed at this position
     """
 
-    current_coords = tree.val
+    current_node = tree.nodes[node]
+    current_coords = current_node.val
     abs_offset = abs(used_offset)
     result_coords = []
     result_coords_origin = []
 
     # We cut the current item so that its index 0 is closest to close_point
-    start_distance = tree.val.project(close_point)
+    start_distance = current_coords.project(close_point)
     if start_distance > 0:
         current_coords = cut(current_coords, start_distance)
-        tree.val = current_coords
+        current_node.val = current_coords
 
-        if not tree.transferred_point_priority_deque.is_empty():
+        if not current_node.transferred_point_priority_deque.is_empty():
             new_DEPQ = DEPQ(iterable=None, maxlen=None)
-            for item, priority in tree.transferred_point_priority_deque:
+            for item, priority in current_node.transferred_point_priority_deque:
                 new_DEPQ.insert(
                     item,
                     math.fmod(
@@ -98,7 +99,7 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
                         current_coords.length,
                     ),
                 )
-            tree.transferred_point_priority_deque = new_DEPQ
+            current_node.transferred_point_priority_deque = new_DEPQ
 
     stitching_direction = 1
     # This list should contain a tuple of nearest points between
@@ -106,8 +107,8 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
     # 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)
+    for subnode in tree[node]:
+        point_parent, point_child = nearest_points(current_coords, tree.nodes[subnode].val)
         proj_distance = current_coords.project(point_parent)
         nearest_points_list.append(
             nearest_neighbor_tuple(
@@ -141,7 +142,7 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
         end_distance,
         stitch_distance,
         min_stitch_distance,
-        tree.transferred_point_priority_deque,
+        current_node.transferred_point_priority_deque,
         abs_offset,
         offset_by_half,
         False)
@@ -149,8 +150,8 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
     assert len(own_coords) == len(own_coords_origin)
     own_coords_origin[0] = sample_linestring.PointSource.ENTER_LEAVING_POINT
     own_coords_origin[-1] = sample_linestring.PointSource.ENTER_LEAVING_POINT
-    tree.stitching_direction = stitching_direction
-    tree.already_rastered = True
+    current_node.stitching_direction = stitching_direction
+    current_node.already_rastered = True
 
     # Next we need to transfer our rastered points to siblings and childs
     to_transfer_point_list = []
@@ -172,6 +173,7 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
     # to use "-used_offset" for stitching_direction==-1
     point_transfer.transfer_points_to_surrounding(
         tree,
+        node,
         stitching_direction * used_offset,
         offset_by_half,
         to_transfer_point_list,
@@ -188,6 +190,7 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
     if offset_by_half:
         point_transfer.transfer_points_to_surrounding(
             tree,
+            node,
             stitching_direction * used_offset,
             False,
             to_transfer_point_list,
@@ -232,6 +235,7 @@ def connect_raster_tree_nearest_neighbor(  # noqa: C901
 
                 item = nearest_points_list[cur_item]
                 (child_coords, child_coords_origin) = connect_raster_tree_nearest_neighbor(
+                    tree,
                     item.child_node,
                     used_offset,
                     stitch_distance,
@@ -324,7 +328,7 @@ def get_nearest_points_closer_than_thresh(travel_line, next_line, thresh):
 
 
 def create_nearest_points_list(
-        travel_line, children_list, threshold, threshold_hard, preferred_direction=0):
+        travel_line, tree, 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
@@ -357,13 +361,13 @@ def create_nearest_points_list(
     weight_reversed_order = 0
     for child in children_list:
         result = get_nearest_points_closer_than_thresh(
-            travel_line, child.val, threshold
+            travel_line, tree.nodes[child].val, threshold
         )
         if result is None:
             # where holes meet outer borders a distance
             # up to 2*used offset can arise
             result = get_nearest_points_closer_than_thresh(
-                travel_line, child.val, threshold_hard
+                travel_line, tree.nodes[child].val, threshold_hard
             )
             assert result is not None
         proj = travel_line.project(result[0])
@@ -378,13 +382,13 @@ def create_nearest_points_list(
         )
 
         result = get_nearest_points_closer_than_thresh(
-            travel_line_reversed, child.val, threshold
+            travel_line_reversed, tree.nodes[child].val, threshold
         )
         if result is None:
             # where holes meet outer borders a distance
             # up to 2*used offset can arise
             result = get_nearest_points_closer_than_thresh(
-                travel_line_reversed, child.val, threshold_hard
+                travel_line_reversed, tree.nodes[child].val, threshold_hard
             )
             assert result is not None
         proj = travel_line_reversed.project(result[0])
@@ -404,7 +408,7 @@ def create_nearest_points_list(
             weight_in_order / 2, max(0, weight_in_order - 10 * threshold)
         )
         if weight_in_order == weight_reversed_order:
-            return (1, result_list_in_order)
+            return 1, result_list_in_order
     elif preferred_direction == -1:
         # Reduce weight_reversed_order to make reversed
         # stitching more preferred
@@ -438,7 +442,8 @@ def calculate_replacing_middle_point(line_segment, abs_offset, max_stitch_distan
         return line_segment.coords[1]
 
 
-def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance, min_stitch_distance, close_point, offset_by_half):  # noqa: C901
+def connect_raster_tree_from_inner_to_outer(tree, node, used_offset, stitch_distance, min_stitch_distance, close_point,
+                                            offset_by_half):  # noqa: C901
     """
     Takes the offsetted curves organized as tree, connects and samples them.
     Strategy: A connection from parent to child is made as fast as possible to
@@ -462,20 +467,21 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
      at this position
     """
 
-    current_coords = tree.val
+    current_node = tree.nodes[node]
+    current_coords = current_node.val
     abs_offset = abs(used_offset)
     result_coords = []
     result_coords_origin = []
 
-    start_distance = tree.val.project(close_point)
+    start_distance = current_coords.project(close_point)
     # We cut the current path so that its index 0 is closest to close_point
     if start_distance > 0:
         current_coords = cut(current_coords, start_distance)
-        tree.val = current_coords
+        current_node.val = current_coords
 
-        if not tree.transferred_point_priority_deque.is_empty():
+        if not current_node.transferred_point_priority_deque.is_empty():
             new_DEPQ = DEPQ(iterable=None, maxlen=None)
-            for item, priority in tree.transferred_point_priority_deque:
+            for item, priority in current_node.transferred_point_priority_deque:
                 new_DEPQ.insert(
                     item,
                     math.fmod(
@@ -483,19 +489,20 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
                         current_coords.length,
                     ),
                 )
-            tree.transferred_point_priority_deque = new_DEPQ
+            current_node.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
     parent_stitching_direction = -1
-    if tree.parent is not None:
-        parent_stitching_direction = tree.parent.stitching_direction
+    if current_node.parent is not None:
+        parent_stitching_direction = tree.nodes[current_node.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,
+        tree,
+        tree[node],
         constants.offset_factor_for_adjacent_geometry * abs_offset,
         2.05 * abs_offset,
         parent_stitching_direction,
@@ -528,7 +535,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
             end_offset,
             stitch_distance,
             min_stitch_distance,
-            tree.transferred_point_priority_deque,
+            current_node.transferred_point_priority_deque,
             abs_offset,
             offset_by_half,
             False
@@ -545,7 +552,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
             current_coords.length - end_offset,
             stitch_distance,
             min_stitch_distance,
-            tree.transferred_point_priority_deque,
+            current_node.transferred_point_priority_deque,
             abs_offset,
             offset_by_half,
             False
@@ -554,8 +561,8 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
 
     assert len(own_coords) == len(own_coords_origin)
 
-    tree.stitching_direction = stitching_direction
-    tree.already_rastered = True
+    current_node.stitching_direction = stitching_direction
+    current_node.already_rastered = True
 
     to_transfer_point_list = []
     to_transfer_point_list_origin = []
@@ -563,7 +570,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
         # TODO: maybe do not take the first and the last
         # since they are ENTER_LEAVING_POINT points for sure
         if (
-            not offset_by_half
+                not offset_by_half
                 and own_coords_origin[k] == sample_linestring.PointSource.EDGE_NEEDED
                 or own_coords_origin[k] == sample_linestring.PointSource.FORBIDDEN_POINT):
             continue
@@ -579,6 +586,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
     # need to use "-used_offset" for stitching_direction==-1
     point_transfer.transfer_points_to_surrounding(
         tree,
+        node,
         stitching_direction * used_offset,
         offset_by_half,
         to_transfer_point_list,
@@ -595,6 +603,7 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
     if offset_by_half:
         point_transfer.transfer_points_to_surrounding(
             tree,
+            node,
             stitching_direction * used_offset,
             False,
             to_transfer_point_list,
@@ -642,10 +651,8 @@ def connect_raster_tree_from_inner_to_outer(tree, used_offset, stitch_distance,
                 # 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(
+                (child_coords, child_coords_origin) = connect_raster_tree_from_inner_to_outer(
+                    tree,
                     item.child_node,
                     used_offset,
                     stitch_distance,
@@ -820,14 +827,14 @@ def connect_raster_tree_spiral(
     """
 
     abs_offset = abs(used_offset)
-    if tree.is_leaf:
+    if not tree['root']:  # if node has no children
         return sample_linestring.raster_line_string_with_priority_points(
-            tree.val,
+            tree.nodes['root'].val,
             0,
-            tree.val.length,
+            tree.nodes['root'].val.length,
             stitch_distance,
             min_stitch_distance,
-            tree.transferred_point_priority_deque,
+            tree.nodes['root'].transferred_point_priority_deque,
             abs_offset,
             offset_by_half,
             False)
@@ -836,86 +843,92 @@ def connect_raster_tree_spiral(
     result_coords_origin = []
     starting_point = close_point.coords[0]
     # iterate to the second last level
-    for node in PreOrderIter(tree, stop=lambda n: n.is_leaf):
-        ring1 = node.val
-        ring2 = node.children[0].val
-
-        part_spiral = interpolate_linear_rings(ring1, ring2, stitch_distance, starting_point)
-        node.val = part_spiral
+    for node in nx.dfs_preorder_nodes(tree, 'root'):
+        if tree[node]:
+            ring1 = tree.nodes[node].val
+            child = list(tree.successors(node))[0]
+            ring2 = tree.nodes[child].val
+
+            part_spiral = interpolate_linear_rings(ring1, ring2, stitch_distance, starting_point)
+            tree.nodes[node].val = part_spiral
+
+    for node in nx.dfs_preorder_nodes(tree, 'root'):
+        if tree[node]:
+            current_node = tree.nodes[node]
+            (own_coords, own_coords_origin) = sample_linestring.raster_line_string_with_priority_points(
+                current_node.val,
+                0,
+                current_node.val.length,
+                stitch_distance,
+                min_stitch_distance,
+                tree.nodes[node].transferred_point_priority_deque,
+                abs_offset,
+                offset_by_half,
+                False)
 
-    for node in PreOrderIter(tree, stop=lambda n: n.is_leaf):
-        (own_coords, own_coords_origin) = sample_linestring.raster_line_string_with_priority_points(
-            node.val,
-            0,
-            node.val.length,
-            stitch_distance,
-            min_stitch_distance,
-            node.transferred_point_priority_deque,
-            abs_offset,
-            offset_by_half,
-            False)
-
-        point_transfer.transfer_points_to_surrounding(
-            node,
-            -used_offset,
-            offset_by_half,
-            own_coords,
-            own_coords_origin,
-            overnext_neighbor=False,
-            transfer_forbidden_points=False,
-            transfer_to_parent=False,
-            transfer_to_sibling=False,
-            transfer_to_child=True)
-
-        # We transfer also to the overnext child to get a more straight
-        # arrangement of points perpendicular to the stitching lines
-        if offset_by_half:
             point_transfer.transfer_points_to_surrounding(
+                tree,
                 node,
                 -used_offset,
-                False,
+                offset_by_half,
                 own_coords,
                 own_coords_origin,
-                overnext_neighbor=True,
+                overnext_neighbor=False,
                 transfer_forbidden_points=False,
                 transfer_to_parent=False,
                 transfer_to_sibling=False,
                 transfer_to_child=True)
 
-        # Check whether starting of own_coords or end of result_coords can be removed
-        if not result_coords:
-            result_coords.extend(own_coords)
-            result_coords_origin.extend(own_coords_origin)
-        elif len(own_coords) > 0:
-            if Point(result_coords[-1]).distance(Point(own_coords[0])) > constants.line_lengh_seen_as_one_point:
-                lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[0], own_coords[1]])
-            else:
-                lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[1]])
-            (temp_coords, _) = sample_linestring.raster_line_string_with_priority_points(lineseg,
-                                                                                         0,
-                                                                                         lineseg.length,
-                                                                                         stitch_distance,
-                                                                                         min_stitch_distance,
-                                                                                         DEPQ(),
-                                                                                         abs_offset,
-                                                                                         offset_by_half,
-                                                                                         False)
-            if len(temp_coords) == 2:  # only start and end point of lineseg was needed
-                result_coords.pop()
-                result_coords_origin.pop()
-                result_coords.extend(own_coords[1:])
-                result_coords_origin.extend(own_coords_origin[1:])
-            elif len(temp_coords) == 3:  # one middle point within lineseg was needed
-                result_coords.pop()
-                result_coords.append(temp_coords[1])
-                result_coords.extend(own_coords[1:])
-                result_coords_origin.extend(own_coords_origin[1:])
-            else:  # all points were needed
+            # We transfer also to the overnext child to get a more straight
+            # arrangement of points perpendicular to the stitching lines
+            if offset_by_half:
+                point_transfer.transfer_points_to_surrounding(
+                    tree,
+                    node,
+                    -used_offset,
+                    False,
+                    own_coords,
+                    own_coords_origin,
+                    overnext_neighbor=True,
+                    transfer_forbidden_points=False,
+                    transfer_to_parent=False,
+                    transfer_to_sibling=False,
+                    transfer_to_child=True)
+
+            # Check whether starting of own_coords or end of result_coords can be removed
+            if not result_coords:
                 result_coords.extend(own_coords)
                 result_coords_origin.extend(own_coords_origin)
-                # make sure the next section starts where this
-                # section of the curve ends
-        starting_point = result_coords[-1]
+            elif len(own_coords) > 0:
+                if Point(result_coords[-1]).distance(Point(own_coords[0])) > constants.line_lengh_seen_as_one_point:
+                    lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[0], own_coords[1]])
+                else:
+                    lineseg = LineString([result_coords[-2], result_coords[-1], own_coords[1]])
+                (temp_coords, _) = sample_linestring.raster_line_string_with_priority_points(lineseg,
+                                                                                             0,
+                                                                                             lineseg.length,
+                                                                                             stitch_distance,
+                                                                                             min_stitch_distance,
+                                                                                             DEPQ(),
+                                                                                             abs_offset,
+                                                                                             offset_by_half,
+                                                                                             False)
+                if len(temp_coords) == 2:  # only start and end point of lineseg was needed
+                    result_coords.pop()
+                    result_coords_origin.pop()
+                    result_coords.extend(own_coords[1:])
+                    result_coords_origin.extend(own_coords_origin[1:])
+                elif len(temp_coords) == 3:  # one middle point within lineseg was needed
+                    result_coords.pop()
+                    result_coords.append(temp_coords[1])
+                    result_coords.extend(own_coords[1:])
+                    result_coords_origin.extend(own_coords_origin[1:])
+                else:  # all points were needed
+                    result_coords.extend(own_coords)
+                    result_coords_origin.extend(own_coords_origin)
+                    # make sure the next section starts where this
+                    # section of the curve ends
+            starting_point = result_coords[-1]
 
     assert len(result_coords) == len(result_coords_origin)
     return result_coords, result_coords_origin
diff --git a/lib/utils/dotdict.py b/lib/utils/dotdict.py
index acd575b9..12cf6e79 100644
--- a/lib/utils/dotdict.py
+++ b/lib/utils/dotdict.py
@@ -15,7 +15,7 @@ class DotDict(dict):
 
     def update(self, *args, **kwargs):
         super(DotDict, self).update(*args, **kwargs)
-        self.dotdictify()
+        self._dotdictify()
 
     def _dotdictify(self):
         for k, v in self.items():