Python Shapely – How to Sort Points in a MultiLineString for Continuous LineString

linelinestringpythonshapelysorting

Is there a way to "sort" the points of a MultiLineString such that they follow a more sequential order? Let me illustrate what I mean with a graphical example:

Input

Suppose I have the following MultiLineString: MULTILINESTRING ((120 105, 140 98),(160 103, 140 98),(100 100, 120 105))
Input MultiLineString

Note how, to our human eyes, it seems out of order: the first (orange) segment is in the middle, the second (green) segment is coded backwards in relation to the other segments (i.e., pointing to the left instead of to the right).

Desired Output

The desired output would be the following LineString: LINESTRING (100 100, 120 105, 140 98 160 103)

Output LineString

Note how the output is now looks much more sensible. It's one continuous LineString, the segments are all nicely ordered from left to right and the green segment itself is now oriented from left to right.

Is there a simple way to perform this kind of "reordering" inside MultiLineStrings?

What I've done so far

I'm trying to develop a solution using Python's Shapely library. My approach has two different steps:

  • Extract unique coordinates
  • Sort unique coordinates

I've been able to do the first part quite easily, but it's not clear to me how to reorder the points.

I thought about a heuristic that would find the point that is cumulatively furthest to all other points, label that as the starting point, add all other points to a pool of unsorted points and then sequentially find the next closest point until I run out of unsorted points.

However, this sorting heuristic would fail in A BUNCH of cases: consider a geometry that describes a spiral. Or a strong zig-zagging pattern. Or a geometry with a bunch of self-intersections. This heuristic would just fail completely.

Therefore, I suspect this approach of extracting unique points and sorting them isn't the right one.

Back to the start

So, I'm back to my main question: how can I sort the coordinates of a MultiLineString such that they make more intuitive sense?

Reproducible example and code

Here's the Python code for my very incomplete solution thus far.

import shapely

# Write the MultiLineString WKT
mls_wkt = 'MULTILINESTRING ((120 105, 140 98),(160 103, 140 98),(100 100, 120 105))'

# Generate the shapely geometry
mls = shapely.wkt.loads(mls_wkt)

# Function that extracts unique coordinate values
def get_unique_points(input_multilinestring):
    # Gets a nested list of coordinates
    coords_nested = [list(this_geom.coords) for this_geom in input_multilinestring.geoms]
    
    # Flattens the list
    coords = [item for sub_list in coords_nested for item in sub_list]

    # Gets only the unique coords
    coords_set = set()
    coords_final = []
    for i,coord in enumerate(coords):
        if coord not in coords_set:
            coords_set.add(coord)
            coords_final.append(coord)
    return coords_final

Best Answer

You might be able to just use shapely.ops.linemerge. I haven't used it much, and cannot speak to how it handles potential floating point differences where the geometries in the MultiLineString meet.

from shapely import wkt
from shapely.ops import linemerge


mls = wkt.loads('MULTILINESTRING ((120 105, 140 98),(160 103, 140 98),(100 100, 120 105))')

line_string = linemerge(mls.geoms)
# LINESTRING (100 100, 120 105, 140 98, 160 103)
Related Question