gpt4 book ai didi

algorithm - 我怎样才能找到包含一些给定点的最小圆圈?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:30:33 25 4
gpt4 key购买 nike

我已经给出了一些点(二维坐标)并希望找到包含所有这些点的最小圆。该算法不必非常高效(虽然它自然会很好)。

最佳答案

这就是所谓的最小封闭球问题(在您的例子中,最小封闭圆),又名迷你球。这个问题有几种算法和实现 - 以下所有都是线性时间解决方案(即,给定 n 个球,它们在 O(n) 内运行,如果您认为维度 d 是固定的,d=2 在您的情况下):

  • 对于 2D 和 3D,Gärtner's implementation可能是最快的。

  • 对于更高的维度(比如高达 10,000),请查看 https://github.com/hbf/miniball ,这是 Gärtner、Kutz 和 Fischer 对算法的实现(注:我是合著者之一)。

  • 对于非常非常高的维度,核心集(近似)算法会更快。

注意:如果您正在寻找一种算法来计算球体的最小封闭球体,您将在Computational Geometry Algorithms Library (CGAL) 中找到C++ 实现。 . (您不需要使用所有 CGAL;只需提取所需的头文件和源文件即可。)

关于algorithm - 我怎样才能找到包含一些给定点的最小圆圈?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3102547/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com