我试图用“粒子”(由3D XYZ矢量表示)最佳地填充3D球形体积,这些粒子需要彼此保持特定的距离,同时试图最小化它们之间存在的自由空间量。
虽然有一个问题 - 粒子本身可能落在球形体积的边界上 - 它们不能存在于球体体外。理想情况下,我想最大化落在这个边界上的粒子数量(这让我觉得这是一种球形填充问题),然后向内填充剩余的体积。
有没有哪种算法可以解决这类问题?它不需要精确,但关键在于最终解决方案的密度需要相当准确(“完美”解决方案的+/- ~5%)。
你的约束有点模糊,很难说肯定,但我会尝试现场方法。首先看:
和子链接,您可以在其中找到此方法的一些示例。
现在的算法:
N
粒子随机放入球体内
N
应该安全地低,因此它比溶液颗粒数小。max(|particles_velocity|)<threshold
停止。N+1
粒子从#1重试。如果没有停止并使用最后正确的解决方案
为了加快速度,您可以添加更多粒子而不是使用(N+1)
,类似于二分搜索(添加32个粒子直到你可以...然后只有16 ......)。此外,您不需要在#1中使用随机位置进行其他运行。您可以让其他粒子开始放置在最后运行解决方案中的位置。如何确定解决方案的准确性是完全不同的事情。由于您没有提供确切的规则,我们只能猜测。我会尝试估算理想的粒子密度,并根据球体积计算理想的粒子数。您也可以将此用于N
的初始猜测,然后与最终的N
进行比较。