Python Concave Hull Polygon of a set of lines

Here is a github repo on finding the concave hull for a set of points using python.

My recommendation to you is the following. Create a set of points using the endpoints of each line. Then use the linked to code to generate a concave hull for these points, with some guess for the value of alpha. Once this is done you can check if the generated hull intersects any of your lines, and if it does modify alpha. You can make the check for intersection and adjustment automated if you like.

You could also try adding the midpoints of your lines to your set of points, that may decrease the number of alphas you need to try.

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]).