Generating a minimal convex polygon

19 次查看（过去 30 天）
Mark
Mark 2014-2-18
评论： Image Analyst 2021-5-18
So I'd like to generate a convex polygon around a set of points, where the number of vertices is an input. I'm aware of convexhull, but this produces far too many vertices for my needs. I'd like a convex polygon (with the smallest area possible) that surrounds all my points (or the convex hull, same thing). For example, If I had 2-D data points that form a circle, and I want a 5 vertex polygon, you can imagine that it would look like an equal sided pentagon tangent to the circle in 5 places. Any ideas? Thanks

请先登录，再回答此问题。

回答（4 个）

Image Analyst
Image Analyst 2014-2-19
I think Mark might like John D'Errico's very nice suite of minimally bounding shapes: http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects. Mark can pick the shape he's interested in.
Boris Blagojevic
Boris Blagojevic 2021-5-17
In case someone stumbles over this:
An easy alternative is using hull = convull(Points,'Simplify',true). All Points which add no area are neglected with this. I think that is quite what was asked for.
  1 个评论
Image Analyst
Image Analyst 2021-5-18
That's a nice feature. It won't however turn a circle into a pentagon (the example the original poster mentioned). For that, or for situations where the shape is not convex, one might refer to the attached paper on "minimum perimeter polygon".

请先登录，再进行评论。

John D'Errico
John D'Errico 2014-2-18
You have stated an ill-posed problem, because your goals are not clear. Clearly THE minimal convex polygon is the convex hull. But you are asking for the minimal convex polygon with n vertices, where n<H, the number of vertices of the convex hull. Is n fixed? If not, then what measure is used to choose n?
Even if n is fixed, it is not clear what the best scheme is. For some values of n, it is likely that the minimal enclosing polygon has some edges that are coincident with edges of the convex hull, but choosing those edges may be difficult.
And if the enclosed object is some completely general closed, smooth form, the problem is now more difficult yet.
Sorry, but you need to define your goals more clearly, and make those goals have a snowball's chance in Texas to represent a solvable problem.
arich82
arich82 2014-2-19
It seems like you've already eaten the computational cost of finding the 2-D convex hall (resulting in a convex n-gon). It sounds like, for a given number of vertices k, you're asking to find the minimum circumscribing convex k-gon, where k<n.
This is not a trivial problem, unless k=3.
See if Aggarwal et. al (1985) [and references therein] might be helpful: http://link.springer.com/article/10.1007%252FBF01898354. They report to have an order O(n^2 log(n) log(k)) algorithm, though they don't seem to claim optimality.
Note: If you have a more structured problem, e.g. you're just looking to identify a box with long edges but there are some rounded corners artificially increasing n, then you could likely devise a simple algorithm to eliminate sides below a certain threshhold length, and extend their neighbors to intersect; note that this wouldn't gurantee a minimal solution, but might be a practical one.

类别

在 Help Center 和 File Exchange 中查找有关 Bounding Regions 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by