Python Concave Hull Polygon of a set of lines

Question

I'm looking for a python implementation for the Concave Hull problem. My problem is a bit different since I don't have a set of points, but a set of lines, where the result Concave-Hull will roughly bound along the lines (as in the left drawing).

I understand that there is no single "correct answer". But some approximation will be enough for my needs. One possible solution is to take each line and interpolate it to a range of let's say 20 points and find the concave hull of all the created points. Not sure about it.

Edit:

I think the lines add some value making the hull clearer and easier to find.

A good python implementation for the problem, even if not using the lines (just finding a concave hull from a list of points) will also be helpful

Answer 1

This is an answer for your subquestion:

A good python implementation for the problem, even if not using the lines (just finding a concave hull from a list of points) will also be helpful

You could use alphashape. The tricky part is to choose an alpha that fits your needs. Alphashape comes with a function to find the optimum alpha value. Basically it starts with 0 (= convex hull) and increases alpha until it starts loosing points. From this optimum value we take 95 %, which is, of course, a rather arbitrary solution, but it'll give you a good approximation in many cases.

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

points = [(17, 158),(15, 135),(38, 183),(43, 19),(93, 88),(96, 140),(149, 163),(128, 248),(216, 265),(248, 210),(223, 167),(256, 151),(331, 214),(340, 187),(316, 53),(298, 35),(182, 0),(121, 42)]

alpha = 0.95 * alphashape.optimizealpha(points)
hull = alphashape.alphashape(points, alpha)
hull_pts = hull.exterior.coords.xy

fig, ax = plt.subplots()
ax.scatter(hull_pts[0], hull_pts[1], color='red')
ax.add_patch(PolygonPatch(hull, fill=False, color='green'))

One possible solution is to take each line and interpolate it to a range of let's say 20 points and find the concave hull of all the created points.

This will not give you the desired output as the concave hull will follow these additional (fake) points and it becomes more concave than it can be with the original points.
I think the best solution for the whole problem is to start with the concave hull of the points for the optimum alpha obtained from optimizealpha and then decrease it until your hull doesn't intersect any of your lines as suggested by @sgillen. This can be done similarly to finding the optimum alpha by using a bisection loop with testing any([polygon.crosses(line) for line in lines]).