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

Question

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

$Illustration of $\alpha$ size effect$

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.

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 04: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

score 4 · Accepted Answer · answered Jul 24 '12 at 18:07

4

You might investigate the so-called alpha-hull, for example: CRAN package, Wikipedia on alpha shapes:
enter image description here
_{[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.

answered Jul 24 '12 at 18:07

Joseph O'Rourke

543
2
9

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

score 1 · Answer 2 · answered Jul 27 '12 at 22:46

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.

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

2 Answers2