vtkDijkstraGraphGeodesicPath Class Reference

#include <vtkDijkstraGraphGeodesicPath.h>

Inheritance diagram for vtkDijkstraGraphGeodesicPath:

Inheritance graph
[legend]
Collaboration diagram for vtkDijkstraGraphGeodesicPath:

Collaboration graph
[legend]

List of all members.


Detailed Description

Dijkstra algorithm to compute the graph geodesic.

Takes as input a polygonal mesh and performs a single source shortest path calculation. Dijkstra's algorithm is used. The implementation is similar to the one described in Introduction to Algorithms (Second Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill. Some minor enhancement are added though. All vertices are not pushed on the heap at start, instead a front set is maintained. The heap is implemented as a binary heap. The output of the filter is a set of lines describing the shortest path from StartVertex to EndVertex.

Warning:
The input polydata must have only triangle cells.
Thanks:
The class was contributed by Rasmus Paulsen. www.imm.dtu.dk/~rrp/VTK . Also thanks to Alexandre Gouaillard and Shoaib Ghias for bug fixes and enhancements.

Definition at line 47 of file vtkDijkstraGraphGeodesicPath.h.

typedef vtkGraphGeodesicPath Superclass
static int IsTypeOf (const char *type)
static
vtkDijkstraGraphGeodesicPath
SafeDownCast (vtkObject *o)
virtual const char * GetClassName ()
virtual int IsA (const char *type)
void PrintSelf (ostream &os, vtkIndent indent)

Public Member Functions

virtual double GetGeodesicLength ()
virtual vtkIdListGetIdList ()
virtual vtkFloatArrayGetd ()
virtual void SetStopWhenEndReached (int)
virtual int GetStopWhenEndReached ()
virtual void StopWhenEndReachedOn ()
virtual void StopWhenEndReachedOff ()
virtual void SetUseScalarWeights (int)
virtual int GetUseScalarWeights ()
virtual void UseScalarWeightsOn ()
virtual void UseScalarWeightsOff ()

Static Public Member Functions

static
vtkDijkstraGraphGeodesicPath
New ()

Protected Member Functions

 vtkDijkstraGraphGeodesicPath ()
 ~vtkDijkstraGraphGeodesicPath ()
virtual int RequestData (vtkInformation *, vtkInformationVector **, vtkInformationVector *)
void BuildAdjacency (vtkPolyData *pd)
void DeleteAdjacency ()
double CalculateEdgeCost (vtkPolyData *pd, vtkIdType u, vtkIdType v)
void Initialize ()
void Reset ()
void Heapify (int i)
void HeapInsert (int v)
int HeapExtractMin ()
void HeapDecreaseKey (int v)
void InitSingleSource (int startv)
void ShortestPath (int startv, int endv)
void Relax (int u, int v, double w)
void TraceShortestPath (vtkPolyData *inPd, vtkPolyData *outPd, vtkIdType startv, vtkIdType endv)

Protected Attributes

vtkTimeStamp AdjacencyBuildTime
int NumberOfVertices
vtkFloatArrayd
vtkIntArraypre
vtkIntArrayf
vtkIntArrays
vtkIntArrayHeap
int HeapSize
vtkIntArrayp
vtkIdListIdList
vtkIdList ** Adjacency
int StopWhenEndReached
int UseScalarWeights
int AdjacencyGraphSize

Member Typedef Documentation

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

Definition at line 57 of file vtkDijkstraGraphGeodesicPath.h.


Constructor & Destructor Documentation

vtkDijkstraGraphGeodesicPath::vtkDijkstraGraphGeodesicPath (  )  [protected]

vtkDijkstraGraphGeodesicPath::~vtkDijkstraGraphGeodesicPath (  )  [protected]


Member Function Documentation

static vtkDijkstraGraphGeodesicPath* vtkDijkstraGraphGeodesicPath::New (  )  [static]

Instantiate the class

Reimplemented from vtkPolyDataAlgorithm.

virtual const char* vtkDijkstraGraphGeodesicPath::GetClassName (  )  [virtual]

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

static int vtkDijkstraGraphGeodesicPath::IsTypeOf ( const char *  type  )  [static]

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

virtual int vtkDijkstraGraphGeodesicPath::IsA ( const char *  type  )  [virtual]

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

static vtkDijkstraGraphGeodesicPath* vtkDijkstraGraphGeodesicPath::SafeDownCast ( vtkObject o  )  [static]

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

void vtkDijkstraGraphGeodesicPath::PrintSelf ( ostream &  os,
vtkIndent  indent 
) [virtual]

Standard methids for printing and determining type information.

Reimplemented from vtkGraphGeodesicPath.

virtual vtkIdList* vtkDijkstraGraphGeodesicPath::GetIdList (  )  [virtual]

The vertex ids (of the input polydata) on the shortest path

virtual vtkFloatArray* vtkDijkstraGraphGeodesicPath::Getd (  )  [virtual]

Get the summed weight for all vertices

virtual void vtkDijkstraGraphGeodesicPath::SetStopWhenEndReached ( int   )  [virtual]

Stop when the end vertex is reached or calculate shortest path to all vertices

virtual int vtkDijkstraGraphGeodesicPath::GetStopWhenEndReached (  )  [virtual]

Stop when the end vertex is reached or calculate shortest path to all vertices

virtual void vtkDijkstraGraphGeodesicPath::StopWhenEndReachedOn (  )  [virtual]

Stop when the end vertex is reached or calculate shortest path to all vertices

virtual void vtkDijkstraGraphGeodesicPath::StopWhenEndReachedOff (  )  [virtual]

Stop when the end vertex is reached or calculate shortest path to all vertices

virtual void vtkDijkstraGraphGeodesicPath::SetUseScalarWeights ( int   )  [virtual]

Use scalar values in the edge weight (experimental)

virtual int vtkDijkstraGraphGeodesicPath::GetUseScalarWeights (  )  [virtual]

Use scalar values in the edge weight (experimental)

virtual void vtkDijkstraGraphGeodesicPath::UseScalarWeightsOn (  )  [virtual]

Use scalar values in the edge weight (experimental)

virtual void vtkDijkstraGraphGeodesicPath::UseScalarWeightsOff (  )  [virtual]

Use scalar values in the edge weight (experimental)

virtual double vtkDijkstraGraphGeodesicPath::GetGeodesicLength (  )  [inline, virtual]

TODO: Get the total geodesic length.

Implements vtkGeodesicPath.

Definition at line 87 of file vtkDijkstraGraphGeodesicPath.h.

virtual int vtkDijkstraGraphGeodesicPath::RequestData ( vtkInformation request,
vtkInformationVector **  inputVector,
vtkInformationVector outputVector 
) [protected, virtual]

This is called by the superclass. This is the method you should override.

Reimplemented from vtkPolyDataAlgorithm.

void vtkDijkstraGraphGeodesicPath::BuildAdjacency ( vtkPolyData pd  )  [protected]

void vtkDijkstraGraphGeodesicPath::DeleteAdjacency (  )  [protected]

double vtkDijkstraGraphGeodesicPath::CalculateEdgeCost ( vtkPolyData pd,
vtkIdType  u,
vtkIdType  v 
) [protected]

void vtkDijkstraGraphGeodesicPath::Initialize (  )  [protected]

void vtkDijkstraGraphGeodesicPath::Reset (  )  [protected]

void vtkDijkstraGraphGeodesicPath::Heapify ( int  i  )  [protected]

void vtkDijkstraGraphGeodesicPath::HeapInsert ( int  v  )  [protected]

int vtkDijkstraGraphGeodesicPath::HeapExtractMin (  )  [protected]

void vtkDijkstraGraphGeodesicPath::HeapDecreaseKey ( int  v  )  [protected]

void vtkDijkstraGraphGeodesicPath::InitSingleSource ( int  startv  )  [protected]

void vtkDijkstraGraphGeodesicPath::ShortestPath ( int  startv,
int  endv 
) [protected]

void vtkDijkstraGraphGeodesicPath::Relax ( int  u,
int  v,
double  w 
) [protected]

void vtkDijkstraGraphGeodesicPath::TraceShortestPath ( vtkPolyData inPd,
vtkPolyData outPd,
vtkIdType  startv,
vtkIdType  endv 
) [protected]


Member Data Documentation

Definition at line 101 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 137 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 140 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 143 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 147 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 151 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 154 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 157 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 160 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 163 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 166 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 168 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 170 of file vtkDijkstraGraphGeodesicPath.h.

Definition at line 173 of file vtkDijkstraGraphGeodesicPath.h.


The documentation for this class was generated from the following file:

Generated on Sat Dec 27 13:22:39 2008 for VTK by  doxygen 1.5.6