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

[paullee]

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?

Thanks for the study

This post start with a view to understand the detailed algorithm of Part.getSortedCluser() and Part.sortEdges() in the first place.

[edwilliams16]

@paullee
It was hard to understand without accounting for edge orientation.

crossedrect.png (25.08 KiB) Viewed 621 times

I believe the algorithm works this way.

[561234] a=> [61234] b=> [6234] c=> [234] d => [34] e=> [4] f => [] remaining edges
[[]] a => [[5]] b =>[[15]] c=>[[615]] d=> [[6152]] e =>[[36152]] f => [[36152][4]] segments in orientation order

a) start with 5 delete from list
b) 6 not connected. Reverse 1 and attach to left of list
c) attach 6 to left of list
d) reverse 2 and add to right of list
e) attach 3 to left of list
f) no remaining edges to attach. Start a new segment.
g) 4 in new segment

The first element determines the segment orientation.
At each step we go through the remaining edges left to right to find one that will connect to an end of the segment chain.
If there are none, or the current segment forms a closed loop, start a new segment.
If there is one, reverse if necessary and attach to the correct end of the segment.
Delete the edge from the remaining list.

@wmayer explained why isSame is no good. The C++ routine creates a new edge when it is required to reverse one. This edge has the same underlying geometry, but has no topological association with our object.

[edwilliams16]

I tried to write Part.__sortEdges__ in python, but got stuck on reversing an edge. It turns out

Code: Select all

edge.reverse()

just changes the Orientation flag. It doesn't create a new edge with the vertices swapped, which the C++ does. I couldn't find a method to do that. (Of course, there might be some hack like creating a BSpline and reversing the parametrization, or case by case with lines, arcs etc.)

viewtopic.php?t=31850&start=10 If that was resolved here, I didn't understand it.

[paullee]

Thanks for the detailed analysis / reverse-enginerring studies

Would have a closer look; just noted at the moment
- some wire seems is closed but further edges added
(1st case is not )
- Part.getSortedCluster() enable user to compare the input edge vs output edge, so guess they ;share same TopoShape, maybe reversed, or placement changed - so isEqual, isSame, and isPartner works in my code

[paullee]

I still have difficult to understand why the 1st result has 4 edges and considered as 'closed' so no more edge added; whilst all other has 5 edges at the output...

I tried to write Part.__sortEdges__ in python, but got stuck on reversing an edge. It turns out

Code: Select all

edge.reverse()

just changes the Orientation flag. It doesn't create a new edge with the vertices swapped, which the C++ does. I couldn't find a method to do that. (Of course, there might be some hack like creating a BSpline and reversing the parametrization, or case by case with lines, arcs etc.)

viewtopic.php?t=31850&start=10 If that was resolved here, I didn't understand it.

Anyway, what are you expecting with the edge.reverse() ? That thread in fact contained study and experiment of the effect of that method.

[onekk]

it is clear, you have edge 1, 2, 3, 4 that form a closed wire, so start point of line1, is end point of line4.

5 and 6 are keep out, and probably 6 is not considered as 4 is probably tried before 6. five is not considered as 4 is connected to 1.

For others, I don't know, but probably "original list order" has a precedence when sorting and if a "good candidate is found" others are simply excluded.

But you have no answered of the main question, maybe useful to develop a possible alternative algorithm, what is desired order?

I could think in the first case of ignoring the coincidence between line4 and line 1 and try if there is a line that starting from line4 endpoint go somewhere (in this case 5), but how to insert 6 in a "reasonable and computable" scheme, and for computable I intend translatable in conditions and choices.

Hoping to have been clear.

Regards

Carlo D.

[edwilliams16]

I still have difficult to understand why the 1st result has 4 edges and considered as 'closed' so no more edge added; whilst all other has 5 edges at the output...

If you mean [1, 2, 3, 4, 5, 6] -> [[1, 2, 3, 4], [5], [6]], it stops adding edges to the segment after [1] -> [1,2] -> [1, 2, 3] ->[1, 2, 3, 4] because it tests for closure after each edge is added.

I tried to write Part.__sortEdges__ in python, but got stuck on reversing an edge. It turns out

Code: Select all

edge.reverse()

just changes the Orientation flag. It doesn't create a new edge with the vertices swapped, which the C++ does. I couldn't find a method to do that. (Of course, there might be some hack like creating a BSpline and reversing the parametrization, or case by case with lines, arcs etc.)

viewtopic.php?t=31850&start=10 If that was resolved here, I didn't understand it.

Anyway, what are you expecting with the edge.reverse() ? That thread in fact contained study and experiment of the effect of that method.

To write Part.__sortEdges__ one needs a function that actually creates an edge with the vertices exchanged. edge.reverse() doesn't do that. It creates a pointer to the same TShape with the Orientation flag reversed. Part.__sortEdges__ creates new edges with the vertices swapped when required.

I think it is now clear what Part.sortEdges does. It was designed to link up linear chains of edges. It was not designed to do anything useful when there are vertices shared by more than two edges. It does something that is now predictable, but it doesn't appear to be anything of practical use.

If you want a new function that will operate on an arbitrary directed graph of edges - what is it supposed to do?

EDIT Re-reading your post. A segment (a chain of edges) is closed if and only if the tail and head vertices are the same.

[onekk]

This code could be a

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

Code: Select all

import FreeCAD
import Part

V3d = FreeCAD.Vector

pt1 = V3d(0,0,0)
pt2 = V3d(20,0,0)
pt3 = V3d(20,10,0)
pt4 = V3d(0,10,0)

ln1 = Part.LineSegment(pt1, pt2).toShape()
ln2 = Part.LineSegment(pt2, pt3).toShape()
ln3 = Part.LineSegment(pt3, pt4).toShape()
ln4 = Part.LineSegment(pt4, pt1).toShape()

ln5 = Part.LineSegment(pt1, pt3).toShape()
ln6 = Part.LineSegment(pt4, pt2).toShape()

edges = [ln1, ln2, ln3, ln4, ln5, ln6]


def sortEdges(edges):
    """Sort edges. Deprecated. Use Part.__sortEdges__ instead."""
    if len(edges) < 2:
        return edges

    # Build a dictionary of edges according to their end points.
    # Each entry is a set of edges that starts, or ends, at the
    # given vertex hash.
    sdict = dict()
    edict = dict()
    nedges = []
    for e in edges:
        if hasattr(e, "Length"):
            if e.Length != 0:
                sdict.setdefault(e.Vertexes[0].hashCode(), []).append(e)
                edict.setdefault(e.Vertexes[-1].hashCode(), []).append(e)
                nedges.append(e)

    if not nedges:
        print("DraftGeomUtils.sortEdges: zero-length edges")
        return edges

    # Find the start of the path.  The start is the vertex that appears
    # in the sdict dictionary but not in the edict dictionary, and has
    # only one edge ending there.
    startedge = None
    for v, se in sdict.items():
        if v not in edict and len(se) == 1:
            startedge = se
            break

    # The above may not find a start vertex; if the start edge is reversed,
    # the start vertex will appear in edict (and not sdict).
    if not startedge:
        for v, se in edict.items():
            if v not in sdict and len(se) == 1:
                startedge = se
                break

    # If we still have no start vertex, it was a closed path.  If so, start
    # with the first edge in the supplied list
    if not startedge:
        startedge = nedges[0]
        v = startedge.Vertexes[0].hashCode()

    # Now build the return list by walking the edges starting at the start
    # vertex we found.  We're done when we've visited each edge, so the
    # end check is simply the count of input elements (that works for closed
    # as well as open paths).
    ret = list()
    # store the hash code of the last edge, to avoid picking the same edge back
    eh = None
    for _ in range(len(nedges)):
        try:
            eset = sdict[v]
            e = eset.pop()
            if not eset:
                del sdict[v]
            if e.hashCode() == eh:
                raise KeyError
            v = e.Vertexes[-1].hashCode()
            eh = e.hashCode()
        except KeyError:
            try:
                eset = edict[v]
                e = eset.pop()
                if not eset:
                    del edict[v]
                if e.hashCode() == eh:
                    raise KeyError
                v = e.Vertexes[0].hashCode()
                eh = e.hashCode()
                e = invert(e)
            except KeyError:
                print("DraftGeomUtils.sortEdges failed - running old version")
                # return sortEdgesOld(edges)
        ret.append(e)

    return ret


sort_edges = sortEdges(edges)

print(sort_edges)

This fails and signal the failing, but maybe it could be a starting point


Regards

Carlo D.

[edwilliams16]

This code could be a

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


Maybe trying to reuse some of this code even deprecated, could be a strating point, that eventually could be made in C++ by someone.

Regards

Carlo D.

The key point in this code is invert(edge), which points to

https://github.com/FreeCAD/FreeCAD/blob ... es.py#L137

where one finds it goes case-by-case of edge Curves, but can't handle either Beziers or BSplines. I imagine that is why it was deprecated in favor of Part.__sortEdges__ which does.

[onekk]

The key point in this code is invert(edge), which points to
...
where one finds it goes case-by-case of edge Curves, but can't handle either Beziers or BSplines. I imagine that is why it was deprecated in favor of Part.__sortEdges__ which does.

Yes I know but if the goal is to formalize a new sorting algorithm, and working with C++ is not very handy, probably trying to write a Python method, could help to develop something that could be made then in a C++ method.

Even limiting to lines, will be "better than nothing", if @paullee could clarify what is "his expected result"
If not probably using the actual sortEdges and then make some method that will process excluded edges to put in the right place could be a "sub optimal" solution, but a solution.

Regards

Carlo D.