Description on sortEdges

Need help, or want to share a macro? Post here!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

Here's my take on a python sortEdges routine.

Code: Select all

V3 = App.Vector

def vertexSameLoc(v1, v2, tol = 1e-7):
    ''' 
    v1, v2 App.Vertex
    tol: tolerance float
    returns Boolean : same position within tol
    '''
    return abs((v1.Point - v2.Point).Length) <= tol

def matchingEdge(edgechain, edgelist, tol = 1e-7):
    '''
    Looks for an edge in edgelist with an end point co-located (within tol) 
    with an endpoint of edgechain
    edgechain: list of consecutive edges
    edgelist: list of edges
    returns: (edge, i , j) i is chain end, j is edge end
    '''
    for edget in edgelist:
        for j in [0, -1]:
            for i in [0, -1]:
                if vertexSameLoc(edgechain[i].Vertexes[i], edget.Vertexes[j], tol):
                     return (edget, i, j)
    return None

def reversedEdge(edge):
    ''' reverses the geometry of edge - swapping the vertices
    '''
    curve = edge.Curve.trim(*edge.ParameterRange)
    curve.reverse()
    revedge =  Part.Edge(curve)
    #print(f' {[v.Point for v in edge.Vertexes]} rev: {[v.Point for v in revedge.Vertexes]}')
    return revedge

def sortEdges1(edges, tol = 1e-7):
    ''' edges: list of Part.Edge
        tol: float tolerance
        returns: (closededges, edgechain, remainingedges)
    '''
    closededges = edgechain = []
    remainingedges = edges.copy()

    for i, edge in enumerate(remainingedges):
        if edge.isClosed() or vertexSameLoc(edge.Vertexes[0], edge.Vertexes[-1], tol):
            closededges.append(edge)
            del remainingedges[i]
    if len(remainingedges) == 0:
        return (closededges, [], remainingedges)
    else:
        edgechain = [remainingedges.pop(0)]

    while True:
        numremaining = len(remainingedges)
        match = matchingEdge(edgechain, remainingedges, tol)
        print(f'Match {match}')
        if match:
            edgematch, i, j = match
            if i == 0 and j == 0:
                #print('begin/begin')
                edgechain.insert(0, reversedEdge(edgematch))
            elif i == 0 and j == -1:
                #print('begin/end')
                edgechain.insert(0, edgematch)
            elif i == -1 and j == 0:
                #print('end/begin')
                edgechain.append(edgematch)
            elif i == -1 and j == -1:
                #print('end/end')
                edgechain.append(reversedEdge(edgematch))
            else:
                print("This can't happen")
            
            remainingedges.remove(edgematch)
            #print(f'Edgechain{edgechain}')
            #print(f'Remaining {remainingedges}')

        if len(remainingedges) == numremaining or len(remainingedges) == 0:
            break
    for edge in closededges:
        for v in edge.Vertexes:
            v.Tolerance = 2*tol
    for edge in edgechain:
        for v in edge.Vertexes:
            v.Tolerance = 2*tol

    for edge in remainingedges:
        for v in edge.Vertexes:
            v.Tolerance = 2*tol

    return (closededges, edgechain, remainingedges)

def sortEdges2(edges, tol = 1e-7):
    '''
    edges: List of Part.Edge
    tol: float tolerance
    returns: List of lists of serially connected edges
    '''
    a, b, c = sortEdges1(edges, tol)
    blist = [[e] for e in a]
    blist.append(b)
    for i in range(100):
        if len(c) > 0:
            aa, bb, c = sortEdges1(c, tol)
            blist.append(bb)
            if len(c) == 0:
                break
    return blist

####  a test

def makeEdgeList(eps):
    p0 = V3(-100,0,0)
    p1 = V3(0,100,0)
    p2 = V3(100,100,0)
    p3 = V3(0,100,0)
    epsv = eps * p2
    e0 = Part.makeLine(p0+epsv, p1 + epsv)
    e1 = Part.makeLine(p2-epsv, p1 - epsv) #reversed
    e2 = Part.makeLine(p2+epsv, p3 + epsv)
    #e3 = Part.makeLine(p0-epsv, p3 - epsv) #reversed
    e3 = Part.makeCircle(100, V3(0,0,0), V3(0,0,1), 180, 360)
    edges = [e0, e2, e1, e3]
    return edges

rect = makeEdgeList(1e-5)

App.newDocument()
import OpenSCADdxf
c,f=OpenSCADdxf.importEZDXFshape("/Users/ed/Downloads/SLvl-2D-BodySketch.dxf",retcompound=True,retfaces=True)
#Collect the edges from an object that is created silently by that routine:
the_edges=OpenSCADdxf.mylayerlist[0]

ll = sortEdges2(the_edges + rect, 1e-2)
for l in ll:
    try:
        w = Part.Wire(l)
        Part.show(w, 'Wire')
    except:
        print('Failed to make wire')
sortEdges1(edges, tol = 1e-7) is the worker routine. It first looks for single closed edges and puts them in closededges. It consists of edges that FreeCAD reports as closed plus any whose two distinct vertices are within tol. It then takes the first of the remaining edges and uses it to start a chain. It loops through the remainder (less the chain edge) and looks for an edge with a vertex within tol of either end of the chain. Finding one, it prepends or appends it to the chain, reversing it if necessary. This edge is then deleted from the remaining list. This continues until no more edges can be added to the chain. The constructed chain and any remaining elements are returned.

sortedges2(edges, tol = 1e-7) applies sortedges1 to the edge list, returning a list of chain lists.

Note that like the Part.sortEdge function, you don't get predictable (or useful?) results if the edges have any t-junctions. Traversal will depend on the ordering of the input edges.

This routine is not at all polished, given it will become redundant when Part.sortEdges() acquires a tolerance argument. I found writing it educational however. Try it on data and see if I missed anything important.
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

I think this routine definitely moves the ball forward a bit. It clearly works on the test case provided. And it does a better job on another problematic DXF (attached, that I got somewhere on the forum but the link to which I have lost), though in that case it results in two wires that FC/OCC says are not closed. I need to try to figure out why that's the case, as there isn't an obvious gap that I can see.

THANK YOU very much for this help!
mconsidine
Attachments
TabletStand01.dxf
(43.84 KiB) Downloaded 10 times
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

@mconsidine

It's failing to connect up where there are tiny edges of length 0.024 mm. Clearly there's a problem if we make the Vertex tolerances of an edge larger than half its edge length, particularly if there are larger gaps than that elsewhere in the chain. That may or may not be the case here... In any case, it will require fixing.

OK. I've found the problem here. The dxf file has duplicated edges.

Code: Select all

>>> [v.Point for v in the_edges[9].Vertexes]
[Vector (-2978.049554158792, 2015.5452583150707, 0.0), Vector (-2976.0151253142517, 2036.3462810092242, 0.0)]
>>> [v.Point for v in the_edges[10].Vertexes]
[Vector (-2978.049554158792, 2015.5452583150707, 0.0), Vector (-2976.0151253142517, 2036.3462810092242, 0.0)]
EDIT Delete the duplicates and the code works as is.
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

Ok, thanks for that. That suggests I might need to add a step that looks for duplicate edges and drop them before more processing.

I think your code is working better than the default, based on the limited testing so far. What I'll do is add it into my workflow and rerun the tests I had been doing on a pile of DXFs from the forum.

Much obliged!

mconsidine
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

Yes. Since you are basically fixing broken DXFs, it comes down to seeing how broken they are. Picking tol in some automated way is one task.
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

@edwilliams16 Thanks again for all this work. Building on what you did...

I took your code posted above, ultimately finding that I needed to omit the "for" block in sortEdges1 here :

Code: Select all

    #for i, edge in enumerate(remainingedges):
    #    if edge.isClosed() or vertexSameLoc(edge.Vertexes[0], edge.Vertexes[-1], tol):
    #        print("Same vertex : ",vertexSameLoc(edge.Vertexes[0], edge.Vertexes[-1], tol))
    #        closededges.append(edge)
    #        del remainingedges[i]
(I found I was losing an edge in a couple of cases.)

What works for me now is, a shown above :

Code: Select all

import OpenSCADdxf
c,f=OpenSCADdxf.importEZDXFshape("/home/matt/Downloads/DXFtests/forum/SLvl-2D-BodySketch.dxf",retcompound=True,retfaces=True)
#c,f=OpenSCADdxf.importEZDXFshape("/home/matt/Downloads/DXFtests/forum/TabletStand01.dxf",retcompound=True,retfaces=True)
#c,f=OpenSCADdxf.importEZDXFshape("/home/matt/Downloads/DXFtests/forum/czolg.dxf",retcompound=True,retfaces=True)

#show that face doesn't get formed with this
Part.show(c)

#collect edges
the_edges=OpenSCADdxf.mylayerlist[0] 
Now, delete any duplicate edges. This puzzled me for a bit as the standard tests of isSame or isEqual gave incorrect results, for reasons I don't understand. And I think I need to test for the circumstance when there's a point and a segment (which is found in one of the above DXFs).

Code: Select all

#delete any duplicate edges; looks like there are two though regular tests don't work???
for i, m in enumerate(the_edges):
  for n in range(i):
    if n < i :
      e1 = [v1.Point for v1 in m.Vertexes]
      e2 = [v2.Point for v2 in the_edges[n].Vertexes]    
      #if i==10 and n==9:
      #if m.Length == the_edges[n].Length not a good enough test; isEqual/isSame=False
      if (len(e1) == 1) and (len(e2) == 1) : #should duplicate points be trapped?
        if e1==e2:
          print("duplicate point deleted")
          del the_edges[n]
      elif (len(e1) == 2) and (len(e2) == 2) :
        if (e1[0] == e2[0] and e1[1] == e2[1]) or (e1[0] == e2[1] and e1[1] == e2[0]): #orientation matters?? 
          print(i, m.Length)
          print(n, the_edges[n].Length)   
          print(m.isEqual(the_edges[n]))
          print(m.isSame(the_edges[n]))
          print(m.isPartner(the_edges[n]))
          #Vertexes are the same though ...
          print(e1)
          print(e2)
          #So ... tests based on length can give a false result; ie cant use Length to winnow pairs to test
          #Ideally, anything using Length to compare in a test should use a tolerance. isSame/isEqual??
          print("now we know is same")
          del the_edges[n]  #does this get us into trouble during loop??  should be past this
      elif (len(e1) == 1 and len(e2) == 2) or (len(e2) == 1 and len(e1) == 2): #trap??
        if len(e1) == 1:
          if (e1[0] == e2[0]) or (e1[0] == e2[1]):
            print("dupe point")
            del the_edges[n-1]
        else:
           if (e2[0] == e1[0]) or (e2[0] == e1[1]):
            print("dupe point 2")
            del the_edges[n]       
      else:
        print("unexpected result")

With that done:

Code: Select all

#iterate to find smallest tol that yields len(ll)==1 or expected number of faces and no Matches=None? 
#I think this could be automated to run in a narrow range, e.g. 1e-1 to 1e-7?? 
ll = sortEdges2(the_edges , 1e-2) 
print(len(ll))

for l in ll:
    try:
        w = Part.Wire(l)
        Part.show(w, 'Wire')
    except:
        print('Failed to make wire')

In each of the above three DXFs I was able to take the final result and use Part to take the shapes into an error-free face.

Thoughts? I would be interested in knowing the reason for including the block that I commented out in sortEdges1. But as this stands I think I can now import DXFs that were giving me a problem. I do need to rerun all my tests at this point though.

Unless I can understand otherwise, I think your version of sortEdges is the way to go for me.

Thanks again (and apologies as well for the hijacking of the thread :) )
mconsidine
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

The for block is to handle closed edges like circles

Code: Select all

p =Part.makeCircle(10)
len(p.Vertexes)#  -> 1 
which only have one vertex and can make faces in of themselves. All other edges have two vertices at different locations, which I deal with in the remaining code. But perhaps my trying to deal with almost-closed as well as actually closed edges causes more problems than it solves.

What you need to deal with/delete is edges that share the same pair of vertices. If they are duplicates in error, presumably delete. I don't know how to deal with a dxf which has two wires which each have an edge, not identical, but sharing the same vertices. How does one guess which edge belongs to which wire? Or a dxf where two wires have a common edge - can that happen? It sure complicates things.

isSame, isEqual are topological methods. You can use them to find edges shared between two faces, for instance. They do not compare geometry. If you make copies of edges, they don't test equal to the original.
If you test whether two edges share the same vertex locations and have the same length, they are likely geometrical duplicates, but you'd have to dig deeper to be certain. (could be opposite arcs, for instance?)

Is 1e-1 for tolerance plausible for a DXF? I'm guessing errors are of numerical origin , and shouldn't be much more than 1e-7 in the first place- though in principle it depends on the scale of the objects. If your dxf is 10 km in size, relative errors of 1e-7 are 1 mm. You are screwed if you have a range of edges sizes in the dxf that exceeds its precision.
Post Reply