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

Couldn't you create a set of points based on the endpoints of the lines? Then it would be the same as the 'normal' concave hull problem. — Calvin Godfrey, Jul 29 '19 at 19:34
First, I still need a python implementation for that (and would love to have one, even if it doesn't support the lines info), Second I think that the lines themselves add some information to the problem that should be used — user972014, Jul 29 '19 at 20:02
Why would the lines add any information? In the end the concave hull is about the (end-)points and from these you can generate the lines anyway (and vice versa). Since you didn't show us any code to get started, it's difficult to help you with your specific implementation. Could you provide an example? — a_guest, Jul 29 '19 at 20:37
Your question, as worded, is confusing. You need to clarify _if_ the points where the lines intersect are expected to contribute to the hull or not. Otherwise, the lines are irrelevant and distracting information. — Tasos Papastylianou, Aug 02 '19 at 08:47
There are numerous `O(n log n)` vertex-only convex hull algorithms, but the number of lines joining `n` points can be as large as `O(n^2)` (theoretical maximum `n(n-1)/2`) - the act of even *creating* them itself can be more expensive (asymptotically speaking) than computing the convex hull from the points directly. — meowgoesthedog, Aug 02 '19 at 09:09

Stef · Accepted Answer · 2019-08-08T09:03:08.183

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

is there a way to query if a point is inside the polygon concave hull? — Alejandro, Jan 14 '22 at 10:47
@Alipapa https://stackoverflow.com/questions/16750618/whats-an-efficient-way-to-find-if-a-point-lies-in-the-convex-hull-of-a-point-cl ? — Stef, Jan 14 '22 at 10:49

score 5 · Answer 2 · edited Nov 18 '20 at 00:15

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.

Python Concave Hull Polygon of a set of lines

2 Answers2

Linked