多面体表面の正確な測地線と最短経路

凸型および非凸多面体表面に沿って距離を計算するための2つのアルゴリズムを提示します。最初のアルゴリズムは、正確な最小地形距離を計算し、2番目のアルゴリズムはこれらの距離を組み合わせて、表面に沿って正確な最短パス距離を計算します。両方のアルゴリズムが拡張されており、正確な最小地形パスと最短パスを計算しています。これらのアルゴリズムは、精度を検証し、各アルゴリズムの立方体以下のランタイムパフォーマンスを測定するために、正しいソリューションが既知の表面に実装および検証されています。これらのアルゴリズムによって実行される正確な距離計算は、何万もの頂点を含む大規模な表面で実行可能であり、湾曲した多様体を平らな表現に正確に変換する近似表面平坦化方法の必要なコンポーネントです。

We present two algorithms for computing distances along convex and non-convex polyhedral surfaces. The first algorithm computes exact minimal-geodesic distances and the second algorithm combines these distances to compute exact shortest-path distances along the surface. Both algorithms have been extended to compute the exact minimal-geodesic paths and shortest paths. These algorithms have been implemented and validated on surfaces for which the correct solutions are known, in order to verify the accuracy and to measure the run-time performance, which is cubic or less for each algorithm. The exact-distance computations carried out by these algorithms are feasible for large-scale surfaces containing tens of thousands of vertices, and are a necessary component of near-isometric surface flattening methods that accurately transform curved manifolds into flat representations.