Research > Software > GeodesicPath

GeodesicPath

GeodesicPath is an application that finds the shortest path between two vertices on a surface. Two types of shortest paths the application can find are the Dijkstra path and the Geodesic path.

Features

  • <p>The user may specify one of two types of shortest paths to use, either Dijkstra or geodesic.</p>
  • <p>At present, the following surface formats are supported: OFF, Duff, LONI Ucf grid and TM, DX triangulated surface, Minc OBJ, CCB CCBBM.</p>

Description

GeodesicPath is an application that finds the shortest path between two vertices on a surface. There are two types of shortest paths that can be computed.

Usage

System Requirements

  • OS: any
  • Processor: any
  • Memory: Data-dependent
  • Other: Java 1.5 (or higher) runtime environment

Installation

Compliation

Portable java executable make compilation unnecessary.

Installation InstructionsCopy java executable 'jar' file to local disk.

Purpose

GeodesicPath takes a shape and two vertex indices as arguments and produces a contour that encodes the path between the specified vertices. There are several options for the programs output.

There are two types of shortest paths the application can find. The simpler one is the Dijkstra path, which is constrainted to lie on either the vertices or the edges of the shape. Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weightsThis path is dependent on the shape's parameterization. If the shape is sparsely sampled, then the Dijkstra path may not be the shortest possible path. The alternative path is the true geodesic path to the surface. This path is constrained to lie on the faces of the surface. This path is independent of the shape's parameterization. The geodesic path is computed in an iterative fashion, where the Dijkstra path is the initial path, and segments are added and changed to minimize the length of the path. This means that the geodesic will be a local minimum geodesic.

In general, the Dijkstra method is very fast and usually a very good approximation to the true geodesic. The geodesic method will give a local shortest path, but it's convergence rate depends heavily on the shape's geometry and the starting Dijkstra path.