希望这里有一些计算几何学的人可以帮助我解决以下问题 -
请想象我在 3 空间中取一个自由移动的球，并通过定义一组不可通过的坐标 Sc（即 3 空间中不允许扩散球的任何部分重叠的点）在它周围创建一个“笼子”。这些点位于某个较大球体的体积 V(cage) 内，其中 V(cage) >> V(ball)。
假设一组不可通过的坐标 Sc，是否有一种计算上有效和/或很好的方法来确定球是否可以逃脱笼子？
请参阅我之前在 MathOverflow 上的帖子 - https://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of-无言以对
假设球的半径为R。正如您在 MathOverflow 上的朋友所指出的那样，这个问题相当于用半径为R的球替换不可通行的点，用点P替换球。所以问题是P是否在一个被球密封的房间里。
要回答这个问题，您需要计算球的联合，然后取该联合的曲面S。如果P在S的任何组件内，它将被困住，否则它可以逃脱。
这些是计算球并集的成熟算法，至少可以追溯到EdelsBrunner 的这篇论文。理解和实现该算法有相当长的学习曲线，但幸运的是它是在 CGAL 库中实现的。
CGAL 计算好皮肤后，您可以查看皮肤的连接组件（所有这些组件都应该是封闭的网格）并检查P是否在其中任何一个内（如果您需要帮助，请喊）。
由于镶嵌的蒙皮是实际球体表面的近似值，您可能会问是否存在精度问题。我希望网格面实际上位于原始球内，并假设P最初位于所有球之外，我认为检查P是否在任何皮肤组件内将为您提供准确的结果。