Algorithm to remove Loops from a Line-String

Question

I am using a third-party API to acquire a linestring representing a route. Occasionally, this API (which I will not name, here) returns a linestring that contains loops. Logically, this makes no sense. The shortest path on a plane would never include a loop.

By definition, the presence of a loop in a planar linestring must imply that the linestring intersects itself at some point. Without loss of generality, there must be a segment of the path from the origin of the path to that point of intersection, a segment along the loop that returns to the point of intersection and a segment from that point to the end-point of the path; the way to remove the loop would simply be to remove the segment starting and ending at the point of intersection. I could write an algorithm to do this, it might go something like this...

for each step, U = (a, b), along the line-string
    if the step intersects a previous step, V = (p, q) at z
        insert a step (p, z)
        remove all steps between V and U, inclusive of both
        insert a step (z, b)

My question is simple, are there any published algorithms to remove loops from a line-string (assumed to be planar)?

I don't like to implement my own scribblings without learning, first, what is out there. It's easy to invent an algorithm. It is difficult to invent a perfect one.

Answer 1

I have done a fair amount of research into this problem, now, and I believe that the best way to do this is to create a weighted graph with vertices for every point in the line-string and every intersection between steps along the line-string and apply Dijkstra's Algorithm to find the shortest path from the starting vertex to the end-point.

Why my Pseudo-Code Does Not Work

Consider the path, below, which starts at A, proceeds to B, C, D, E, F. At F, the path returns to E, D and C. It then proceeds to G and ends at H.

P, Q, R, V, W are intersections that do not exist in the original line-string but are relevant to the discussion.

As the algorithm adds steps, this is what will happen:

1. while adding the step CD, the algorithm will discover intersection P and create the path A, P, D.
2. Next, while adding EF, it will discover Q and create A, Q, F.
3. On the return leg, while adding FE, the meaningful intersection will again be Q and the result will be A, Q, E.
4. While adding DC, R will be discovered and the result will be A, Q, R, C. This will be the last intersection that governs the algorithm's behaviour
5. and the final output will be A, Q, R, C, G, H.

Human intuition suggests that paths like A, V, W, G, H or even A, B, G, H will be shorter. They would never be discovered by my pseudo-code algorithm.

This is at least one case where the algorithm results in a sub-optimal path, hence my conclusion that the best solution is to find all intersections and run Dijkstra's Algorithm.

---

The input points for the path above:

(-56.8217793676305, -8.88299365847671), (-113.643558735261, -17.7659873169534)
(-56.6527353669234, -25.4905092205507), (-109.059870307362, -1.80265591606324)
(-65.6069009172882, -39.4783992800045), (-96.4819575546674,  9.04327695318884)
(-65.6069009172882, -39.4783992800045), (-109.059870307362, -1.80265591606324)
(-56.6527353669234, -25.4905092205507), (-94.6466176124818, -20.3408279514859)
(-151.468396980112, -29.2238216099626)