Add clean-up that removes singular edges without any twinCURA-7948_remove_singular_edges

Only twins are allowed in the graph. Any others must be removed.

Contributes to issue CURA-7948.

3 files changed, 80 insertions, 1 deletions

diff --git a/src/SkeletalTrapezoidation.cpp b/src/SkeletalTrapezoidation.cpp
index 4a65fc5a3..fe283c2a1 100644
--- a/src/SkeletalTrapezoidation.cpp
+++ b/src/SkeletalTrapezoidation.cpp
@@ -435,7 +435,8 @@ void SkeletalTrapezoidation::constructFromPolygons(const Polygons& polys)
     separatePointyQuadEndNodes();
 
     graph.fixNodeDuplication();
-    
+
+    graph.fixSingularEdges();
     graph.collapseSmallEdges();
 
     // Set [incident_edge] the the first possible edge that way we can iterate over all reachable edges from node.incident_edge,
diff --git a/src/SkeletalTrapezoidationGraph.cpp b/src/SkeletalTrapezoidationGraph.cpp
index 2b029c0a0..1f77c2f6d 100644
--- a/src/SkeletalTrapezoidationGraph.cpp
+++ b/src/SkeletalTrapezoidationGraph.cpp
@@ -204,6 +204,79 @@ void SkeletalTrapezoidationGraph::fixNodeDuplication()
         }
     }
 }
+
+void SkeletalTrapezoidationGraph::fixSingularEdges()
+{
+    unsigned int iterations = 0; //Track the number of iterations to make sure it's not getting out of hand.
+    bool more_to_remove = true;
+    while(more_to_remove) //Repeat until we've converged.
+    {
+        more_to_remove = false;
+
+        //Find any edges that don't have twins and remove those.
+        for(std::list<edge_t>::iterator edge_it = edges.begin(); edge_it != edges.end();)
+        {
+            edge_t* edge = &*edge_it;
+            if(edge->twin)
+            {
+                edge_it++;
+                continue; //This edge is all fine.
+            }
+
+            //Remove the broken edge from the linked list.
+            if(edge->prev)
+            {
+                edge->prev->next = edge->next;
+            }
+            if(edge->next)
+            {
+                edge->next->prev = edge->prev;
+            }
+
+            //If it was a middle edge, close the gap that the broken edge was spanning.
+            if(edge->prev && edge->next)
+            {
+                //Move the start point of the next edge to the start point of the broken edge.
+                edge->next->from = edge->from;
+                if(edge->next->twin && edge->prev->twin)
+                {
+                    edge->next->twin->to = edge->prev->twin->from; //Also move the point on the opposite side, if the opposite side is well-formed.
+                }
+            }
+            //If it was a start or end edge, check if the quad is now too small, having just 1 edge. Remove the entire quad then.
+            else
+            {
+                if(edge->prev && !edge->prev->prev) //This is a solo edge. Remove it.
+                {
+                    if(edge->prev->twin) //The solo edge has a twin though. Unlink them and remove them in the next iteration.
+                    {
+                        edge->prev->twin->twin = nullptr;
+                    }
+                    edge->prev->twin = nullptr;
+                    more_to_remove = true;
+                }
+                if(edge->next && !edge->next->next) //This is a solo edge. Remove it.
+                {
+                    if(edge->next->twin)
+                    {
+                        edge->next->twin->twin = nullptr;
+                    }
+                    edge->next->twin = nullptr;
+                    more_to_remove = true;
+                }
+            }
+
+            //Remove the actual edge.
+            edges.erase(edge_it++);
+        }
+
+        iterations++;
+        if(iterations > 50)
+        {
+            logWarning("Removing a lot of singular edges in a cascade!");
+        }
+    }
+}
     
 void SkeletalTrapezoidationGraph::collapseSmallEdges(coord_t snap_dist)
 {
diff --git a/src/SkeletalTrapezoidationGraph.h b/src/SkeletalTrapezoidationGraph.h
index ff5effc57..13a224176 100644
--- a/src/SkeletalTrapezoidationGraph.h
+++ b/src/SkeletalTrapezoidationGraph.h
@@ -72,6 +72,11 @@ public:
     void fixNodeDuplication();
 
     /*!
+     * Remove edges which have no twins.
+     */
+    void fixSingularEdges();
+
+    /*!
      * If an edge is too small, collapse it and its twin and fix the surrounding edges to ensure a consistent graph.
      * 
      * Don't collapse support edges, unless we can collapse the whole quad.