如何找到包围一组点的最复杂的凸多边形？
我有一个（大约 200-300）2d 点的列表。我知道需要找到包围所有这些的多边形。多边形必须是凸的，并且应该尽可能复杂（即不是矩形边界框）。它应该在尽可能短的时间内找到它，但对内存没有限制。
您可以用伪代码或任何您想使用的语言来回答。
I have a list of (about 200-300) 2d points. I know needs to find the polygon that encloses all of them. The polygon has to be convex, and it should be as complex as possible (i.e. not a rectangular bounding box). It should find this in as low as possible time, but there are no restrictions on memory.
You may answer in pseudocode or any language you want to use.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
听起来您正在寻找凸包算法？距离我学习这些知识已经有十多年了，但 Graham Scan 这个名字一直在我的脑海中挥之不去，并且可能就是我开始的地方。
Sounds like you're looking for a convex hull algorithm? It's been more than a decade since I was taught about these, but the name Graham Scan sticks in my mind and would probably be where I'd start.
看看格雷厄姆算法。
Take a look at Graham's Algorithm.
Qhull 是计算 2D 凸包的好软件。
Qhull is good software for computing 2D convex hulls.
如果这是一个现实世界的问题 - 例如，而不是学术问题 - 永远没有真正的理由来解决这样一个通用问题你自己。
If it is a real world problem - as in, not an academic one - there's never really a reason to solve such a generic problem yourself.