# Algorithm: move a source polyline to a reference polyline (completely or maybe partially)

In our system, there're the requirements that we want to move some source lines (with low precision) to reference lines (with high precision). Following pictures gives the normal use cases. The red one is a source line and the blue one is a reference line.

For this case, the source line would be moved partially, and the result would be as the green line shows:

There're situations that the source line need to be moved completely.

Result:

Currently our solution is to project head/end point of the source line to the reference line and vice versa, then find projected points on the source and reference line. With these projected points, we can extract the needed part of the source and reference line and then combine them into a new one.

This works for most cases, but there are cases that this method does not work. Specifically, when either of the line has "C" like shape or the head point is very close to the end point. The next two pictures gives the scenario.

Applying my algorithm, we get the result:

In a way it's understandable because the current algorithm just finds projected points and extracts lines.

What we expected is something like this:

So what I need more robust algorithm to do this so that it can also handle special cases like the preceding one. I have tried to project every points from a line to another and to find the two projected points that closest to the head/end point of the projected line, but there was no luck. Still I can find cases that give unexpected results.

Has anyone come across similar problems before? It would be also great if there is a software or library can do similar job. Any answer will be appreciated.

-
Maybe it will help you when you look how the Topology in ArcGIS checks whether objects are coincident: help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//… paragraph "Cluster processing". – Jens Mar 7 '13 at 8:26
Thank you for your answer, @Jens. But I'm afraid that's not what I want. – mfdev Mar 7 '13 at 10:36
Do these line represent a network? Are there topological relations between them? – julien Mar 13 '13 at 8:50
It doesn't have to be a network and possibly no topological relations. – mfdev Mar 14 '13 at 6:49

My estimation is that end cases will often be exceptions that are not machine programmable. I worked with similar problems and they always required a certain amount of manual editing. What you need to tune for are exceptions that are being produced by the case and serve them up in a work management system to an end user.

-
A somewhat similar example of this can be seen here: vividsolutions.com/jcs JCS goes a long way to automate geometry conflation, but also includes manual QA for geometries that it can't merge completely. vividsolutions.com/… Is built from it and allows for QA and adds issue tracking for difficult geometries. – DPierce Mar 14 '13 at 19:46
All topological solutions can't be automated by programming and and in large enterprises such solutions are developed similar to the example as the conflation fall out can be large and cyclical in nature with complex transportation geometries with a high change rate. – lewis Mar 15 '13 at 14:42

You will need a snap tolerance and a turn tolerance for this algorithm (I assume you already have a snap tolerance).

Project the head point from the source line to the reference line. Break the reference line at this projected point.

Traverse the source line from the head point to the first vertex to get direction of travel along the source line. Traverse each of your two reference lines from the projected source point to the next vertex. If the direction of travel is within the turn tolerance of the direction of travel from the head point on your source line, then apply your algorithm normally, but only using that section of the reference line. If the algorithm reaches the end of the source line, you are done. If not, break the source line between the transformed piece and the untransformed piece (which will include the end point).

Now take the untransformed piece and project the end point onto the original reference line. Do the same procedure as before... traverse the source from the end point to the first vertex to find direction of travel. Break the reference line at the project end point and traverse each one to find if the direction of travel from the projected end point is within the turn tolerance. If so, use that piece of the reference line to apply the algorithm normally.

Remember, at this point you are only using the untransformed piece, so you will not overlap with the head point transformation.

Finally, merge the two resulting line pieces if necessary: the head point transformed piece from the projected head point to the untransformed break point and then on the end point transformed piece from the untransformed break point to the projected end point.

-