# Algorithm for lines comparison

I'm working on the import of land-use data into Openstreetmap. Unfortunately I've encountered a problem that has delayed my time table.

Take a look at the picture below: the red line is the main road (it is correctly mapped using GPS devices). The white area is the region that indicated the presence of the road: it should be placed exactly above the red line. Unfortunately, this region wasn't aquired with GPS data, but it was constructed mainly with aerial imaginery (so there are projection errors and also problems with the contrast and definition of the images): this explain the matching problem with the red line.

Since I possess a limited knowledge in this particular geometric problem, I was looking for any algorithms that could help me solve this. My thought was to handle the borders of the white region as two different lines and to apply some sort of matching algorithm. Ideally, the algorithm I'm looking for should be able to compare the features of two lines, and adjust one of them accordingly to the other.

Is there something similar that could help me? Or do you have any other possible solutions?

Thank you for your help and time.

• What comes to mind is that you need a 'least squares' method, but then in two dimensions. Maybe google for something like least squares 2 dimensions. I find stuff like On Least-Squares Fitting of Two-Dimensional Data with a Special Structure. Maybe add geography and mapping as additional keywords Jul 25, 2016 at 14:58
• Wouldn't you rather ask this in gis.stackexchange.com ? Aug 18, 2016 at 14:17
• What exactly shall your algorithm do? Adjust the position of the background picture until it matches the red line as best as possible? Change/Distort that picture? Or change the red line until it fits into the white corridor (but I guess since you wrote "the red line is correct", that is not what you want). Or are you simply looking for a metrics how "good" the redline matches the picture? Consider to edit your question to add some clarifying words. Nov 16, 2016 at 15:02

## 2 Answers

There is no need to compare the lines if you know the white one is faulty and the red one is ok. Just delete the existing white line from the original picture, then add a new white line which follows the red path and has a "thickness" which is comparable to the "thickness" of the original white line.

If that is not what you had in mind, or if it is not working for some reason you forgot to describe so far, feel free to comment or edit your question and improve it.

This is quick idea how I would do it:

1. Divide red line into points at appropriate interval
2. For each point, find closes point on white line.
3. Shift each point towards found point slightly. Maybe apply "bleed" that also shifts neighborhood points in same direction, but at reduced amplitude.
4. Repeat steps 2-3 until lines are close enough. Maybe create an error metric/heuristic to quit after difference is small enough.
5. The difference between where point started and ended is mapping between the two lines.
• What would define closest point on white line in this two-dimensional structure? Jul 25, 2016 at 15:03