What are the best algorithms to match segments?
I'm trying to match corresponding segments from two map sources, one less accurate but with segment names, and one more accurate without segment names. I want to semi-automatically apply the segment names to the more accurate map.
The requested algorithm has quite a vague description because a "match" is not well defined, and many factors (orientation, relative length, distance) might have different weight in different scenarios; However, I'm looking for a basic knowledge about the general approaches for handling this problem.
Working implementations for open-source environment (PostGIS, shapely, …) are warmly welcome.
Sample segments : See description below images.
Best Answer
The Hausdorff distance may be used: matching segments could be 'close' segments according to this distance. It is quite simple to compute on segments.
A free java implementation is available in JTS - see JTS Distance Package. You may also have a look at the JCS Conflation Suite (now abandoned, copy of sources e.g. at https://github.com/oschrenk/jcs).