如何找到包围一组点的最复杂凸多边形？

Question

3

我有一个包含大约200-300个2D点的列表。我需要找到能够包围它们所有的多边形。这个多边形必须是凸多边形，并且应该尽可能复杂（即不是矩形边界框）。要在尽可能短的时间内找到它，但是对内存没有限制。

您可以用伪代码或任何您想使用的语言回答。

- Marius

2

他可能意思完全不同：“覆盖面积最小”。你可以通过减少多边形的复杂性来增加包含的面积，所以他可能颠倒了这种思考方式并走得太远了。 - Craig Gidney

4个回答

4

- zebrabox

1

Qhull 是一个计算二维凸包的好软件。

- Suresh

0

如果这是一个现实世界的问题 - 也就是说，不是学术性的问题 - 你没有必要自己解决这样一个通用的问题。

- Ofek Shilon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- crazyscot · Accepted Answer

看起来你正在寻找一种凸包算法？虽然我已经超过十年没有关注这方面的知识了，但“Graham扫描”这个名称仍在我脑海中，并且可能是我开始的地方。