Skip to main content

Module geodesics

Module geodesics 

Source
Expand description

Stability: unstable — geodesics API may change before 1.0. 测地线距离(Geodesic Distance)。

实现 Heat Method(Crane, Weischedel, Wardetzky 2013), 通过求解两个稀疏线性系统高效计算网格上从源点出发的测地线距离。

§算法步骤

  1. 时间步 $\tau = h^2$($h$ 为平均边长)
  2. 求解热流:$(I - \tau \Delta) u_\tau = u_0$(初始热源 $u_0$)
  3. 计算归一化梯度:$X = -\nabla u_\tau / |\nabla u_\tau|$
  4. 求解 Poisson:$\Delta \phi = \nabla \cdot X$
  5. $\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
从目标顶点沿测地线距离梯度回溯到源顶点的最短路径。