[ 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!
Post Reply
User avatar
Roy_043
Veteran
Posts: 8450
Joined: Thu Dec 27, 2018 12:28 pm

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

Post by Roy_043 »

A self-intersecting wire can be closed. It would not be a good loop for a face, but the 8-like shape can be offset.

So we need:
  1. A good wire_from_edges function (optimized for Arch_Wall).
  2. An improved wire_is_closed function (with a self_intersect_is_allowed argument, or a separate function to check that).
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 »

Maybe you have researched this already, but I'm unclear on what is the exact specification for Part.sortEdges(edgelist)
It seems it returns a list of lists of connected edges - but the result can't be unique.

Take a crossed rectangle - each vertex has degree 3 (three lines connecting to it.) Euler's theorem says that there is a closed circuit visiting each edge once if and only if the degree of every vertex is even. (only if is obvious, if harder.

If we remove any single edge from our crossed rectangle, we have two vertices of even degree and two with odd. We can then start and end our Eulerian path at the odd vertices and visit the remainder by Euler's theorem, making an open connected Eulerian path with the remaining five edges.

What's the result: there are six different decompositions of the crossed rectangle, depending on which edge we chose to hypothetically delete.

https://en.wikipedia.org/wiki/Eulerian_path

You may remember the famous Bridges of Konigsberg problem. https://en.wikipedia.org/wiki/Seven_Bri ... B6nigsberg My grandfather posed this to me when I was about ten years old. I wasted many, many hours in a futile attempt to solve it. Of course, I wasn't capable of proving that it couldn't be solved.
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Thanks @edwilliams16 !

seems nobody can tell the mechanism of the sorting methods :)
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
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Thanks @edwilliams16 :)

Maybe someone can identify are getSortedCluster / sortEdges() using similar algorithm ?
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Roy_043 wrote: Sat Jan 07, 2023 4:29 pm So we need:
  1. A good wire_from_edges function (optimized for Arch_Wall).
  2. An improved wire_is_closed function (with a self_intersect_is_allowed argument, or a separate function to check that).
Thanks again. The 2nd one seems more urgent as it current provide 'false positive' and create weird shape.

For 1st one, as edwilliams16 points out the sorting result won't be unique, as it involve human perception of the preferred sorting.
User avatar
Roy_043
Veteran
Posts: 8450
Joined: Thu Dec 27, 2018 12:28 pm

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

Post by Roy_043 »

paullee wrote: Sun Jan 08, 2023 1:39 am The 2nd one seems more urgent as it current provide 'false positive' and create weird shape.
It is not that simple.

Let's look at the file attached to the first post in this topic:
We have a rectangle with 2 diagonals. The Shape only has a single Wire with 6 edges. This is already a problem of course: this wire should not be possible IMO. But isReallyClosed returns False for this Shape. So whatever problems Arch_Wall has, are not caused by a false positive. It is the offset algo that is the primary cause. And the offset algo fails because the generated wires are less than ideal.

So the primary focus should be the wire_from_edges function:
  1. Merge collinear edges.
  2. Wires probably should not pass the same point twice.
  3. First pre-sort edges based on length? Assuming that the longest edges are the perimeter of a building?
  4. Join edges with some notion of orthogonality: prefer a 90 degree connection over a 30 degree connection?
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Ok, maybe below is a brief summary of available findings of what current ArchWall.py and offsets.py behaves:-

  1. L1273-1298 of ArchWall : getSortedCluster() sorted some edges in a Sketch
    ( This sorting is necessary for some other features, could explain separately )
    { The 6-edges Wire returned by Sketch.Shape is not used in original ArchWall.py }

    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)
    
  2. The 1st sorted cluster includes the Rectangle with 1 Diagonal edge as reported above; the 2nd cluster has the opposite Diagonal edge
  3. The sorted lists of cluster of edges are passed to offsetwires() for processing
  4. L222 of offsets.py : Part.__sortEdges__(edges) is 'redundant' (creating other error as reported above) and should be remarked out

    Code: Select all

                #wire = Part.Wire(Part.__sortEdges__(edges))
                wire = Part.Wire(edges)
    
  5. L241 of offsets.py : isReallyClosed return false positive for 1st cluster (See screencapture); can try wire.isClosed() to show the effect

    Code: Select all

        #closed = isReallyClosed(wire)
        closed = wire.isClosed()
    
  6. Revised offsets.py attached - isClosed return False in this case and ArchWall return more sensible result (needs other improvement) (see 2nd screencapture)
  7. Not sure if wire.isClosed() is good enough, or to use improved isReallyClosed() :?:

offsets.py
(21.5 KiB) Downloaded 18 times
Test_ ArchWall_ 01_ r5.FCStd
(11.74 KiB) Downloaded 21 times
Screenshot from 2023-01-09 00-27-32.png
Screenshot from 2023-01-09 00-27-32.png (150.86 KiB) Viewed 919 times
Screenshot from 2023-01-09 00-57-58.png
Screenshot from 2023-01-09 00-57-58.png (148.82 KiB) Viewed 919 times
User avatar
Roy_043
Veteran
Posts: 8450
Joined: Thu Dec 27, 2018 12:28 pm

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

Post by Roy_043 »

Thanks for the clear description, it is very helpful. I have to admit that I sort of liked the idea of getting rid of getSortedCluster(). But if it is necessary for ArchSketch (I assume) then we need to keep it. The fact that the results of Arch_Wall are different for a sketch and a Shape with (visually) the exact same edges (f.e. a PartDesign_SubShapeBinder) is reason for concern though. It is also strange that sketches are checked for valid curves and other shapes and single edges are not.

Regarding offsets.py:
Removing the redundant sorting (#4) should not be a problem. Calling functions can pre-sort the list.
Switching to isClosed (#5) is possible but the wire argument can also be a Face. So we need to handle that case. See attached file.

The isReallyClosed function is used in several files, but we probably can remove it over time. But to avoid the false positives we can change it to:

Code: Select all

def isReallyClosed(wire):
    if isinstance(wire, (Part.Wire, Part.Edge)):
        return wire.isClosed()
    return isinstance(wire, Part.Face)
I must say that I have learned a lot from this topic. Some of my assumption regarding wires were wrong. The first surprise is that edges need not be in sequence. But what is really strange is that the edges need not result in a single polyline. A wire can be 3 straight edged that share a single point for example.
Attachments
offsets.py
(21.34 KiB) Downloaded 24 times
paullee
Veteran
Posts: 5098
Joined: Wed May 04, 2016 3:58 pm

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

Post by paullee »

Ah yes, ellipse should be included, just noted it work in offset :)

Then, there is something like Shape.OrderedVertexes / Shape.OrderedEdges that may help.


(The Sorting mechanism help so it resolve 'topo-naming' problem, user can select the exact edges for some feature, and it can be traced; also even when an edge is deleted and the Index of edges shifted, it can somehow be traced)
Post Reply