通过球体的联合近似实体

Question

我有一个3D实体,表示为一组多面体凸壳的联合.(或者单个凸起,如果这样可以使事情变得更容易.)我想将该实体近似为一组球体的并集,以最小化集合中球体的数量和近似中的误差.(后一个目标是刻意模糊的:任何合理的误差度量都可以.同样,目标组合的方式在空中;要么球体的数量或误差度量可能受到限制,要么两者的某些功能可以最小化.我不想把自己指定到一个角落.)

近似值不需要完全包含原始集合或完全包含在原始集合中.每个球体可以具有任意半径.

这感觉就像NP完全的问题,并且在任何情况下都不太可能使用精确方法,所以我假设解决方案在于随机优化领域.感觉k-means的某些变体可能适合(将未覆盖的位置分配给它们最近的球体,并精炼球体以覆盖其中的一些),但我不确定如何处理多重覆盖的位置,或者如何找到局部的,不一定是覆盖 - 即使对于单个球体也是最佳的.此外,对于迭代方法,效率很重要,并且执行3D布尔操作不会有效.

Answer 1

问题并不简单,但以前已经研究过了.中心概念是中轴,可以通过无限的球联合来看待对象的表示.解决您问题的关键文章是:

"力量外壳,球的联合和内轴转换." Nina Amenta,Sunghee Choi,Ravi Krishna Kolluri.计算几何.第19卷,第2-3期,2001年7月,第127-153页.(期刊链接.)

 
(图像来源:从点云到动力结壳.)

第二篇论文是

Cazals,Frédéric,et al."用于球的集合的贪婪几何算法,应用于几何近似和分子粗粒化." 计算机图形论坛.卷.33. No. 6. 2014.(PDF下载.)

第一句话是"选择最接近3D物体的球是一个非平凡的问题."!它们的主要应用是分子模型,这可能与您的兴趣相去甚远.

Answer 2

一个好的开始是开发一种算法来：

1) 求内切球的最大半径。

2）然后考虑减去体积

3) 用多面体近似减去体积。

4）将该多面体细分为更小的（更精细的）多面体。

5) 重做步骤1。

可能会有一些变化，但它似乎回答了你的问题。正如您所看到的，误差函数随着球体数量的增加而减小，因此您不能同时最小化两者：这是一种权衡。但是您可以修复一个并尝试优化另一个，例如将误差函数修复为可接受的容差，并最小化执行此操作的球体数量，反之亦然。