I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.
The precondition is very simple: For each point there's always a set of nearby points within a narrow arc, and another (possibly empty) set of nearby points within a narrow arc at a nearly opposite direction. There are no other nearby points.
For each set of three contiguous points within the path, namely A, B and C, the angle ∠ABC always has a measure between 90° and 270° (most of the time it's close to 180°, though there are a couple cases of points forming a nearly right angle), and the angles ∠BAC and ∠BCA have a measure of less than 90° (or possibly a smaller threshold).
My naïve idea is: for each point, evaluate the vectors toward the nearest n points to find whether there are two nearest opposite pairs and make the path piecewise (if all the other points are at nearly the same direction, then we're at the beginning or end of the path).
However, I want to know about a better way to trace the shortest path between the set of points, given the constraints above.
Edit: I forgot to say. No, I don't want a cycle. Though minimum Hamiltonian paths are still NP-hard, I...
You know what? I'll build a sparse graph that only contains the set of edges whose weight (Euclidean distance) is less than a threshold, then run Dijkstra's algorithm through the resulting adjacency list. This will work well with my data.