geodesic

「測地」。形容詞。曲面上的（連續）、網格上的（離散）。

計算幾何的常見主題，都可以推廣成測地版本，諸如測地距離、測地交點、測地凸包、測地三角剖分、測地最近鄰居。

計算學家習慣討論離散版本，也就是網格。

二維測地與三維測地，問題性質截然不同。二維測地：網格內部（或者多邊形內部），癥結在於如何繞過邊界。三維測地：網格表面（或者多面體表面），癥結在於如何穿越鄰面。

近期文獻主要討論二維，鮮少討論三維。

geodesic path / geodesic distance

「測地路徑」與「測地距離」。曲面上的最短路徑與最短距離。

經典範例是「大圓航線」：飛機在地球表面的飛行路線。

二維網格的測地路徑，就是直線，缺乏討論意義。

三維網格的測地路徑，就是網格攤平之後的直線。從各種攤平方式之中，找到最短直線。

儘管攤平方式有指數個，但是測地路徑擁有多項式時間演算法。

1. exact O(nnlogn) 1987      https://code.google.com/archive/p/geodesic/
2. exact O(nn) 2009          https://sites.google.com/site/xinshiqing/knowledge-share
3. diffusion 2013            https://www.cs.cmu.edu/~kmcrane/index.html
4. saddle vertex graph 2013  https://github.com/GeodesicGraph/DGG_and_SVG
5. edge flip 2020            https://nmwsharp.com/research/flip-geodesics/

《A Survey of Algorithms for Geodesic Paths and Distances》

演算法（Mitchell–Mount–Papadimitriou algorithm）

Dijkstra's algorithm。時間複雜度O(N²logN)。

演算法（Xin–Wang algorithm）

時間複雜度O(N²logN)。

《Improving Chen and Han's algorithm on the discrete geodesic problem》

演算法（diffusion）

《Geodesics in heat: A new approach to computing distance based on heat flow》

演算法（saddle vertex graph）

《Saddle Vertex Graph (SVG): A Novel Solution to the Discrete Geodesic Problem》

演算法（edge flipping）

大家習慣調整網格，測地路徑隨之變動。乾脆修改點邊面，把一條普通路徑打造成測地路徑。

《You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges》

2D geodesic nearest neighbor

《Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon》

我尚未找到實用的演算法。

2D geodesic nearest neighbor

查無資料。

2D geodesic convex hull

3D geodesic convex hull

查無資料。

凸的定義不復存在。問題必須區分為面積最小包、周長最短包、……，諸如之類。

2D geodesic Voronoi diagram

《A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram in a Simple Polygon》

我尚未找到實用的演算法。

3D geodesic Voronoi diagram

查無資料。