--- 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):