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?

Agreeable

You may search beginning with "map matching", this is close to your problem. – Zinkenite

For detail views this is useful, but for a more zoomed out view I need to merge the two paths (lanes) For more zoomed out views you might want to merge the two lanes, but you could simply ignore one of them. If they are close enough to be represented by the centreline at large scale, this might satisfy your requirements and be easier to code. – Conception

If you did nothing extra and just plotted both neighboring lines, they would naturally overlap when you zoom out and automatically appear as if they were one line naturally depending on the zoom. But it seems you don't want that. So please explain what it is you don't like about that and what you want to avoid by doing something different than letting the lines overlap. What are your goals for a good solution that would be better than just writing out all lines and letting them overlap naturally when zoomed out? – Gonococcus

@Gonococcus You are right, in some situations simply plotting everything and letting it overlap (just showing what happens to be on top) might be enough. If the rendering of the map is more sophisticated, though (consider wanting labels on roads, but only once per road, or repeating textures, or outlines, shadows, etc), this approach leads to maps that simply do not look nice at all. – Agreeable

Answer 1

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.

Poplar

I like this, but the assumption about only wanting to merge two paths is wrong (roads can have more than two lanes). Of course your approach could be extended using tensors to accommodate for that, but I might just end up skipping the voting process and simply merge all the line segments that fall into the same bin (instead of paths) of the Hough transform, and in the end remove identical/overlapping paths. – Agreeable

One more issue that I see with this suggestion is two line segments that are parallel and the same distance from the origin would be considered by this algorithm to be merged (end up in the same bin in Hough space). But as those are line segments they need not necessarily actually be close (i.e. two segments on the same diagonal line, but one is in the far top left and one is in the far bottom right). How would you address this? – Agreeable

Answer 2

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}

Recitativo

Thank you for the pointer to the Frechet distance, I did not know of this before. However, as I understand it, this distance would still be large if a very short line segment lies very close to a much longer path. If so, that would be an issue, as I would want to merge a short path (i.e. short part where road is two lanes wide) that lies close to a much longer path (i.e. majority of the road that is one lane wide). Also, would your get_all_edge_with_frechet_distance_less_than_thr compare edges to entire paths or edges to edges? – Agreeable

we compare trajectories (each comprising of multiple edges/segments) with one another. one thing to note is that there is hardly any single correct answer (in deterministic way). – Recitativo

Answer 3

To find the distance between path A and path B:

• Given point X on path A
• Define line Y at 90 degrees to the line between point X and the next point.
• Calculate the intersection of the line Y with one of the lines in the path B
• Calculate the distance between point X and intersection point and you get the space between the paths at point X.

To create a path between two paths:

• The above method will help to find the distances.
• The new path will be the middle distance between the two paths.

Popularize