给定一个 3D 点云，我如何找到包含给定点百分比的最小边界球体？
即如果我有一个带有一些噪声的点云，并且我想忽略 5% 的异常值，如果我不知道哪些点是异常值，我怎样才能得到包含 95% 剩余点的最小球体？
示例:我想找到绿色球体，而不是红色球体:
我正在寻找一种相当快速且简单的算法。它不必找到最优解，合理的近似也可以。
我知道如何计算 100% 点的近似包围球，例如与 Ritter 的算法。
我如何将其推广到找到包含 x% 点的最小球体的算法？
最佳答案
只是一个想法:二分查找。
首先，使用边界球之一 algorithms首先找到 100% 的包围球。
将 95% 球体的中心点固定为与 100% 球体的中心点相同。 (不能保证它是，但你说你可以接受近似答案。)然后对球体的半径使用二进制搜索，直到得到 95% +- epsilon。里面的点。
假设这些点按它们与中心点的距离(或平方距离，稍微快一点)排序，对于固定半径 r需要 O(log n)查找半径为 r 的球内点数的操作，例如通过使用另一个二进制搜索。二分查找右边r本身需要对数这样的评价。因此，在找到 100% 的球体后，整个搜索应该只需要 O(log2n) 步。
编辑:如果您认为缩小球体的中心可能离完整球体太远，您可以重新计算边界球体，或者只计算点集的质量中心，每次丢掉一些点之后。每次重新计算不应超过 O(n)。重新计算后，根据点与新中心点的距离对点进行排序。由于您希望它们已经接近排序，因此您可以依靠冒泡排序，它对于接近排序的数据在 O(n + epsilon) 中工作。请记住，只需要这些测试的对数数量，因此您应该能够在整个过程中接近 O(n log2 n)。
这取决于您所寻求的性能以及您愿意为此牺牲的性能。 (我很高兴得知我错了，并且有一个很好的精确算法。)
关于algorithm - 包含 x% 点的最小包围球，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39705456/