Longest-path in a graph, where the path should be 'straight'

Question

Is there any existing work done on finding paths that are geometrically straight?

---

I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of which has a defined position in euclidean space (they're taken from a picture). Specifically, I want to find all straightish paths longer than X, but finding the longest may be simpler and basically equivalent.

Essentially, this is a path-finding problem in a non-directed, non-planar graph, where the path's destination isn't known, and the path itself must be straight, for an arbitrary and somewhat loose definition of 'straight'.

While I've found path-finding algorithms that use graphs whose vertices have defined positions, they generally work by just using those positions to give each edge a weight, after which the positions are ignored. I'm not sure that couldn't be done here, but I think it'd require a complicated edge-weight function that somehow takes into account the weights of previous edges in the current path.

---

Perhaps you could consider it a directed graph, where edges go only geometrically away from the source node/existing path - edges that double-back towards the start can't be taken. Marking them as such may be linear. Finding all complete paths (that is, starting at a source and ending at a sink) in a directed acyclic graph is polynomial. So while all the implementations I've tried so far range from 'very inaccurate' to 'quite inaccurate and also slow', I wouldn't expect the problem to be harder than polynomial.

---

---

Edit:

Because the graph is derived from an image, the lines will generally never be perfectly straight, and while straightness is usually visually obvious, my current algorithms have measured straightness by minimizing the change in angle from point to point, or by minimizing the geometrical width of the convex hull of either the entire path, or of sections of the path individually in turn. Width being measured perpendicularly to the straight-line distance between the first point in a path and the last. The problem with either of those though, is that each point has to be processed many times (I think $N^3$), and it feels less than elegant, and more like brute force.

---

The source of the problem is measuring fibers in an image, where the image looks kinda like a large game of pick-up sticks - hundreds of straight fibers, of varying lengths, cris-crossing frequently. Vertices in the graph are at endpoints, intersections, and discontinuities (i.e. potential endpoints). I'd guess that machine learning techniques, or other methods of image-processing, may be better suited for the problem, as it boils down to recognition of simple objects in an image, but the purpose of my question is more to learn about graphs, rather than just solve that problem.

Answer 1

Idea 1: Short paths are straight paths

In Euclidean space, a straight path is usually a short path.

So I would compute shortest paths between every pair of points in the graph. This can be done in $O(|V|^3)$ time with the Floyd-Warshall algorithm, which is suitable for dense graphs, or $O((|E|+|V|)|V|\log|V|)$ time by running Dijkstra's algorithm starting from each vertex in turn, which is faster for sparse graphs.

You can then evaluate each vertex pair according to whatever "straightness" criteria you like -- e.g. average/maximum angle formed or maximum perpendicular distance, balancing these against the length of the path somehow -- and choose the overall maximum.

For a quick heuristic, you could randomly subsample the points and solve the smaller subproblem. Repeat this several times to build a list of candidate (source, sink) pairs, then run Dijkstra on each candidate in the full graph to pick the overall winner.

Idea 2: Partition edges by angle

The above should work well if it's OK for the line to be quite jagged at a small scale. But if smoothness at a small scale is important, another approach comes to mind: Partition the edges into angle buckets (e.g. all edges making an angle of 0-5 degrees with the horizontal, all edges making an angle of 6-10 degrees, etc., for 360/5 = 72 buckets overall). For each bucket, solve a separate subproblem that contains all vertices, but only the edges in that particular bucket. Every path in such a graph necessarily contains only edges that have very similar directions. (If you choose sufficiently fine buckets, you might find that the graph fragments into many small, line-like components, which will speed things up greatly as they can be solved independently.)

In fact it's not necessary to partition the edges; it's probably desirable to have some bucket overlap, so that an edge typically appears in more than one subproblem.