4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
3
$\begingroup$

Your paths are varieties of what are often called angle-restricted paths in the literature, and exploring the literature may help with your particular situation:

The general angle-restricted TSP (Traveling Salesman Path) problem is NP-hard, as established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.