vtkDijkstraGraphGeodesicPath Class Reference

#include <vtkDijkstraGraphGeodesicPath.h>

Inheritance diagram for vtkDijkstraGraphGeodesicPath:

[legend]

Collaboration diagram for vtkDijkstraGraphGeodesicPath:

[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 vtkIdList *	GetIdList ()

virtual vtkFloatArray *	Getd ()

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
vtkFloatArray *	d
vtkIntArray *	pre
vtkIntArray *	f
vtkIntArray *	s
vtkIntArray *	Heap
int	HeapSize
vtkIntArray *	p
vtkIdList *	IdList
vtkIdList **	Adjacency
int	StopWhenEndReached
int	UseScalarWeights
int	AdjacencyGraphSize

Member Typedef Documentation

typedef vtkGraphGeodesicPath vtkDijkstraGraphGeodesicPath::Superclass

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]`