20

I'm using Shapely in python and I'm given a MultiLineString with a bunch of Linestring objects. I can guarantee that all the LineString objects are simple lines with only 2 vertices and that they are all part of one single line (no branches).

I want to "connect-the-dots" and create a single LineString.

Do I need to write a recursive welding method for this or is there a faster way?

0
31

You can use shapely's ops.linemerge to accomplish this:

from shapely import geometry, ops

# create three lines
line_a = geometry.LineString([[0,0], [1,1]])
line_b = geometry.LineString([[1,1], [1,0]])
line_c = geometry.LineString([[1,0], [2,0]])

# combine them into a multi-linestring
multi_line = geometry.MultiLineString([line_a, line_b, line_c])
print(multi_line)  # prints MULTILINESTRING ((0 0, 1 1), (1 1, 2 2), (2 2, 3 3))

# you can now merge the lines
merged_line = ops.linemerge(multi_line)
print(merged_line)  # prints LINESTRING (0 0, 1 1, 2 2, 3 3)

# if your lines aren't contiguous
line_a = geometry.LineString([[0,0], [1,1]])
line_b = geometry.LineString([[1,1], [1,0]])
line_c = geometry.LineString([[2,0], [3,0]])

# combine them into a multi-linestring
multi_line = geometry.MultiLineString([line_a, line_b, line_c])
print(multi_line)  # prints MULTILINESTRING ((0 0, 1 1), (1 1, 1 0), (2 0, 3 0))

# note that it will now merge only the contiguous portions into a component of a new multi-linestring
merged_line = ops.linemerge(multi_line)
print(merged_line)  # prints MULTILINESTRING ((0 0, 1 1, 1 0), (2 0, 3 0))
7
  • How can I know which linestring was merged ? I want to receive a list like: merged = [[line_a,line_b],[line_c]]
    – james
    Jan 2 '18 at 10:49
  • You could loop through a list of your individual lines and check whether the new merged line contains() the individual lines. Those not contained would not have been merged. e.g. merged_line.contains(line_a) which would return a boolean True or False
    – songololo
    Jan 2 '18 at 11:07
  • thanks a lot. How do you check if the line is contained in the merged_lines ?
    – james
    Jan 2 '18 at 11:14
  • 1
    ah, I didn't understand that ".contains(line_a)" was a prewritten function. perfect. Thanks a lot !
    – james
    Jan 2 '18 at 11:29
  • 2
    sorry, to bother you again... but do you know who to merge lines which are "close" (within a certain maximum distance from each other) ? I am asking because I am seeing many lines which should be merged, but due to a small gab between them, they are not merged.
    – james
    Jan 6 '18 at 8:54
2

I think you could do it with Shapely using shapely.ops.linemerge() method.

It looks like it could take a list of lines as input and merge them. I used the 'polygonize' method before and it does take a list of lines.

Take a look at the doc here: http://toblerity.org/shapely/manual.html#shapely.ops.linemerge

2
  • 1
    Do you know how to merge lines which are "close" (within a certain maximum distance from each other) ?
    – james
    Jan 6 '18 at 16:34
  • polygonize_full works somewhat better, but I got some strange datastructures as a result
    – danuker
    Jul 12 '19 at 10:08
1

shapely.ops.linemerge works if the lines are contiguous ("tips" coincide with the "tails" of the constituent lines), but if they are non-contiguous (if there's a gap between the tips and tails) it returns another MultiLineString. If your constituent lines are well-ordered (with one line ending near the start of the next line) but have a tip-to-tail gap, you can extract the coordinates and use them make a new simple line. This approach also works for multi-lines made of more complex sublines (i.e. sublines with more than two points).

import shapely

# Make a MultiLineString to use for the example
inlines = shapely.geometry.MultiLineString(
    [shapely.geometry.LineString([(0,0),(0,0.9)]), 
     shapely.geometry.LineString([(0,1),(1,1)])]
)

# Put the sub-line coordinates into a list of sublists
outcoords = [list(i.coords) for i in inlines]

# Flatten the list of sublists and use it to make a new line
outline = shapely.geometry.LineString([i for sublist in outcoords for i in sublist])
1

shapely.ops.linemerge() failed for some of my lines so I had to do it manually. It seems to fail for the lines that "returned" to itself, i.e., going through the same point more than once. For my case, I know that the lines are in the correct order so it was easy to write a small function to merge them.

from shapely.geometry import LineString
from typing import List


def merge_lines(lines: List[LineString]) -> LineString:
    last = None
    points = []
    for line in lines:
        current = line.coords[0]

        if last is None:
            points.extend(line.coords)
        else:
            if last == current:
                points.extend(line.coords[1:])
            else:
                print('Skipping to merge {} {}'.format(last, current))
                return None
        last = line.coords[-1]
    return LineString(points)

Hope it helps someone

Not the answer you're looking for? Browse other questions tagged or ask your own question.