在半边DS中逼近大地测量，我如何改进我的网格以获得良好的逼近
我在任意网格上实现了吉卜斯特的最短路径算法来逼近大地测量。贾克斯特拉的作品，但我注意到一个固有的问题，我的网格离散化。
请考虑以下数字顺序：
..。
这是我目前的求精算法，它是最简单的/标准的人脸细分。现在考虑一个测地线在两点上的近似：
蓝色点是我认为实际测地线与边缘相交的地方，离近似测地线穿过的地方很远。然而，这条道路并没有错。
以正方形网格为例。网格中任意两个点之间的距离是曼哈顿距离，x，+，x，x，y，y。
因此，就贾克斯特拉的情况而言，一条一直往下再到左边的路径，其长度与一条在楼梯模式中对角的路径是相同的。细化网格也不会改变距离。换句话说，在正方形网格中，当方格的大小为0时，Djikstra发现的最短路径的极限不是连接两个点的斜线。
现在，实际的问题是，有人知道如何细分我的表面，这是相当简单的，但实际上会收敛到测地线？
回答 1
Computer Graphics用户
发布于 2020-07-21 15:50:25
正如您所指出的，这里的问题是网格的离散/细分。如果你的网格是由四边形而不是三角形组成的，那么最明显的细分策略就是将每个四字文字分成四个同样大小的较小的四边形：
对于任意两点P_1和P_2，Dijkstra的算法将在这些点P_1和P_2之间产生最短路径集。使用这种细分策略细化离散化越多，在这两个点之间找到的路径就越短。然而，直觉上很明显，对于每个细分级别的l\in\mathbb{N}，您可以选择其中一条最短路径p_l，这样序列(p_l)_{l\in\mathbb{N}}就可以收敛到P_1和P_2之间的实际测地线(对于必须指定的某种范数，例如上确界范数)。
不幸的是，对于标准的细分策略--将一个三角形分割成四个较小的三角形--情况并非如此，这一点在您的示例中得到了证明。我相信，在它的核心，问题是，没有办法到达三角形的中心与直线从它的每一个边缘。这可以通过将每个细分步骤中的一个三角形分成6个较小的三角形来实现，如下所示：
我没有证据证明这种细分对于用Dijkstra的算法计算测地线更有用，但在我看来这是很有可能的。我很想看看你的结果和这个细分策略是什么样子的！然而，无论你做什么，最终你可能会或不可能得到一组最短的路径，而不是一条最短的路径。在这种情况下，您将需要某种启发式或附加的算法来决定哪条路径最接近于真实的测地线。
https://computergraphics.stackexchange.com/questions/10046
复制相似问题
腾讯云开发者
