2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What kind of graphs do you consider? Can you say the nodes of the graph are points in an Euclidean space and the length of an edge is the Euclidean distance of its endpoints? You are expected to provide at least clear definition of "straightness" in one case. $\endgroup$ – Apass.Jack Jan 24 at 21:27
  • $\begingroup$ By "straightness" do you mean the path is one of the shortest paths between the source and destination? If yes, the longest path (and its length) are then called the diameter of the graph. $\endgroup$ – Apass.Jack Jan 24 at 21:34
  • $\begingroup$ @Apass.Jack Yes, the points are in euclidean space, and the distance between them is the euclidean distance. Part of the problem is the definition of 'straightness' - a straight path would be one of the shortest paths between one endpoint and the other endpoint of the same line, but while that'd be visually obvious if you were looking at a plot/image of the data, algorithmically I won't know which endpoints are on the same line. I'll add more detail. $\endgroup$ – HammerN'Songs Jan 25 at 15:33
  • $\begingroup$ Vague idea: sort the edges by angle. Cover the circle with overlapping arcs. For each arc, take all the edges in that arc and direct them in the same way, giving a DAG. Find the maximum length path for all edges in that arc. Then branch and bound until you're within tolerances you consider "straight." $\endgroup$ – Daniel McLaury Jan 25 at 23:09
  • 1
    $\begingroup$ "Finding all complete paths (that is, starting at a source and ending at a sink) in a directed acyclic graph is polynomial" -- not true. There can be an exponential number of such paths: Consider a DAG in which there are 2 columns containing $n$ vertices each, each with two outgoing edges, one to the next-higher vertex on the same side, and one to the next-higher vertex on the other side. There are $2^n$ source-to-sink (bottom-to-top) paths in this graph. $\endgroup$ – j_random_hacker Jan 27 at 17:41
2
$\begingroup$

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.

$\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.