Get the outer shape of a MultiLineString

Question

i have a bunch of shapely MultiLineStrings, which I would like to "convert" to Polygons so that the "outer" boundaries of the MultiLineStrings serve as edges.

One of my MultiLineStrings looks like this:

Using

import matplotlib.pyplot as plt
x = my_gdf.geometry.iloc[0].convex_hull
ax = my_gdf.geometry.iloc[:1].plot()
x,y = x.exterior.xy
ax.plot(x, y)

, I can obtain the convex hull, resulting in:

However, what I would like to have is something like:

(note, that the outer blue line is the convex hull)

Is there a shapely operation or similar in Python, that can give me this "outer boundary"?

Answer 1

New Answer:

It turned out, the thing I was looking for was the so-called concave hull, or alpha shape of the string. There are implementations to calculate the alpha shape, and I found one particularly helpful post on StackOverFlow. The only drawback is that alpha has to be chosen for each set of points within the MultiLineString individually. This alpha can be optimized by alphashape but the time it takes seems to scale with the number of points.

import alphashape
import matplotlib.pyplot as plt
from time import time
from descartes import PolygonPatch

# Get Points from MultiLineString
# mls is a MultiLineString
points = []
for line in mls:
    for c in line.coords:
        points.append(c)
points = np.array(points)

# Get optimal alpha and alpha shape
alpha = 0.95 * alphashape.optimizealpha(points, lower=0, upper=0.01, max_iterations=100)
hull = alphashape.alphashape(points, alpha)
hull_pts = hull.exterior.coords.xy

# Plot it
ax = gdf.iloc[1:2].plot()
ax.scatter(hull_pts[0], hull_pts[1], color='red')
ax.add_patch(PolygonPatch(hull, fill=True, color='green'))

I might still need to resample some points on the lines, but otherwise it's great.

Old:

After some tinkering, I found a solution by myself:

Edit: This only works when the MultiLineString forms some sort of Linear Ring. When Lines are not connected, polygonize returns an empty list.

import matplotlib.pyplot as plt
from shapely.geometry import MultiPolygon
from shapely.ops import polygonize, unary_union

multi = MultiPolygon(list(polygonize(my_gdf.geometry.iloc[0])))
poly = unary_union(mp)

ax = my_gdf.geometry.iloc[:1].plot()
x,y = poly.exterior.xy
ax.plot(x, y, color="orange")

The orange line is the boundary of the poly polygon, encompassing all the lines of the multilinestring.