多面体放置优化

Question

3

我希望将一个多面体（对象）放入另一个多面体（容器）中。两个多面体都是凸的，由一组点和三角形定义。容器大小固定。对象可以缩放，并严格位于容器内。我希望计算出使对象最大的位置和方向。近似和高效的解决方案也可行。

有什么建议吗？非常感谢。

- ArthurQian

一个令人害怕的问题。多面体可以非常复杂吗？ - user1196549

它们都是凸多边形，且顶点不超过一百个。 - ArthurQian

很有趣的是，如果最优解始终满足几何限制，比如内部多面体的一个面与外部多面体的一个面平行，那么这将大大减少搜索空间。不幸的是，这超出了我的能力范围。 - user1196549

2个回答

1

如果时间允许，另一个建议：

对于外部多面体的固定姿态，内部多面体的姿态由围绕任意中心的3个平移和3个旋转参数（如欧拉角）定义。

当这些参数固定时，从中心通过内部顶点投射射线直到击中外部多面体，可以得到允许的缩放因子。

现在，问题被重新制定为6个变量函数的最大化问题，可能会出现局部最大值。这可以通过Hooke＆Jeeves步骤、上山下山法（Nelder-Mead）和/或模拟退火来解决。

我不建议从我的其他答案中找到解决方案并保持接近它，因为您可能会陷入局部最大值。

- user1196549

非常感谢您的建议。我会尝试使用建议的方法设计算法。 - ArthurQian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

基于椭球体的快速且次优解建议：

对于两个顶点集，以重心为中心并通过计算惯性等效椭球来归一化坐标，从而得到更各向同性的集合。

对于外部集合，找到面和原点之间的最短距离；对于内部集合，找到距离一个顶点最远的距离。这给你两个球，一个是封闭的，一个是包围的。

现在将封闭的球体变换到包围球的坐标系中，得到一个椭球体：椭球体的长轴告诉你可以膨胀多少才能适应球体。

如果多面体倾斜，则此近似可能很差。

您可以通过从内部多面体的中心绘制射线穿过所有顶点，并击中外部多面体，可能会给您提供额外的增长因子，稍微改善此解决方案。