给定3D空间中的N点，如何找到包含这些N点的最小球体？ [英] Given N points in a 3D space, how to find the smallest sphere that contains these N points?

问题描述

给定3D空间中的N个点，如何找到包含这些N个点的最小球体？

解决方案

被称为最小包围球问题。 （google这个词可以找到教程和论文）。

这是一个实现： http://www.inf.ethz.ch/personal/gaertner/miniball.html 在c ++中。

它的2d案例（找到一个圆圈来包围平面中的所有点）是计算几何课程教授的典型例子。 3D只是2D案例的简单扩展。

这个问题的一个算​​法是渐进式。你从4点开始，他们固定一个球体，当你添加第5点时，有两种情况：

1. 关键在于球体。不需要更新。




2. 在这种情况下，您需要更新球体。那么一个不平凡的财产就是这个新的一点必须在你的新领域！

根据上述观察，您的问题变小。阅读这本书的第4.7节。它也可以在谷歌书。

Given N points in a 3D space, how to find the smallest sphere that contains these N points?

解决方案

This problem is called minimal enclosing ball problem. (google this term to find tutorials and papers on it).

Here's one implementation: http://www.inf.ethz.ch/personal/gaertner/miniball.html in c++.

Its 2d case (find a circle to enclose all points in a plane) is a classic example taught in computational geometry course. 3D is just a simple extension to the 2D case.

One algorithm for this problem is incremental style. You start with 4 points and they fix a sphere, and when you add 5-th point, there are two cases:

1. the point is in the sphere. no need to update.

2. outside the point. In this case, you need to update your sphere. Then a non-trivial property is that this new point must be on your new sphere!

Based on the above observation, your problem gets smaller. Read section 4.7 of this book. It is also available on google book.

这篇关于给定3D空间中的N点，如何找到包含这些N点的最小球体？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！