View Issue Details

IDProjectCategoryView StatusLast Update
0001691DraftBugpublic2014-09-15 21:00
Reporterpkoning2 Assigned Toyorik  
PrioritynormalSeveritymajorReproducibilityalways
Status closedResolutionfixed 
Product Version0.14 
Summary0001691: DXF export fails with recursion stack overflow
DescriptionI have a model of a staircase, which includes a railing that ends in a curve. The curve is just a quarter circle, but when the DXF export machinery projects that onto the X/Y plane it ends up as a wire with thousands of edges -- apparently there is no way to represent it as a simple ellipse.
That wire then ends up in DraftGeomUtils.sortEdges, which clearly is not designed to cope with such inputs. For one thing, it seems to be somewhere between O(n**2) and O(n**3) complexity. And since it is recursive, and the default recursion limit is 1000, it blows up if the input has more than just under 1000 edges.
I have some ideas for a more efficient version, will try those and report.
TagsNo tags attached.
FreeCAD Information

Activities

pkoning2

2014-08-15 20:55

reporter   ~0004950

The attached diff file appears to do the job. It builds dictionaries of edges keyed by their endpoints, and then just walks that from one endpoint to the other. No recursion, runs in linear time.

pkoning2

2014-08-15 20:56

reporter  

DraftGeomUtils.py.diff (7,285 bytes)   
--- DraftGeomUtils.py.old	2014-08-15 16:18:15.000000000 -0400
+++ DraftGeomUtils.py	2014-08-15 16:44:46.000000000 -0400
@@ -557,94 +557,83 @@
             return False
     return True
 
-def sortEdges(lEdges, aVertex=None):
-    "an alternative, more accurate version of Part.__sortEdges__"
-
-    #There is no reason to limit this to lines only because every non-closed edge always
-    #has exactly two vertices (wmayer)
-    #for e in lEdges:
-    #        if not isinstance(e.Curve,Part.Line):
-    #                print "Warning: sortedges cannot treat wired containing curves yet."
-    #                return lEdges
-
-    def lookfor(aVertex, inEdges):
-        ''' Look for (aVertex, inEdges) returns count, the position of the instance
-        the position in the instance and the instance of the Edge'''
-        count = 0
-        linstances = [] #lists the instances of aVertex
-        for i in range(len(inEdges)) :
-            for j in range(2) :
-                if aVertex.Point == inEdges[i].Vertexes[j-1].Point:
-                        instance = inEdges[i]
-                        count += 1
-                        linstances += [i,j-1,instance]
-        return [count]+linstances
-
-    if (len(lEdges) < 2):
-        if aVertex == None:
-            return lEdges
-        else:
-            result = lookfor(aVertex,lEdges)
-            if result[0] != 0:
-                if aVertex.Point == result[3].Vertexes[0].Point:
-                    return lEdges
-                else:
-                    if geomType(result[3]) == "Line":
-                        return [Part.Line(aVertex.Point,result[3].Vertexes[0].Point).toShape()]
-                    elif geomType(result[3]) == "Circle":
-                        mp = findMidpoint(result[3])
-                        return [Part.Arc(aVertex.Point,mp,result[3].Vertexes[0].Point).toShape()]
-                    elif geomType(result[3]) == "BSplineCurve" or\
-                        geomType(result[3]) == "BezierCurve":
-                        if isLine(result[3].Curve):
-                            return [Part.Line(aVertex.Point,result[3].Vertexes[0].Point).toShape()]
-                        else:
-                            return lEdges
-                    else:
-                        return lEdges
+def vpoint(vertex):
+    """Turn a vertex into a triple of its point coordinates.  This is
+    so we can put it into a dictionary; vertexes hash on their identity
+    and compare equal on object identity rather than coordinates.
+    And vertex.Point compares on value, but is mutable so it doesn't
+    have a hash value.
+    """
+    p = vertex.Point
+    return (p.x, p.y, p.z)
+
+def sortEdges(edges):
+    """Sort edges in path order, i.e., such that the end point of edge N
+    equals the start point of edge N+1.
+    """
+    # Build a dictionary of vertexes according to their end points.
+    # Each entry is a set of vertexes that starts, or ends, at the
+    # given vertex position.
+    sdict = dict()
+    edict = dict()
+    for e in edges:
+        v1, v2 = e.Vertexes
+        v1 = vpoint(v1)
+        v2 = vpoint(v2)
+        try:
+            sdict[v1].add(e)
+        except KeyError:
+            sdict[v1] = set()
+            sdict[v1].add(e)            
+        try:
+            edict[v2].add(e)
+        except KeyError:
+            edict[v2] = set()
+            edict[v2].add(e)            
+    # Find the start of the path.  The start is the vertex that appears
+    # in the sdict dictionary but not in the edict dictionary, and has
+    # only one edge ending there.
+    startedge = None
+    for v, se in sdict.iteritems():
+        if v not in edict and len (se) == 1:
+            startedge = se
+            break
+    # The above may not find a start vertex; if the start edge is reversed, 
+    # the start vertex will appear in edict (and not sdict).
+    if not startedge:
+        for v, se in edict.iteritems():
+            if v not in sdict and len (se) == 1:
+                startedge = se
+                break
+    # If we still have no start vertex, it was a closed path.  If so, start
+    # with the first edge in the supplied list
+    if not startedge:
+        startedge = edges[0]
+        v = vpoint (startedge.Vertexes[0])
+    # Now build the return list by walking the edges starting at the start
+    # vertex we found.  We're done when we've visited each edge, so the
+    # end check is simply the count of input elements (that works for closed
+    # as well as open paths).
+    ret = list()
+    for i in xrange(len(edges)):
+        try:
+            eset = sdict[v]
+            e = eset.pop()
+            if not eset:
+                del sdict[v]
+            v = e.Vertexes[1]
+        except KeyError:
+            eset = edict[v]
+            e = eset.pop()
+            if not eset:
+                del edict[v]
+            v = e.Vertexes[0]
+            e = e.reverse()
+        ret.append(e)
+        v = vpoint(v)
 
-    olEdges = [] # ol stands for ordered list 
-    if aVertex == None:
-        for i in range(len(lEdges)*2) :
-            if len(lEdges[i/2].Vertexes) > 1:
-                result = lookfor(lEdges[i/2].Vertexes[i%2],lEdges)
-                if result[0] == 1 :  # Have we found an end ?
-                    olEdges = sortEdges(lEdges, result[3].Vertexes[result[2]])
-                    return olEdges
-        # if the wire is closed there is no end so choose 1st Vertex
-        # print "closed wire, starting from ",lEdges[0].Vertexes[0].Point
-        return sortEdges(lEdges, lEdges[0].Vertexes[0]) 
-    else :
-        #print "looking ",aVertex.Point
-        result = lookfor(aVertex,lEdges)
-        if result[0] != 0 :
-            del lEdges[result[1]]
-            next = sortEdges(lEdges, result[3].Vertexes[-((-result[2])^1)])
-            #print "result ",result[3].Vertexes[0].Point,"    ",result[3].Vertexes[1].Point, " compared to ",aVertex.Point
-            if aVertex.Point == result[3].Vertexes[0].Point:
-                #print "keeping"
-                olEdges += [result[3]] + next
-            else:
-                #print "inverting", result[3].Curve
-                if geomType(result[3]) == "Line":
-                    newedge = Part.Line(aVertex.Point,result[3].Vertexes[0].Point).toShape()
-                    olEdges += [newedge] + next
-                elif geomType(result[3]) == "Circle":
-                    mp = findMidpoint(result[3])
-                    newedge = Part.Arc(aVertex.Point,mp,result[3].Vertexes[0].Point).toShape()
-                    olEdges += [newedge] + next
-                elif geomType(result[3]) == "BSplineCurve" or \
-                    geomType(result[3]) == "BezierCurve":
-                    if isLine(result[3].Curve):
-                        newedge = Part.Line(aVertex.Point,result[3].Vertexes[0].Point).toShape()
-                        olEdges += [newedge] + next
-                    else:
-                        olEdges += [result[3]] + next
-                else:
-                    olEdges += [result[3]] + next                                        
-            return olEdges
-        else :
-            return []
+    # All done.
+    return ret
 
 
 def flattenWire(wire):
DraftGeomUtils.py.diff (7,285 bytes)   

yorik

2014-08-16 02:07

administrator   ~0004951

Looks nice! It might also be much faster. I'll test and include if I find no problems. Thanks a lot for this!

Related Changesets

FreeCAD: master a4f208c8

2014-09-15 22:30:37

yorik

Details Diff
Draft: replaced DraftGeomUtils.sortEdges with better version from pkoning2 - fixes 0001691 Affected Issues
0001691
mod - src/Mod/Draft/DraftGeomUtils.py Diff File

Issue History

Date Modified Username Field Change
2014-08-15 19:25 pkoning2 New Issue
2014-08-15 20:55 pkoning2 Note Added: 0004950
2014-08-15 20:56 pkoning2 File Added: DraftGeomUtils.py.diff
2014-08-16 02:07 yorik Note Added: 0004951
2014-08-16 02:07 yorik Assigned To => yorik
2014-08-16 02:07 yorik Status new => assigned
2014-08-16 02:07 yorik Project FreeCAD => Draft
2014-09-15 21:00 yorik Changeset attached => FreeCAD Master master a4f208c8
2014-09-15 21:00 yorik Status assigned => closed
2014-09-15 21:00 yorik Resolution open => fixed