CODEWITHSUNDEEP
algorithmgraphicsgeometrygiscartography
anroesti
anroesti

Reputation: 11383

Algorithm for merging spatially close paths / line segments

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:

Graph of a road network, consisting of three horizontal lines running across the image almost in parallel and one vertical line intersecting them in the middle

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?

Upvotes: 13

Views: 3423

Answers (3)

Edward Aung
Edward Aung

Reputation: 3512

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}

Upvotes: 3

Ahmed Elyamani
Ahmed Elyamani

Reputation: 496

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 aij is the votes for merging the ith and jth 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:

  1. 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.

Upvotes: 3

codeDom
codeDom

Reputation: 1769

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.

Upvotes: 0

Related Questions