我在2D中有一组点。我想找到:
- 包含所有点的最小三角形
- 包含所有点的最小圆。
是否有相应的算法?我遇到了凸壳，以适应凸多边形的一组点。但是我想要一个圆和三角形。
Thanks in advance
如果你指的是面积，那么下面的算法可能是有用的。
三角形线性(即O(n))算法的实现，用于计算欧几里得二维空间中包围给定点集的最小面积三角形，如下开放获取科学笔记:O。Parvu和D. Gilbert，线性最小面积包围三角形算法的实现，计算与应用数学，Springer, pp. 1-16, 2014年11月。
本科学笔记仅提供了以下论文中最初引入的算法的详细描述:
J。O 'Rourke, A. Aggarwal, S. madila, M. Baldwin，一种寻找最小包围三角形的最优算法，算法学报，第7卷，第7期。2，第258-269页，1986年6月
免责声明:我是这篇科学笔记的作者之一。
该算法的c++ 实现在:
https://github.com/IceRage/minimal-area-triangle
，并将包含在OpenCV的下一个主要版本(3.0)中。
圆最小面积围圆算法在下面的文章中描述:
G。Bernd，快速鲁棒最小封闭球，第七届欧洲算法研讨会论文集(ESA)， Springer, pp 325-338, 1999.
该算法的c++ 实现在:
http://www.inf.ethz.ch/personal/gaertner/miniball.html。
对于这两个问题都有O(n)种算法，但它们都是非平凡的。请参阅http://en.wikipedia.org/wiki/Smallest-circle_problem和http://prografix.narod.ru/source/orourke1986.pdf。计算一个轴对齐的边界框，或者将一个圆或等边三角形居中于凸包的坐标平均值会容易得多。这可能是考虑您的真正需求是什么，或者找到一个库实现的好时机。