Find shortest path around a cylinder represented by 3d triangular mesh
An answer to this question on the Scientific Computing Stack Exchange.
Question
Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh.
How can I find the shortest path from $C$ to itself that goes around the cylinder? By shortest, I mean the sum of Euclidean distances between consecutive vertices on the path. By "around the cylinder" I mean that such a path would essentially divide the cylinder into two new cylinders.
I have also asked this question on Mathematics SE.
Answer
Find a longitudinal axis of the cylinder (a least-squares linear fit to all your points will yield this).
Construct a plane passing through this axis. Any orientation should be fine, but let's say it is perpendicular to a normal passing from the axis to $C$.
Reorientate so the axis is vertical and the plane is divided into "left" and "right" halves by the axis. (This step is more conceptual than mathematical.)
Begin a Dijkstra shortest paths traversal from $C$.
When an edge passes through the plane, color it "left" or color it "right" depending on which side it passed through.
Dijkstra inspects the neighbours of each node and a choice is made.
If a neighbour is unvisited, it is added to the frontier and given its parents colour, if any.
If a neighbour is already visited, another check is performed.
If the neighbour is uncoloured, it is rejected.
If the neighbour's colour matches the colour of the node under consideration, it is rejected.
If the neighbour's colour differs from the node under consideration, then the edge between the node under consideration and this neighbour completes the shortest circumferential path.
Use parent pointers to backtrace the path.
The left-right plane intersections should be simple geometric checks and you shouldn't need to worry about floating-point issues since it doesn't matter if the checks are perfect or not: there's a quarter-cylinder worth of wiggle room.