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.

screenshot of the project

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.


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.


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *