Your def is using lot’s of add-ons (I don’t work with any other than K2). One of them is called Euler Cycle (so it should - in theory - provide a solution).
Anyway … Euler/Hamiltonial paths in graphs are one of the most challenging tasks known to man (if we want a solution in less than a week). If the EulerCycle thingy doesn’t work AND you can’t code (level required : expert) I would suggest to go after some other task. See Ham cycles using Meshes as Graphs.
thank you very much for your answer,
it indeed provides an Euler path for a given mesh (after making sure that all the mesh nod degrees are even, and if not pairing based on distance, find the shortest way between the 2 vertices for each pair and double the edges, according to the chinese postman problem - Chinese postman problem - Wikipedia)
In this sense, it works perfectly.
however, I do look for a specific one: an Euler path that doesn’t cross itself.
I am willing to put my time on because it is important to me, but I am looking for a clue on how to start
thanks again!
Well … thst’s kinda saying that a Harley Davidson is a motorcycle. I mean a Ham path/cycle algo should work (if there’s a solution anyway) on ANY valid Graph. So your thing is … er … hmm … some other thing.
That said your C# for the prox pairs … well … that’s another quite hard task: imagine trying to find the “best” prox pairs. In order to get the gist of what the issue is do a graph that displays the distances … and attempt to make it “as even as possible”.
Anyway … you don’t need “best” prox pairs for a Ham cycle so don’t bother with that one.
How to start? Get a Graph, do the VV Connectivity, find possible islands (general case) using SOLELY the VV (and some Recursion) and “reorder” the VV using obviously 2 dim paths. Any “isolated” VV means a classic Adjacency Matrix: the only thing that a Ham cycle solution needs (assuming that the cost is not an issue for you).
How to end? In order to be pragmatic you should avoid any N factorial algo: this means advanced heuristics, so to speak.
Tip: what about a TSP thing? Or a PMST? (both are far easier to deal with).
well, I am actually interested in a path that travels through all the edges once - the Euler path (and not through all the nods- Hamiltonian path), and specifically a path that doesn’t cross itself.
unfortunately, the Hamiltonian cycle/path are not relevant to my problem at the moment.
your definitions look fantastic though! maybe for a next project
Indeed (most notably when an E path can visit Vertices more than once). It could be a good thing if we had some insight: what is the goal? Some AEC thing? (a freaky truss “spine” for instance). Some routing optimization? Some Academic thing?
This is rather a very simple paper to follow. Also is very easy to write a Method that tells if an Edge is a Bridge (*). So given a Mesh, the Mesh TopoV, TopoE connectivity Methods available in R SDK (thus the related VV, VE, EV Trees AND the Bridges) … blah ,blah. Plus during the search a “cross” check Method based on neighbor indices intersections maybe could cut the mustard.
If you have a graph that is self intersecting, you can use it in order to suppress self intersection.
The idea is quite simple at each self intersection flip the direction of the curve . I have done this tool for curve in my Nautilus Plugin (not online at the moment, but could be send).
If you have that