Shortest routes on varying height surfaces using gray-level distance transforms

The distance transform on curved space (DTOCS) and its locally Euclidean modification weighted DTOCS (WDTOCS) calculate distances along gray-level surfaces. This article presents the Route DTOCS algorithm for finding and visualizing the shortest route between two points on a gray-level height map, and also introduces new distance definitions producing more accurate global distances. The algorithm is very simple to implement, and finds all optimal paths between the two points at once. The Route DTOCS is an efficient 2D approach to finding routes on a 3D surface. It also provides a more flexible solution to obstacle avoidance problems than the constrained distance transform.