9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Have you looked into the concept of strongly convex sets? $\endgroup$ – Deathbreath Jul 24 '12 at 16:19
  • $\begingroup$ Could you clarify the purpose of $\alpha$? What purpose does it serve? $\endgroup$ – Paul♦ Jul 24 '12 at 17:42
  • $\begingroup$ 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? $\endgroup$ – hardmath Jul 25 '12 at 4:46
  • $\begingroup$ 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. $\endgroup$ – naufraghi Jul 25 '12 at 10:44
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – naufraghi Jul 25 '12 at 11:29
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.