Expand description
Stability: unstable — geodesics API may change before 1.0. 测地线距离(Geodesic Distance)。
实现 Heat Method(Crane, Weischedel, Wardetzky 2013), 通过求解两个稀疏线性系统高效计算网格上从源点出发的测地线距离。
§算法步骤
- 时间步 $\tau = h^2$($h$ 为平均边长)
- 求解热流:$(I - \tau \Delta) u_\tau = u_0$(初始热源 $u_0$)
- 计算归一化梯度:$X = -\nabla u_\tau / |\nabla u_\tau|$
- 求解 Poisson:$\Delta \phi = \nabla \cdot X$
- $\phi$ 即为测地线距离(偏移去除后)
额外提供 shortest_path 沿距离场梯度回溯最短路径。
Functions§
- dijkstra_
geodesic - Dijkstra 单源最短图距离。
- dijkstra_
multi_ source_ geodesic - Dijkstra 多源最短图距离。
- dijkstra_
shortest_ path - Dijkstra 精确最短路径(顶点序列)。
- dijkstra_
with_ parent - Dijkstra 单源最短图距离 + 父节点回溯信息。
- geodesic_
distance_ from_ vertex - Heat Method 热核法测地线距离。
- mmp_
geodesic - MMP 精确测地线距离(单源)。
- mmp_
multi_ source_ geodesic - MMP 精确测地线距离(多源)。
- multi_
source_ geodesic - 多源 Heat Method 测地线距离。
- shortest_
path - 从目标顶点沿测地线距离梯度回溯到源顶点的最短路径。