View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0001691 | Draft | Bug | public | 2014-08-15 19:25 | 2014-09-15 21:00 |
Reporter | pkoning2 | Assigned To | yorik | ||
Priority | normal | Severity | major | Reproducibility | always |
Status | closed | Resolution | fixed | ||
Product Version | 0.14 | ||||
Summary | 0001691: DXF export fails with recursion stack overflow | ||||
Description | I 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. | ||||
Tags | No tags attached. | ||||
FreeCAD Information | |||||
|
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. |
|
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): |
|
Looks nice! It might also be much faster. I'll test and include if I find no problems. Thanks a lot for this! |
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 |