算法来计算两个点之间的最短路径的三维的表面上啮合

Question

我寻找算法来计算如下：

我有：

1. 的三维三角形网格。三角形不一定在一个平面上。两个相邻三角形的范数向量之间的角度小于90度。

2. 两点。这两点位于三角形网格的边缘或网格的三角形内。

我需要计算代表网格上两点之间最短路径的折线。

要做到这一点，最简单和/或最有效的策略是什么？

Answer 1

就目前而言，您的问题没有明确定义;取决于用于将线段“投影”到网格上的方向，可以有许多解决方案。

一旦你选择了投影的方向，将网格平铺到垂直于投影方向的平面上。此时，您的网格是2d边（线段）的集合;只需确定每条边与目标线段的交点（如果有）即可。

---

编辑：

更新的问题是现在很好的定义。由于我对上述原始问题的回答已被标记为已接受，可能这意味着以下评论中提供的信息实际上是正在被“接受”的更新问题。我来总结一下：

• 谷歌搜索“的三维网格最短距离”的变成了一些相关的信息，如Shortest Path Approximation on Triangulated Meshes
• 此外，见：https://stackoverflow.com/a/10389377/294949 - danh