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.
أكثر...
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.
أكثر...