[ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Need help, or want to share a macro? Post here!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

I have another look at my previous test and code, apparently, I used extensively the result of isSame() to match edge before and after sorting (getSortedCluster instead of sortEdges) and identify the index.

Code: Select all

# isPartner():	Share the same TShape, but may have a different Location and may have a different Orientation
# isSame():	share the same TShape, have the same Location but may have a different Orientation
# isEqual():	share the same TShape, have the same Location and have the same Orientation
@wmayer Are the edges after Part.sortEdges() are 'copied' and not 'shared with' the original edges' TShape, so edwilliams16's code using isSame() can't match the edges 'before' and 'after'?

(I might had 'trial and error' kind of tested but not remember ...)
edwilliams16
Veteran
Posts: 3106
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by edwilliams16 »

@paullee

In my simple case I get the same edge numbering with

Code: Select all

edges = sketch.Shape.Edges
or

Code: Select all

edges = [l.toShape() for l in sketch.Geometry]
maybe because all I have is a set of edges. However, the isSame() test fails either way.
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

Thanks for testing the index order :)

Why isSame() not working probably related to how sortEdges() works.
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

Code: Select all

[1, 2, 3, 4, 5, 6] -> [[1, 2, 3, 4], [5], [6]]
[1, 4, 2, 5, 6, 3] -> [[6, 4, 1, 2, 5],  [3]]
[5, 6, 1, 2, 3, 4] -> [[3, 6,  1, 5, 2], [4]]
[5, 3, 1, 4, 6, 2] -> [[6, 1, 5, 3, 4],  [2]]

[4, 2, 6, 3, 5, 1] -> [[3, 2,  6, 4, 5],  [1]]
[3, 5, 2, 1, 6, 4] -> [[2, 1, 5, 3, 6], [4]]
[3, 5, 1, 4, 6, 2] -> [[6, 1, 5, 3, 4], [2]]
[1, 3, 6, 2, 5, 4] -> [[5, 1, 6, 3, 2], [4]]
[5, 4, 1, 2, 3, 6] -> [[3, 4, 5, 2, 1], [6]]
[3, 1, 6, 4, 2, 5] -> [[2, 3, 6, 1, 4], [5]]
Trying to make sense of the result, gone through the first 4 results, the 3rd one seems not understandable to me :roll:

Code: Select all

[5, 6, 1, 2, 3, 4] -> [[3, 6,  1, 5, 2], [4]]
  1. '5' first
  2. then '6' is not connected to '5', and should be ignored, or put to last of the same queue again?
  3. becomes [5] + [1, 2, 3, 4, 6 ] ?
  4. then '1', is 'before' '5', considering the 'orientation' of the vertex, ok --> [ 1, 5 ] + [ 2, 3, 4, 6 ]
  5. then '2' is tricky, the algorithm test '5' first in the sorted list, and it find '2' is connected, so it take precedence ?
  6. [1, 5 ... 2, 3, 4, 6 ] ? --> [ 1, 5, 2 ] + [3, 4, 6] ?
  7. now '3'.... not connected either way, so put to the end again ? [1, 5, 2 ... 3, 4, 6 ] ? --> [ 1, 5, 2 ] + [4, 6, 3] ?
  8. then '4'.... not connected either way, so put to the end again ? [1, 5, 2 ... 4, 6, 3 ] ? --> [ 1, 5, 2 ] + [ 6, 3, 4] ?
  9. then '6 '.... connected to 1, so [1, 5, 2 ... 6, 3, 4 ] --> [ 6, 1, 5, 2 ] + [ 3, 4] ?
  10. then '3 '.... why connected to '6', but not '2' --> [ 6, 1, 5, 2, 3 ] or [ 3, 6, 1, 5, 2 ]
  11. lastly, what is the algorithm end the test loop, concluding not more edges are connected ?
All kind of wild guess :lol:
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by onekk »

Part.sortEdges()

The original author was me. As input it expects an unordered list of edges that forms a single wire and sorts them so that in the output list two adjacent edges share a common vertex. This allows it to create a wire from the sorted list of edges.
Probably the point is here:

- Adjacent edges
- Share a common vertex
- Single wire

Obviously the wire showed is not following rules, so result could be weird as input data are not compatible with rules.

Try to write a sorting routine yourself to see where the problem is.

Another problem could be last and first point of a linesegment of crossing segment, that could determine what are mating segments.

Proposed solutions for a different sorting routine?

What should be the wanted order for the case shown?

I fear that changing existing code will break most of created code and files that use sortEdges as you have to break some rules.

Regards

Carlo D.
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/
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

Thanks @onekk for the comment.

It seem wmayer simplified the description :- https://github.com/FreeCAD/FreeCAD/commit/1031644fa

Code: Select all

            "__sortEdges__(list of edges) -- list of edges\n"
            "Helper method to sort an unsorted list of edges so that afterwards\n"
            "the start and end vertex of two consecutive edges are geometrically coincident.\n"
            "It returns a single list of edges and the algorithm stops after the first set of\n"
            "connected edges which means that the output list can be smaller than the input list.\n"
            "The sorted list can be used to create a Wire."

Code: Select all

            "sortEdges(list of edges) -- list of lists of edges\n"
            "It does basically the same as __sortEdges__ but sorts all input edges and thus returns\n"
            "a list of lists of edges"
So edwilliams16's script handles all edges whether there will be edges 'disconnected' or not'
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

paullee wrote: Sun Feb 05, 2023 3:46 am

Code: Select all

[1, 2, 3, 4, 5, 6] -> [[1, 2, 3, 4], [5], [6]]
[1, 4, 2, 5, 6, 3] -> [[6, 4, 1, 2, 5],  [3]]
[5, 6, 1, 2, 3, 4] -> [[3, 6,  1, 5, 2], [4]]
[5, 3, 1, 4, 6, 2] -> [[6, 1, 5, 3, 4],  [2]]

[4, 2, 6, 3, 5, 1] -> [[3, 2,  6, 4, 5],  [1]]
[3, 5, 2, 1, 6, 4] -> [[2, 1, 5, 3, 6], [4]]
[3, 5, 1, 4, 6, 2] -> [[6, 1, 5, 3, 4], [2]]
[1, 3, 6, 2, 5, 4] -> [[5, 1, 6, 3, 2], [4]]
[5, 4, 1, 2, 3, 6] -> [[3, 4, 5, 2, 1], [6]]
[3, 1, 6, 4, 2, 5] -> [[2, 3, 6, 1, 4], [5]]
In fact, seems 1st result above, which has fist list only 4 edges, is not consistent with the rest, which has 1st list contain 5 edges.

For 1st result, the algorithm seems not further search if there is still edges connected to the list [1, 2, 3, 4], as the 'wire' become 'closed?, and stop there.

But for other results, the algorithm does not stop even though in some case the wire had become 'closed' before it ends up with 5 edges.

:roll:
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by onekk »

paullee wrote: Sun Feb 05, 2023 9:38 am
In fact, seems 1st result above, which has fist list only 4 edges, is not consistent with the rest, which has 1st list contain 5 edges.

For 1st result, the algorithm seems not further search if there is still edges connected to the list [1, 2, 3, 4], as the 'wire' become 'closed?, and stop there.
I'm trying to formalize a "sort method", so make some usually create two list, one is a good list and the other is the list that are not matching, and iterate using a start element, following rules to determine what is the nest element, if it match it is placed in the "good list" and it search mating elements in the "bad list"

rougly it seems that:

https://github.com/FreeCAD/FreeCAD/blob ... t_edges.py

is doing this and even if it is deprecated could gave some hints, on writing a sort method for your case, if you find a rule that could be translated in code and produce your desired result.

Not formalized in code, but using only paper and pencil.

first result seem in line with what is expected.

other result, probably take a different path.

Code: Select all

[1, 4, 2, 5, 6, 3] -> [[6, 4, 1, 2, 5],  [3]]
it seems that 4 is breaking the rule, so it is excluding 1 from the list and search a mating line and find 6, and order the (6, 4) then use 6 and then find 1 and then it is forced to choose between 3 and 5 in this case it choose 5 and exclude 3.

This has some sense, apart from guessing why it choose 5 and not 3.

Code: Select all

[5, 6, 1, 2, 3, 4] -> [[3, 6,  1, 5, 2], [4]]
5 and 6 are crossing so it exclude 5, use 6 and then is forced to choose between 3 and 4 it choose 3 and 4 is pushed out, it order 6 and 3, (probably using a counterclockwise rule, as arcs are drawn in counterclockwise order, so it is more easy to order arc if present using counterclockwise rule), and probably when choosing from 1 and 2 it follow a counterclockwise rule again, and choose 1, then 5 that is the most near if you consider a counterclockwise angle calculated from 1, then it has no choice as 1 is already in list so it choose 2, 4 is remaining in the list and is not mating with the last element (2) so it is left out

But this is only a partial guess, to not create a "one page long" post but seems to have some sense.

But now how to put this in code and find rules that fulfill your needs integrating excluded line(s) in the produced wire.?

What is you desired result?

Regards

Carlo D.
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/
wmayer
Founder
Posts: 20243
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by wmayer »

Are the edges after Part.sortEdges() are 'copied' and not 'shared with' the original edges' TShape, so edwilliams16's code using isSame() can't match the edges 'before' and 'after'?
In case two input edges already share a common vertex then the edges of the output list will do, too. If two adjacent edges don't share a common vertex then they won't do it either in the output list.
But there is one exception: if the orientation of an edge is reversed then BRepBuilderAPI_MakeEdge is used to create an edge with consistent orientation and this presumably creates a copy.

The whole purpose of the algorithm is to sort the edges and the next step to create a wire from the sorted list will do the sharing and eventually copies the shape data.
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

Re: [ ArchWall ] - Part.getSortedCluster, Part.sortEdges(), again

Post by paullee »

wmayer wrote: Sun Feb 05, 2023 2:01 pm
Are the edges after Part.sortEdges() are 'copied' and not 'shared with' the original edges' TShape, so edwilliams16's code using isSame() can't match the edges 'before' and 'after'?
In case two input edges already share a common vertex then the edges of the output list will do, too. If two adjacent edges don't share a common vertex then they won't do it either in the output list.
But there is one exception: if the orientation of an edge is reversed then BRepBuilderAPI_MakeEdge is used to create an edge with consistent orientation and this presumably creates a copy.
Thanks for the comment :)

Edwilliam's script use isSame() trying to match the Edge in the output list against the original Edges in the input list - but it seems not working as mentioned in his remark - rather than trying to compare the Vertex of 2 edges to see if they are common.

The output list by Part.getSortedCluster seem can use outputEdge.isSame(inputEdge) to find the matching one in the input list - to the contrary, it seems Part.sortEdges seem can not.

So I guess, the output list of edges by Part.sortEdges Do Not share the common TopoShape, rather, they are copies of the original so isSame() does not work. Is it the case? Thanks againl


Code: Select all


import random
def edgeindex(edge, edges):
    for i, e in enumerate(edges):
        #if e.isSame(edge): #why not!!
        if e.CenterOfGravity.isEqual(edge.CenterOfGravity, 1e-7):
            return i

    return None


skname = 'Sketch' # or Sketch001
doc = App.ActiveDocument
sketch = doc.getObject(skname)
edges = sketch.Shape.Edges
#print(edges)
order_s = [i for i in range(len(edges))]
for j in range(10):  
    edges_s = [edges[i] for i in order_s]
    #print(edges_s)
    sorted_edges_s = Part.sortEdges(edges_s)
    sortorder =[[edgeindex(edge, edges) for edge in l] for l in sorted_edges_s]
    print(f'{[ i+1 for i in order_s]} -> {[[i+1 for i in l] for l in sortorder]}')#add 1's
    random.shuffle(order_s)
Post Reply