Python - Convex Hull with Some Permissible Interior Points

I'd like to make a convex hull of a set of 2D points (in python). I've found several examples which have helped, but I have an extra feature I'd like that I haven't been able to implement. What I want to do is create the convex hull but allow it to pick up interior points if they are sufficiently "close" to the boundary. See the picture below -> if theta < x degrees, then that interior point gets added to the hull.

Obvious this can make things a bit more complex, as I've found out from my thoughts and tests. For example, if an interior point gets added, then it could potentially allow another further interior point to be added.

Speed is not really a concern here as the number of points I'll be working with will be relatively small. I'd rather have a mo开发者_如何学Cre robust algorithm then a quick one.

I'm wondering if anyone knows of any such example or could point me in the right direction of where to start. Thanks.

---

Concave hull might be what you're looking for, though it doesn't use an angle as far as I know. The algorithm that the LOCAL project uses seems to use k nearest neighbours.

---

You could first compute the convex hull, and then ruin round the edges of that seeing if any of the edges should be broken to include an interior point.

---

The notion you are looking for may be alpha-shape. Tuning alpha, you admit more or less points in your concave hull. Look at Edelsbrunner algorithm for alpha-shape finding.