CODEWITHSUNDEEP
pythonalgorithmgeometryconvex-hull
Scott B
Scott B

Reputation: 2602

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.

enter image description here

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 more 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.

Upvotes: 2

Views: 1538

Answers (3)

kiriloff
kiriloff

Reputation: 26333

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.

Upvotes: 0

dmuir
dmuir

Reputation: 644

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.

Upvotes: 0

Aleksi Torhamo
Aleksi Torhamo

Reputation: 6632

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.

Upvotes: 2

Related Questions