我正在努力寻找有效的算法的3D问题。
我有一个具有给定宽度,高度和深度的边框。我也有一个领域清单。也就是说,每个球体的中心坐标(x i,y i,z i)和半径r i。
保证球体适合边界框,并且彼此之间不重叠。
所以我的情况是这样的:
<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLmltZ3VyLmNvbS9TUjNqVVRNLnBuZyJ9” alt =“边界框内的球体”>
现在我有了一个半径为r的新球体,我必须将其装入边界框内,而不与之前的任何球体重叠。
我也有一个目标点T =(x,y,z),我的目标是(根据上述条件)使这个新球体尽可能接近该目标点。
我正在尝试构建一种有效的算法,以找到新球体的最佳位置。最佳位置:尽可能靠近目标点。如果边界框内任何地方的现有球体之间或周围没有空间适合该新球体,则为“假”结果。
我已经想到了各种复杂的方法,例如对剩余体积进行某种参数化描述,从边界框开始,然后一个个地减去现有球体。但这似乎并没有引导我寻求可行的解决方案。
请注意,有许多已知的“球体填充”算法,但它们往往只是用随机球体填充体积。他们也经常使用试错法,只是进行一定数量的随机尝试然后终止。
尽管我有一个给定的特定新球体尺寸,但我需要将其适应(或发现不可能)。
我正在努力寻找有效的算法的3D问题。我有一个给定的宽度,高度和深度的边框。我也有一个领域清单。也就是说,中心...
[一种可能的方法是通过计算球体的“距离图”,即该函数针对每个点(x,y,z)返回到最接近球体的距离,该距离也是到最接近中心的距离减去相应球体的半径。该图由(超)圆锥形曲面的相交组成。