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!
User avatar
onekk
Veteran
Posts: 6145
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: Description on sortEdges

Post by onekk »

a distance of 0.0 usually means that they intersect.

A guess is that they are crossing lines at the extrema. But you have in the returned infos intersection points and intersecting edges, so you could retune start and ending points to avoid the crossing.

Regards

Carlo D.
Last edited by onekk on Sun May 28, 2023 6:19 pm, edited 1 time in total.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.

Blog: https://okkmkblog.wordpress.com/
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

I think what I need is something like "mindistToShapeEndpoints(edge1,edge2,told), which round return None of no pair of endpoints were within a given tolerance. That is, all were greater than tol. Otherwise it returns a set of indices (?) Identifying candidates for rounding.
mconsidine
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: Description on sortEdges

Post by paullee »

Not sure it helps, some more discussion :-

[ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again
edwilliams16
Veteran
Posts: 3107
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

@mconsidine

I can glue the edges together by setting the vertex tolerance to a larger number (about 1e-3 for the sample file). However, the Part.sortEdges() method does not use the vertex tolerance, but appears to be hard wired to 1e-7. If I sort the edges into head-to-tail order by hand, I can make a full length wire.

Here's a test script that illustrates this.

Code: Select all

V3 = App.Vector

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

#make square with zero eps, sort, make wire
edges = makeEdgeList(0.0)
[Part.show(Part.Wire(es), 'eps0') for es in Part.sortEdges(edges)] #makes single closed wire

make square with 1e-5 eps, sort fails
edges = makeEdgeList(1e-5)
[Part.show(Part.Wire(es), 'eps5_') for es in Part.sortEdges(edges)] # four wires...
#sort by hand, still can't make wire because eps > 1e-7
try:
    edgessort = [edges[0], edges[2], edges[1], edges[3]]
    wire = Part.Wire(edgessort)
except:
    print("Can't make wire")

#set tolerance to 1e -4
for e in edges:
    for v in e.Vertexes:
        v.Tolerance = 1e-4

print(f'Failed to make single wire. Number of wires: {len(Part.sortEdges(edges))}') #four wires ...

#but can sort by hand
edgessort = [edges[0], edges[2], edges[1], edges[3]]
wire = Part.Wire(edgessort) #single wire
Part.show(wire, 'Wire')

So we can get the edges to glue head to tail by increasing the vertex tolerance - but we have to sort the edges by hand, or wait for a tolerance argument for Part.sortEdges()
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

@edwilliams16
Thanks for that, I'll need to study it. At a glance, your approach seems more elegant/robust...

In the meantime, I hacked a solution to the problem I was having with the above-named DXF. It now imports and converts to a Face, albeit it requires the idea of patches. Which I don't think it should if I could figure out how to round vertex values (different thread)

Noting that the distToShape function appears to report back the minimum distance of a perpendicular line, it's not returning the vertex info I wanted.

This does:

Code: Select all

def distBetweenVertexPoints(a,b):
  d1 = np.sqrt( (a.Vertexes[0].X-b.Vertexes[0].X)**2+(a.Vertexes[0].Y-b.Vertexes[0].Y)**2++(a.Vertexes[0].Z-b.Vertexes[0].Z)**2 )
  d1pair = [0,0]
  d2 = np.sqrt( (a.Vertexes[0].X-b.Vertexes[1].X)**2+(a.Vertexes[0].Y-b.Vertexes[1].Y)**2++(a.Vertexes[0].Z-b.Vertexes[1].Z)**2 )
  d2pair = [0,1]
  d3 = np.sqrt( (a.Vertexes[1].X-b.Vertexes[0].X)**2+(a.Vertexes[1].Y-b.Vertexes[0].Y)**2++(a.Vertexes[1].Z-b.Vertexes[0].Z)**2 )
  d3pair = [1,0]
  d4 = np.sqrt( (a.Vertexes[1].X-b.Vertexes[1].X)**2+(a.Vertexes[1].Y-b.Vertexes[1].Y)**2++(a.Vertexes[1].Z-b.Vertexes[1].Z)**2 )
  d4pair = [1,1]
  mindist = min(d1,d2,d3,d4)
  mindistindex = [d1,d2,d3,d4].index(mindist)
  minpair = [d1pair,d2pair,d3pair,d4pair][mindistindex]
  return [mindist, minpair]
  
Basically: calculate the distances between the endpoints of two different edges, figure out the smallest, figure out which vertex pair that corresponds to and return same.

Now calculate patching line segments:

Code: Select all

patches=[]
for i, a_fail in enumerate(the_edges):
  for j,a_success in enumerate(the_edges):
    if j < i: #go through all the edges, ignoring compares to self and redundant compares
      gap = distBetweenVertexPoints(a_fail, a_success)
      if (gap[0] > 1e-7) and (gap[0] < 0.01): # is a gap above the default tolerance and a user defined one, e.g. 0.01?
        a_start = a_fail.Vertexes[gap[1][0]]  # get the starting point of the gap ...
        a_end = a_success.Vertexes[gap[1][1]] # and the ending point
        a_line = Part.Edge( Part.Vertex(a_start), Part.Vertex(a_end)) # make an Edge
        patches += [a_line]  # add it to a list
Collect the original edges and patches together and form Faces, Wires ...

Code: Select all

f = Part.sortEdges(the_edges+patches4)[0] #bc sortEdges returns a list
Part.show(Part.Face(Part.Wire(f)))
Pretty sure that doesn't get awards for gracefulness or robustness. And it's only been tested on this one DXF coming in via EZDXF.

mconsidine
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

@edwilliams16
Your approach makes much more sense and is a lot cleaner. I think I'll ditch what I described above.

I note that the sortEdges routine is written in C++? It looks like there is an old version in python available via

Code: Select all

  from draftgeoutils.sort_edges import (sortEdges,sortEdgesOld)
I don't know the history - did it not work well or was it just replaced with something better and/or faster?

Would it make sense to hack that code to deal with vertex tolerance?
mconsidine
edwilliams16
Veteran
Posts: 3107
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

@mconsidine

I also thought of that solution - i.e. connecting up the vertices that were out of tolerance with tiny edges. It seemed inelegant, and would lead to self-intersection failures when the edges crossed.

If you try to modify the vertex locations of the edges, by rounding say, you have to recreate the underlying Curves with the modified endpoints, which you would need to do case by case - lines, arcs, BSplines etc. The difficulty of this is determined by the number of curve types you support.

The underlying C++ sortEdges appears to have a tolerance argument, it just isn't exposed to python. https://github.com/FreeCAD/FreeCAD/blob ... y.cpp#L156

Writing one's own sort_edges function with a tolerance argument doesn't look too difficult. A starting point might be:
https://github.com/FreeCAD/FreeCAD/blob ... #L124-L228
replacing equality tests of Vertex.Point with tests within tolerance. But I haven't tried it.

EDIT: Looks like you were thinking on the same lines while I was composing my reply...
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

All else being equal, as they say, it looks to me like line 145 of the python version just needs to be converted to a test of distance vs tolerance, rather than an equality test.

I'll try that tomorrow.
mconsidine
edwilliams16
Veteran
Posts: 3107
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: Description on sortEdges

Post by edwilliams16 »

Just reading the code, it looks to me that sortEdgesOld() can only work for lines, circular arcs and lines masquerading as BSplines/Beziers - no conics or curved BSplines.

I'm not sure why it reconstructs reversed edges case by case.

Code: Select all

def reversedEdge(edge):
    ''' reverses the geometry of edge - swapping the vertices by parameterizing in the reverse direction
    '''
    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
    
seems to work for all the cases above.

I am still mystified though, why flipping edge.Orientation doesn't satisfy Part.Wire(edges) when an edge vertex order is backwards. It insists on an having an edge with the Vertices actually reversed. (Part.sortEdges actually reverses geometry, not just Orientation also). I thought the point of the Orientation flag was to accommodate edges shared by adjacent faces which necessarily require the opposite orientation of the corresponding outerwires. (So the orientation of the two faces are both consistently outward.) Obviously I still haven't fully grokked Open Cascade.
mconsidine
Posts: 125
Joined: Wed Jan 18, 2023 10:41 pm
Location: Randolph, VT USA

Re: Description on sortEdges

Post by mconsidine »

I was able to hack the C++ code to get sortEdges to pass through a tolerance value. That still left a set of edges being passed to Part.Wire, which couldn't do anything because of the gaps. So it would appear there needs to be some step between the two that adjusts the endpoints. But I couldn't figure out how any of the "fix" routines worked so I may be back to square one.
mconsidine
Post Reply