geometry - 如何找到包围所有给定点的最小半径圆？

Question

假设我在飞机上有大约 1000 个奇点。

然后，我认为可以做的是丢弃不以任何方式影响圆半径的点-凸包不通过的点[使用几种算法之一]。这给我们留下了重要的观点。

现在从这里开始，可以做些什么来找到最小半径的圆？

一旦我了解了如何为圆完成此操作，我希望将其推广到椭圆。

任何指向某些“公共源代码”的链接都会有所帮助，以便我可以将其修改为省略号。

Answer 1

这被称为最小封闭圈问题（我很困惑为什么您的谷歌搜索没有显示任何内容），并在此处、此处、此处和许多其他地方进行了讨论。

Answer 2

一种选择是CGAL 计算几何算法库。它是开源的，但它也很大——我怀疑你遇到的最大问题是大海捞针。

当然（这部分是为了向 Martin 道歉），您可以使用 Google 轻松找到更集中的选项。如果您不介意 Prolog，那么当我尝试时，列出的第二项看起来还不错，并且在结果的第一页上至少有一个 C 示例和一个 Javascript。你几乎不能再向谷歌声称不知道这些词了。