algorithm - 长方体表面两点间的最短路径

Question

我找不到“蜘蛛与苍蝇问题”(长方体表面两点之间的最短路径)的通用解决方案。每个人都解决了一个特定的案例，但是当两点可以在任何地方时呢？

我的想法是创建一个考虑长方体各种网络的算法，计算 2D 上的最短路径，然后返回最小值，但我不知道该算法生成这些网格(我猜硬编码所有组合不是最好的方式)。

Answer 1

简单方法(仅适用于点在相同或相邻面上的情况)

如下所示将立方体结构展平为 2d...

1. 从包含两个点之一的面开始。如果这还包含另一点，您可以到此为止，解决方案微不足道。
2. 只有 4 张相邻的面孔。如果其中任何一个包含另一个点，您可以将该面与第一个面相邻，并绘制直线。
3. 否则，点在相对的面上。您需要尝试将最终面与 4 个相邻面中的每一个相邻放置，并选择 4 个备选方案中最短的一个。这并不总能提供最佳解决方案，但相距不远，而且成本低廉。

通用方法

吉姆普罗普的 surface distance conjecture是对于中心对称的凸致密体，两点之间的最大表面距离只有通过中心相对的对才能实现。我基于此的猜想是最短距离是大约由两点和 body 中心构成的平面与表面相交的地方。因此，您只需要使用 3d 几何找到该平面与面相交的位置，并在查看可能的路线时使用两个备选方案中较短的一个相交的面。如果平面沿着立方体的边运行(例如，如果点在相对的面上并且都在面的中心和面的角之间，并且这些角由边连接)那么通过两个面的路线应该被考虑，虽然我推测它们将是等效的长度。

这个方案比较通用，同时满足点在同一个面上、相连的面和相对面上的场景。

这种方法的唯一问题是两点之间的线穿过 body 的中心，根据定义，这意味着两点正好彼此相对，因为这意味着 3 个点在一条直线上, 所以没有飞机...