algorithm - 包含一组点的三角形/圆

Question

我有一组二维点。我想找到:

1. 包含所有点的最小三角形
2. 包含所有点的最小圆。

是否有任何算法可以做到这一点？我遇到了 Convex Hull 来为一组点拟合凸多边形。但我想要一个圆形和三角形。

提前致谢

Answer 1

如果您指的是该区域，那么以下算法可能会有用。

三角形

线性(即 O(n))算法的实现在欧几里德二维空间中计算包围给定点集的最小面积三角形在以下开放存取科学中描述注意:

哦。 Parvu 和 D. Gilbert，线性最小面积封闭三角形算法的实现，计算和应用数学，Springer，第 1-16 页，2014 年 11 月。

本科学笔记仅对以下论文中最初介绍的算法提供了详细描述:

J. O'Rourke、A. Aggarwal、S. Maddila 和 M. Baldwin，寻找最小封闭三角形的最佳算法，算法杂志，卷。 7，没有。 2，第 258–269 页，1986 年 6 月。

免责声明:我是这篇科学笔记的作者之一。

该算法的 C++ 实现可在以下位置获得:
https://github.com/IceRage/minimal-area-triangle

并将包含在 OpenCV 的下一个主要版本 (3.0) 中。

圈子

以下论文描述了最小面积包围圆算法:

G. Bernd，Fast and Robust Smallest Enclosing Balls，第七届年度欧洲算法研讨会 (ESA) session 记录，Springer，第 325-338 页，1999 年。

该算法的 C++ 实现可在以下位置获得:
http://www.inf.ethz.ch/personal/gaertner/miniball.html .