Hey,
I am new to gh, and I am looking for an Euler path on a mesh that doesn’t cross itself as in this example:
so far I have managed to find an eulerian path on mesh, but I am not sure how to define that it will not cross itself.
Thank you very much, I appreciate your help!
test surface.gh (56.1 KB)
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.
And one in a rnd prox Graph:
That said 99% of the Internet solutions posted are out of question (N factorial : why bother talking?)
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!
FWIW, the source code for the networkx method I implemented is open source. Might help if you intend on writing your own implementation:
https://networkx.org/documentation/stable/_modules/networkx/algorithms/euler.html#eulerian_circuit
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).
PS: 1 to 10 what is your C# Level?
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 
Get any Graph > do the VV/AdjMatrix thing > then do that:
PS: Replace Dictionary (very slow) with … anything else in fact.
There doesn’t appear to be much precedent, but this paper might be relevant assuming planar graphs:
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?
Plan Z:
EH_Graphs_chapter5-part2.pdf (315.4 KB)
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.
(*) Like:
And in case that you think that the right most result is wrong:
Hello
I don’t follow where you are now, but for
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
Thank you all very much for the time and help!
