[ 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!
eigenwertnotfound
Posts: 14
Joined: Fri Dec 30, 2022 6:11 pm

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

Post by eigenwertnotfound »

couldn't get @Roy_043 offsets.py to work with his archwall.py, but his offsets.py with the original archwall script produce more complete shapes, albeit with more artifacts (see attached image)
Attachments
Screenshot 2023-01-11 at 17.55.39.png
Screenshot 2023-01-11 at 17.55.39.png (95.52 KiB) Viewed 973 times
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

FC needs to be of a recent git in the first place for Roy_043 earlier fix to be included.

What is your version ?
eigenwertnotfound
Posts: 14
Joined: Fri Dec 30, 2022 6:11 pm

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

Post by eigenwertnotfound »

latest release of the realthunder link branch (2022.11.28, https://github.com/realthunder/FreeCAD/releases). But considering it's 5000 commits behind the master branch that might explain the problem, I'll try the most recent "original" version
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Thanks Roy_043 for the PRs.


Any one has idea who is/are the original authors of Part.getSortedCluster, and Part.sortEdges(), and could elaborate the detailed mechanism more the that summary found below ? Thanks :D

https://github.com/FreeCAD/FreeCAD/commit/1031644fa
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

paullee wrote: Sat Jan 14, 2023 10:15 am Any one has idea who is/are the original authors of Part.getSortedCluster, and Part.sortEdges(), and could elaborate the detailed mechanism more the that summary found below ? Thanks :D

https://github.com/FreeCAD/FreeCAD/commit/1031644fa
@wmayer Could you enlighten who was the original author and able to tell the algorithm ?

Many thanks ! :)
wmayer
Founder
Posts: 20242
Joined: Thu Feb 19, 2009 10:32 am
Contact:

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

Post by wmayer »

Part.getSortedCluster
The original author of it was Joachim Zettler (aka dvdjimmy at SVN times). See https://github.com/FreeCAD/FreeCAD/blob ... luster.cpp
I think it was part of the original CAM workbench that has been removed some years ago but I don't know what exactly the algorithm is supposed to do.
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.
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 »

Image

It has become clear to me that Part.sortEdges() is only intended for FreeCAD's restricted view of a wire as a linear list of edges which may or may not close.

I don't know much about C++, but I believe I can follow the implementation in https://github.com/FreeCAD/FreeCAD/blob ... y.cpp#L156
which I can confirm with the following test code

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)
which takes the edges of the above sketch, randomizes the order, and feeds them to Part.sortEdges The result entirely depends on the ordering. The resulting wires can be open, closed and different sizes.
On the other hand, using Sketch001, the result is independent of order and correctly consists of one open wire and one closed one.

The algorithm builds a wire by taking the first edge, looking through the rest of list until it finds one that will connect at either end and appends it to the wire. Then it continues along the list looking for an edge that will connect at either end of our multi-segment wire. It continues looping through the remaining edges until either there are no more edges that will connect at either end, or the first and last vertices are the same and the wire is closed.

This works fine for its intended purpose, but is pretty much useless for OCC's generalized wire, which is any cluster of connected edges.

EDIT: minor clarification
Attachments
PartsortEdgesTest.FCStd
(5.78 KiB) Downloaded 16 times
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Thanks @wmayer and @edwilliams16 !

Hope more people can 'decipher' how Part.getSortedCluster() works also :)


Whilst trying to understand from the result of the code how the wire are constructed from the input edges, would like to mention that the Sketch.Shape.Edges seems somehow constructed by OCC (kind of another 'randomness'), and does not always follow the geometry edge order 'within' the Sketch. In other words, the input index order may or may not correspond exactly as shown in the diagram - in this case exactly the same ?

That's one reason in ArchWall why the geometries in Sketch are used directly and used Geometry.toShape to ensure consistency in order, so the exact index of Geometry 'within' the Sketch can be traced then.

https://github.com/FreeCAD/FreeCAD/blob ... 1273-L1290

Code: Select all

                    elif obj.Base.isDerivedFrom("Sketcher::SketchObject"):
                        self.basewires = []
                        skGeom = obj.Base.GeometryFacadeList
                        skGeomEdges = []
                        skPlacement = obj.Base.Placement  # Get Sketch's placement to restore later
                        for i in skGeom:
                            if not i.Construction:
                                # support Line, Arc, Circle for Sketch as Base at the moment
                                if isinstance(i.Geometry, (Part.LineSegment, Part.Circle, Part.ArcOfCircle)):
                                    skGeomEdgesI = i.Geometry.toShape()
                                    skGeomEdges.append(skGeomEdgesI)
                        for cluster in Part.getSortedClusters(skGeomEdges):
                            clusterTransformed = []
                            for edge in cluster:
                                edge.Placement = edge.Placement.multiply(skPlacement)  ## TODO add attribute to skip Transform...
                                clusterTransformed.append(edge)
                            # Only use cluster of edges rather than turning into wire
                            self.basewires.append(clusterTransformed)
Screenshot from 2023-02-05 09-25-30.png
Screenshot from 2023-02-05 09-25-30.png (41.98 KiB) Viewed 511 times
paullee
Veteran
Posts: 5097
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

paullee wrote: Sun Feb 05, 2023 1:38 am That's one reason in ArchWall why the geometries in Sketch are used directly and used Geometry.toShape to ensure consistency in order, so the exact index of Geometry 'within' the Sketch can be traced then.

Code: Select all

        #if e.isSame(edge): #why not!!
I am also wondering why e.isSame(edge) not works in your code; I kind of trial and test tens of times year ago to see how these works but I forget - I just avoid directly use Sketch.Shape.Edges showhow, but below code, which I use to 'trace' the Sketch Geometry Index order works. I remember most of the time, the index return by isSame() (and/or isPartner ?) works.


https://github.com/paullee0/FreeCAD_Ske ... 1821-L1889

Code: Select all

def getSortedClEdgesOrder(skGeomEdgesSet, skGeomEdgesFullSet=None):		
										
      ''' 0) To support getSketchSortedClEdgesOrder() on a Sketch object	
      	     which pass a) edges not construction (skGeomEdgesSet),		
                    and b) all edges (skGeomEdgesFullSet);			
          1) Or, similar usecases with 2 different edges lists :		
      	     - Do Part.getSortedClusters() on the provided skGeomEdgesSet,	
               and check the order of edges to return lists of indexes		
               against skGeomEdgesFullSet in the order of sorted edges	 	
										
      	  2) Or if skGeomEdgesFullSet is not provided;				
      	     - simply Part.getSortedClusters() provided edges,			
             check the order of edges to return lists of indexes		
             against original in the order of sorted edges	 	 	
										
          return:								
          - clEdgePartnerIndex, clEdgeSameIndex, clEdgeEqualIndex, and		
          - clEdgePartnerIndexFlat, clEdgeSameIndexFlat, clEdgeEqualIndexFlat	
      '''									
										
      skGeomEdgesSorted = Part.getSortedClusters(skGeomEdgesSet)		
      if skGeomEdgesFullSet is None:						
          skGeomEdgesFullSet = skGeomEdgesSet #  .copy()			
      ## a list of lists (not exactly array / matrix) to contain index of found matching geometry			
      clEdgePartnerIndex = []							
      clEdgeSameIndex = []							
      clEdgeEqualIndex = []							
										
      ## a flat list containing above information - but just flat, not a list of lists ..				
      clEdgePartnerIndexFlat = []						
      clEdgeSameIndexFlat = []							
      clEdgeEqualIndexFlat = []							
										
      for h, c in enumerate(skGeomEdgesSorted):					
          clEdgePartnerIndex.append([])						
          clEdgeSameIndex.append([])						
          clEdgeEqualIndex.append([])						
										
          ''' Build the full sub-list '''					
          for a in c:								
              clEdgePartnerIndex[h].append(None)				
              clEdgeSameIndex[h].append(None)					
              clEdgeEqualIndex[h].append(None)					
										
          for i, skGeomEdgesSortedI in enumerate(c):				
              for j, skGeomEdgesI in enumerate(skGeomEdgesFullSet):		
                  if skGeomEdgesI: # is not None / i.e. Construction Geometry	
                      if j not in clEdgePartnerIndexFlat:			
                        if skGeomEdgesSortedI.isPartner(skGeomEdgesI):		
                          clEdgePartnerIndex[h][i] = j				
                          clEdgePartnerIndexFlat.append(j)			
										
                      if j not in clEdgeSameIndexFlat:				
                        if skGeomEdgesSortedI.isSame(skGeomEdgesI):		
                          clEdgeSameIndex[h][i] = j				
                          clEdgeSameIndexFlat.append(j)				
										
                      if j not in clEdgeEqualIndexFlat:				
                        if skGeomEdgesSortedI.isEqual(skGeomEdgesI):		
                          clEdgeEqualIndex[h][i] = j				
                          clEdgeEqualIndexFlat.append(j)			
										
              if clEdgePartnerIndex[h][i] == None:				
                  clEdgePartnerIndexFlat.append(None)				
              if clEdgeSameIndex[h][i] == None:					
                  clEdgeSameIndexFlat.append(None)				
              if clEdgeEqualIndex[h][i] == None:				
                  clEdgeEqualIndexFlat.append(None)				
      return clEdgePartnerIndex, clEdgeSameIndex, clEdgeEqualIndex, clEdgePartnerIndexFlat, clEdgeSameIndexFlat, clEdgeEqualIndexFlat	
Post Reply