如何找到包含一些给定点的最小圆? [英] How can I find the minimal circle include some given points?

问题描述

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

I have given some points (2D-coordinates) and want to find the smallest circle, that includes all of this points. The algorithm doesn't have to be very efficient (while it would be nice naturally).

推荐答案

这就是所谓的Smallest Enclosure Balls 问题(在你的情况下，Smallest Enspiring Circle)，又名迷你球.这个问题有几种算法和实现——以下所有都是线性时间解决方案(即，给定 n 个球，它们以 O(n) 运行，如果您认为维度 d 是固定的，在您的情况下是 d=2):

This is the so-called Smallest Enclosing Balls problem (in your case, Smallest Enclosing Circle), a.k.a. Miniball. There are several algorithms and implementations out there for this problem – all of the following are linear-time solutions (i.e., given n balls, they run in O(n) if you consider the dimension d fixed, d=2 in your case):

• 对于 2D 和 3D，Gärtner 的实现可能是最快的.

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

For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

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

For very, very high dimensions, core-set (approximation) algorithms will be faster.

注意:如果您正在寻找一种算法来计算球体的最小封闭球体，您将在 计算几何算法库 (CGAL).(您不需要使用所有 CGAL；只需提取所需的头文件和源文件即可.)

Note: If you are looking for an algorithm to compute the smallest enclosing sphere of spheres, you will find a C++ implementation in the Computational Geometry Algorithms Library (CGAL). (You do not need to use all of CGAL; simply extract the required header and source files.)

这篇关于如何找到包含一些给定点的最小圆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！