Help with recursive algorithm

Need help, or want to share a macro? Post here!
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
JMG
Posts: 287
Joined: Wed Dec 25, 2013 9:32 am
Location: Spain
Contact:

Help with recursive algorithm

Post by JMG »

Hello.

As I said here, I'm asking for help with some parts of the unfolding algorithm.
What I'm going to ask is not exactly related to FreeCAD, is more a python programming question.
Suppose I have a list containing 17 face objects (listA), and then I have another list like this one (listB):

Code: Select all

[[4, 2], [5, 3], [0, 6], [1, 7], [0, 8], [1, 9], [10, 2], [11, 3], [4], [5], [6, 12], [7, 13], [14, 10], [15, 11], [12, 16], [13, 17], [14], [15]]
What listB means is, for example, that face with index 0 from listA is in contact with faces with index 4 and 2 in listA. If the content related to an index in listB has only one element, means the face with the same index from listA is an end of branch.

My question is how can I obtain a new list containing something like (if it start to unfold from face 4):
[ 4, A, B, C, D ], which is the route from the selected face up to a face without new branches.

Some combination of faces will never link with face 4 (this algorithm has also filtering purposes), this faces should be discarded.

I think it involves recursive programming and my brain just shuts itself down before getting damaged. :oops:
Solving this could be a major step forward, because once the route is created, it could be interpreted like: unfold D over C, all over B, all over A, all over 4. Clean and extrude solution.

I've tried to explain it as simple as possible, if it is not clear enough I will try to draw something, give another example or whatever is needed. :roll:


Javier
FreeCAD scripts, animations, experiments and more: http://linuxforanengineer.blogspot.com.es/
Open source CNC hot wire cutter project (NiCr): https://github.com/JMG1/NiCr
Exploded Assembly Workbench: https://github.com/JMG1/ExplodedAssembly
User avatar
saso
Veteran
Posts: 1920
Joined: Fri May 16, 2014 1:14 pm
Contact:

Re: Help with recursive algorithm

Post by saso »

Did you see this, it has quite some details and includes references to methods behind it and code... But I am not sure if it is what you are looking for :roll:

http://dynamobim.com/dynamounfold/
User avatar
microelly2
Veteran
Posts: 4688
Joined: Tue Nov 12, 2013 4:06 pm
Contact:

Re: Help with recursive algorithm

Post by microelly2 »

saso wrote:Did you see this, it has quite some details and includes references to methods behind it and code... But I am not sure if it is what you are looking for :roll:

http://dynamobim.com/dynamounfold/
@saso: Very nice link,

@javier: in sql this is a classical problem to transform the question "who are my childrens" to a child-father relational table.
I think/hope there exists already a python modul - give me the weekend.

I agree with you: finding the unfolding tree is one major step

but the next more difficult one is how to unfold without collisions
this will the challenging task :roll:
JMG
Posts: 287
Joined: Wed Dec 25, 2013 9:32 am
Location: Spain
Contact:

Re: Help with recursive algorithm

Post by JMG »

Hi saso. Yes, I saw your link ;) , but I think is easier to create an algorithm to order a list than learning a completely new library ( that also appears to be windows only) :? Seems that it can unfold sets of faces by triangulating them, so the "true" CAD feature would be lost there? :?

Microelly - I'm sure that there is a library to do it, but I think too that, splitting one list into several others containing a chain of faces, shouldn't be longer than 15-20 lines of code. Anyway, a solution that works is a good solution.
About how to detect impossible unfolds... In my opinion, the tree is, by far, more challenging:
At unfolding, a sketch containing faces geometries is extruded. If it can't extrude because some lines self-intersect it will raise an error. So maybe it could be as simple as a try & except statement.
FreeCAD scripts, animations, experiments and more: http://linuxforanengineer.blogspot.com.es/
Open source CNC hot wire cutter project (NiCr): https://github.com/JMG1/NiCr
Exploded Assembly Workbench: https://github.com/JMG1/ExplodedAssembly
User avatar
saso
Veteran
Posts: 1920
Joined: Fri May 16, 2014 1:14 pm
Contact:

Re: Help with recursive algorithm

Post by saso »

I know the text at that link is a bit long, but I would recommend to take the time and read it and further also check all the links in it. I am not suggesting to use that library but it talks in details what were the problems when developing it and how the problems were solved, it also has references to academic papers and theories on the topic...

And when you will read all of it and review all the links then you will probably go and google https://www.google.com/search?q=python+spanning+tree ;)

Triangulation is used for curved surfaces and for a reason, when you have to build it from parts or material that cannot be bent... Another interesting topic :)
https://www.google.com/search?q=translational+surfaces
https://www.google.com/search?q=quadril ... anar+faces
wmayer
Founder
Posts: 20241
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Help with recursive algorithm

Post by wmayer »

Your problem can be described as a graph (here it's two trees, i.e. a so called forest) (see graph theory). listB describes the adjacencies between the faces and you can e.g. build a so called adjacency matrix out of it. This should be a symmetric matrix because it's an undirected graph. Upon this matrix you will find a sub-graph which contains your start element.
User avatar
looo
Veteran
Posts: 3941
Joined: Mon Nov 11, 2013 5:29 pm

Re: Help with recursive algorithm

Post by looo »

[[0, [4, [8]], [2, [6, [10, [12, [14, [16]]]]]]], [1, [5, [9]], [3, [7, [11, [13, [15, [17]]]]]]]]
is this the expected output beginning with 0?
JMG
Posts: 287
Joined: Wed Dec 25, 2013 9:32 am
Location: Spain
Contact:

Re: Help with recursive algorithm

Post by JMG »

Saso, I possibly overlooked it. I'll do a careful read when I have some more time :) Now I'm a bit overloaded with all this data structures, trees and bucles, this field is completely new for me ;)

wmayer, thanks for the info, I'll look for more documentation about it.

looo: That is one solution of the problem, but having every line from root to leave (single) separated, would be directly usable.

I have posted more code in my blog. There I describe how to do a first face filtering and how to know which face links with which. I uploaded an example shape for testing the algorithm too.

Thanks!
FreeCAD scripts, animations, experiments and more: http://linuxforanengineer.blogspot.com.es/
Open source CNC hot wire cutter project (NiCr): https://github.com/JMG1/NiCr
Exploded Assembly Workbench: https://github.com/JMG1/ExplodedAssembly
User avatar
looo
Veteran
Posts: 3941
Joined: Mon Nov 11, 2013 5:29 pm

Re: Help with recursive algorithm

Post by looo »

not sure if I have understood correctly.

Code: Select all

lst = [
    [4, 2], [5, 3], [0, 6], [1, 7],
    [0, 8], [1, 9], [10, 2], [11, 3],
    [4], [5], [6, 12], [7, 13],
    [14, 10], [15, 11], [12, 16], [13, 17],
    [14], [15]]

lst1 = [[3, 2], [4, 5], [0, 3, 6], [0, 7],
        [1, 8], [1, 4, 9], [2], [3, 10, 11],
        [4], [5, 12, 13], [7, 14], [7, 10, 15],
        [9, 13, 16], [9, 17], [10], [11], [12], [13]]


def tree(parts, start):
    temp = []
    linear_path = []

    def branch(pos):
        if pos in temp:                     # avoiding endless loops
            return
        else:
            temp.append(pos)
            parent = [pos]                  # first value of list is parent
            for child in parts[pos]:
                tr = branch(child)          # does child have children?
                if tr:
                    parent.append(tr)       # append child and its children
            return parent

    def step_in(tree, lst=[]):
        newlist = lst + [tree[0]]           # append the parent
        if len(tree) > 1:                   # if we have children
            for i in tree[1:]:
                step_in(i, newlist)         # step in
        else:
            linear_path.append(newlist)     # end of path

    step_in(branch(start))
    for i in linear_path:
        i.reverse()
    return linear_path


tr = tree(lst, 0)
print(tr)

JMG
Posts: 287
Joined: Wed Dec 25, 2013 9:32 am
Location: Spain
Contact:

Re: Help with recursive algorithm

Post by JMG »

Looo, you did it!, your code performs flawlessly!! :shock: :D
I tested the whole script with 3 different shapes, the output is perfect with all of them :D

Thank you very much!
FreeCAD scripts, animations, experiments and more: http://linuxforanengineer.blogspot.com.es/
Open source CNC hot wire cutter project (NiCr): https://github.com/JMG1/NiCr
Exploded Assembly Workbench: https://github.com/JMG1/ExplodedAssembly
Post Reply