Algorithm for merging spatially close paths / line segments

Question

I am looking for (the name of) a geometric algorithm for cartographic generalization of a street map.

In my map data, I have many paths (ordered list of points, connected by line segments) that lay close and almost parallel to one another. How do I (1) identify these “adjacent pathsˮ (i.e. how to find paths that are closer than a certain threshold) and (2) merge them into one path (i.e. how to compute the centerline between close paths)?

As an example, consider the following graph of roads / lanes of roads created with data from OpenStreetMaps:

As you can see, the two lanes of the road running horizontally are modeled as two separate paths. For detail views this is useful, but for a more zoomed out view I need to merge the two paths (lanes) to display only one line for the road.

What are the established algorithms used in map renderers to achieve this? Obviously, Google Maps, OSM, etc. do this -- how?

Answer 1

I had studied a problem similar to this as a researcher. my paper on frequent route This is about given a bunch of trajectories (at different time/speed), how to reverse-engineer the road segments.

You can use Frechet distance to measure the distance between segments and cluster the line segments using the distance. For each cluster, you can assign a representative line-segment. That's the gist of the solution.

A simplier way to achieve is using the following algorithm:

def reduce_segments (G : graph):
    for e in G.edges: 
        if not e.mark: 
            continue
        similar_edges = get_all_edge_with_frechet_distance_less_than_thr(G.edges, thr)
        for se in similar_edges:
            se.mark = True
    return {ee : ee in G.edges and ee.mark == False}

Answer 2

This is not what it's for, but how about doing something like a Hough transform?

To find close-enough paths:

1. Transform line segments into hough space (r, θ),
2. Let each point vote for its closest available "bin". You can determine the bin quantization based on how much you want your tolerance for merging two paths to be.
3. Each point in the accumulator should also keep a reference to its parent path, and the length of the line segment.
4. Find the bins that contain exactly two votes, because we're only interested in merging two paths
5. Create an nxn accumulator matrix A, with n being the number of paths you have, such that a_ij is the votes for merging the i_th and j_th path, this will be a mostly sparse matrix.
6. For each one of our bins of interest, vote in the accumulator matrix in the cell corresponding to its two parent paths.
7. If a cell exists in the accumulator matrix that has a sufficiently large number of votes (that is, a sufficient number of line segments in these paths are considered by the algorithm tolerably similar), then these two paths may be merged.

To merge the two paths:

8. Transform back the points from the selected bins into cartesian space, use the length (which was kept reference), slope, and position to define each line segment corresponding to each bin.