曲面上两点之间的最短距离
Shortest distance between two point on surface
我正在写我的学士论文（关于计算机科学），现在我遇到了关于在流形的 3D 三角网格上找到两点之间的最短路径的问题。我已经读过 MMP，但是它计算给定点和网格上的顶点 $x$ 之间的距离函数 $d(x)$。
我知道我正在解决的问题名为测地线，但我真正找不到的是一些使用 A* 寻找两个给定顶点上两个给定点之间的最短路径的好算法。
I 'invented' 也是一种算法，它通过使用欧几里得距离启发式算法和在任何边上找到新点后进行校正来使用 A*。
我也有保存在半边结构中的边。
所以我的主要想法是：
- 我们将通过 A* 算法找到最近的边缘，并使用最小化函数 $f(x) + g(x)$ 找到该边缘点，其中 $f$ 是我们当前的距离，$g$ 是启发式（euclidean距离)
- 每次找到新边，我们都会展开当前网格并找到离起点最近的路径
那么现在我的问题是：
- 你知道一些讨论这个问题的研究论文吗？？
- 为什么没有人写关于使用 A* 的算法？？
- 你对我提出的算法有什么看法？
我不是这方面的专家，所以带着偏见阅读。也很抱歉，这更多的是评论而不是答案...
首先你应该澄清一些事情：
- 网格是凸的还是凹的？
- 路径是始终在表面上还是可以在外侧（如果是凹面）但从不在内侧的面之间飞行？
- start/end 点是在面的边缘还是在里面？
假设凹面，边缘上的点和只有表面路径...
我认为 graph A* 方法不可用，因为点和同一面的任何边缘之间存在无限可能的路径，那么您如何测试所有这些路径？
如果你真的想要 A* 那么你可以做类似于 raster A*
因此将所有边缘重新采样到更多点
所以要么 n 点，要么使用一些密度，例如每个平均边长 10 个点或一些细节尺寸。
在重采样点上使用图 A*（不再将它们作为边处理）
然而，这只会产生接近最短路径的结果，因此为了提高精度，您应该以越来越高的密度递归地对使用点附近的边缘进行重新采样，直到重新采样点之间的距离小于精度。
另一种选择是使用类似于 CCD（循环坐标下降）的方法，因此：
- 创建通过 2 个点和网格中心的平面
- 创建穿过两个点之间所有平面和面的交点的路径（使用两个选项中较短的一个）
- 反复前后移动交叉点并使用贪心法得到结果
但是这可能会陷入局部最小值...您可以改用 但是随着面数的增加这些速度会变得非常慢
我觉得你也可以使用 RANSAC ...
从我的角度来看，我认为第一种 A* 方法是最有前途的，你只需要每条边的点链表和每个点的成本计数器，你甚至可以简单地编码递归改进的准确性。它甚至可以完成 in-place 所以在递归中不需要重新分配......而且算法并不复杂所以你应该没有问题实现它，并且保证结果不是其他方法的情况我提...另一个优点是即使start/end点不属于边也可以使用...
这里有一些与在表面网格上寻找测地线（或近似值）相关的论文和工具：
A Survey of Algorithms for Geodesic Paths and Distances
You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges (code)
The Vector Heat Method
(code)
您可以在调查论文中找到更多论文。
我很久以前就实现了你提到的算法 (MMP)，但由于沿边的拆分数量增长得非常快，所以很难正确实现它并且非常耗时。
我正在写我的学士论文（关于计算机科学），现在我遇到了关于在流形的 3D 三角网格上找到两点之间的最短路径的问题。我已经读过 MMP，但是它计算给定点和网格上的顶点 $x$ 之间的距离函数 $d(x)$。
我知道我正在解决的问题名为测地线，但我真正找不到的是一些使用 A* 寻找两个给定顶点上两个给定点之间的最短路径的好算法。
I 'invented' 也是一种算法，它通过使用欧几里得距离启发式算法和在任何边上找到新点后进行校正来使用 A*。 我也有保存在半边结构中的边。
所以我的主要想法是：
- 我们将通过 A* 算法找到最近的边缘，并使用最小化函数 $f(x) + g(x)$ 找到该边缘点，其中 $f$ 是我们当前的距离，$g$ 是启发式（euclidean距离)
- 每次找到新边，我们都会展开当前网格并找到离起点最近的路径
那么现在我的问题是：
- 你知道一些讨论这个问题的研究论文吗？？
- 为什么没有人写关于使用 A* 的算法？？
- 你对我提出的算法有什么看法？
我不是这方面的专家，所以带着偏见阅读。也很抱歉，这更多的是评论而不是答案...
首先你应该澄清一些事情：
- 网格是凸的还是凹的？
- 路径是始终在表面上还是可以在外侧（如果是凹面）但从不在内侧的面之间飞行？
- start/end 点是在面的边缘还是在里面？
假设凹面，边缘上的点和只有表面路径...
我认为 graph A* 方法不可用，因为点和同一面的任何边缘之间存在无限可能的路径，那么您如何测试所有这些路径？
如果你真的想要 A* 那么你可以做类似于 raster A*
因此将所有边缘重新采样到更多点
所以要么
n点，要么使用一些密度，例如每个平均边长 10 个点或一些细节尺寸。在重采样点上使用图 A*（不再将它们作为边处理）
然而，这只会产生接近最短路径的结果，因此为了提高精度，您应该以越来越高的密度递归地对使用点附近的边缘进行重新采样，直到重新采样点之间的距离小于精度。
另一种选择是使用类似于 CCD（循环坐标下降）的方法，因此：
- 创建通过 2 个点和网格中心的平面
- 创建穿过两个点之间所有平面和面的交点的路径（使用两个选项中较短的一个）
- 反复前后移动交叉点并使用贪心法得到结果
但是这可能会陷入局部最小值...您可以改用
我觉得你也可以使用 RANSAC ...
从我的角度来看，我认为第一种 A* 方法是最有前途的，你只需要每条边的点链表和每个点的成本计数器，你甚至可以简单地编码递归改进的准确性。它甚至可以完成 in-place 所以在递归中不需要重新分配......而且算法并不复杂所以你应该没有问题实现它，并且保证结果不是其他方法的情况我提...另一个优点是即使start/end点不属于边也可以使用...
这里有一些与在表面网格上寻找测地线（或近似值）相关的论文和工具：
A Survey of Algorithms for Geodesic Paths and Distances
You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges (code)
The Vector Heat Method
(code)
您可以在调查论文中找到更多论文。
我很久以前就实现了你提到的算法 (MMP)，但由于沿边的拆分数量增长得非常快，所以很难正确实现它并且非常耗时。