Is there an algorithm to find an almost-convex hull given a tolerance angle?

I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows more closely the "perimeter".

And if there is a definition of a non intersecting perimeter of a set of points, in this case the resulting polygon when $\alpha$ is big.

Another view of the problem can be to find an algorithm that can be parametrized to find for $\alpha = 0$ the minimum perimeter solution (convex-hull) and for $\alpha = 1$ (normalized) the minimum area polyline enclosing all the points.

• Have you looked into the concept of strongly convex sets? – Deathbreath Jul 24 '12 at 16:19
• Could you clarify the purpose of $\alpha$? What purpose does it serve? – Paul Jul 24 '12 at 17:42
• Would it be allowed to propose an algorithm that does more work as $\alpha$ grows? Or did you expect increasing $\alpha$ would decrease "expected" complexity? – hardmath Jul 25 '12 at 4:46
• I intended it as the angle the algorithm is allowed to move away from the convex hull. And no, I don't think it will decrease the complexity. – naufraghi Jul 25 '12 at 10:44

You might investigate the so-called alpha-hull, for example: CRAN package, Wikipedia on alpha shapes:

[Image from this link.]

The alpha-hull has very nice geometric properties, and has been heavily studied, but it still might not serve your purposes.

• Thanks, alpha-shapes are very interesting, they have a superset of the properties I was searching for (I'm interested only in a single envelope), and the implementation is not comparable with the convex-hull one. I'll wait a bit more if someone can suggest something simpler, if not I'll accept this answer. – naufraghi Jul 25 '12 at 11:29

This may be too simple to be of interest, but one approach would be to find the convex hull and use the polygonal boundary segment by segment to locate additional points that satisfy the $\alpha$-angle criterion, stopping once a full circuit has been completed without adding further vertices. More than once pass may be required to reach "convergence".

The $\alpha$-angle criterion may be formulated for a given pair of consecutive boundary vertices as lying in a region between a circular arc and its chord = boundary segment. One might term this a circular segment.

We'd want to give some thought to a data structure that would make finding the specified points efficient. One idea would be to compute a bounding box for each segment and check it against a sorted list of the points.