#include <mitkPointLocator.h>

Collaboration diagram for mitk::PointLocator:

Public Types
typedef PointLocator	Self
typedef Object	Superclass
typedef itk::SmartPointer< Self >	Pointer
typedef itk::SmartPointer < const Self >	ConstPointer
typedef int	IdType
typedef float	DistanceType
typedef float	PixelType
typedef double	CoordRepType
typedef itk::DefaultStaticMeshTraits < PixelType, 3, 2, CoordRepType, CoordRepType, PixelType >	MeshTraits
typedef itk::PointSet < PixelType, 3, MeshTraits >	ITKPointSet
Public Member Functions
virtual const char *	GetClassName () const
void	SetPoints (vtkPointSet *points)
void	SetPoints (mitk::PointSet *points)
void	SetPoints (ITKPointSet *pointSet)
IdType	FindClosestPoint (const vtkFloatingPointType point[3])
IdType	FindClosestPoint (vtkFloatingPointType x, vtkFloatingPointType y, vtkFloatingPointType z)
IdType	FindClosestPoint (mitk::PointSet::PointType point)
DistanceType	GetMinimalDistance (mitk::PointSet::PointType point)
bool	FindClosestPointAndDistance (mitk::PointSet::PointType point, IdType id, DistanceType dist)
Static Public Member Functions
static Pointer	New ()
Protected Types
typedef std::vector< IdType >	IdVectorType
typedef float *	MyANNpoint
typedef int	MyANNidx
typedef float	MyANNdist
typedef MyANNpoint *	MyANNpointArray
typedef MyANNidx *	MyANNidxArray
typedef MyANNdist *	MyANNdistArray
Protected Member Functions
	PointLocator ()
	~PointLocator ()
void	InitANN ()
void	DestroyANN ()
IdType	FindClosestPoint (const MyANNpoint &point)
DistanceType	GetMinimalDistance (const MyANNpoint &point)
Protected Attributes
bool	m_SearchTreeInitialized
IdVectorType	m_IndexToPointIdContainer
vtkPoints *	m_VtkPoints
mitk::PointSet *	m_MitkPoints
ITKPointSet *	m_ItkPoints
unsigned int	m_ANNK
unsigned int	m_ANNDimension
double	m_ANNEpsilon
MyANNpointArray	m_ANNDataPoints
MyANNpoint	m_ANNQueryPoint
MyANNidxArray	m_ANNPointIndexes
MyANNdistArray	m_ANNDistances
ANNkd_tree *	m_ANNTree

Detailed Description

Convenience wrapper around ANN to provide fast nearest neighbour searches. Usage: set your points via SetPoints( vtkPointSet* Points ) or SetPoints(mitk::PointSet*). Then, you may query the closest point to an arbitrary coordinate by FindClosestPoint(). There is no further call to update etc. needed. Currently only calls for 1 nearest neighbour are supported. Feel free to add functions for K nearest neighbours. NOTE: At least 1 point must be contained in the point set.

Definition at line 46 of file mitkPointLocator.h.

Member Typedef Documentation

typedef itk::SmartPointer<const Self> mitk::PointLocator::ConstPointer

Definition at line 50 of file mitkPointLocator.h.

typedef double mitk::PointLocator::CoordRepType

Definition at line 58 of file mitkPointLocator.h.

typedef float mitk::PointLocator::DistanceType

Definition at line 55 of file mitkPointLocator.h.

typedef int mitk::PointLocator::IdType

Definition at line 52 of file mitkPointLocator.h.

typedef std::vector<IdType> mitk::PointLocator::IdVectorType [protected]

Definition at line 146 of file mitkPointLocator.h.

typedef itk::PointSet<PixelType, 3, MeshTraits> mitk::PointLocator::ITKPointSet

Definition at line 61 of file mitkPointLocator.h.

typedef itk::DefaultStaticMeshTraits<PixelType, 3, 2, CoordRepType, CoordRepType, PixelType> mitk::PointLocator::MeshTraits

Definition at line 60 of file mitkPointLocator.h.

typedef float mitk::PointLocator::MyANNdist [protected]

Definition at line 156 of file mitkPointLocator.h.

typedef MyANNdist* mitk::PointLocator::MyANNdistArray [protected]

Definition at line 159 of file mitkPointLocator.h.

typedef int mitk::PointLocator::MyANNidx [protected]

Definition at line 155 of file mitkPointLocator.h.

typedef MyANNidx* mitk::PointLocator::MyANNidxArray [protected]

Definition at line 158 of file mitkPointLocator.h.

typedef float* mitk::PointLocator::MyANNpoint [protected]

Definition at line 154 of file mitkPointLocator.h.

typedef MyANNpoint* mitk::PointLocator::MyANNpointArray [protected]

Definition at line 157 of file mitkPointLocator.h.

typedef float mitk::PointLocator::PixelType

Definition at line 57 of file mitkPointLocator.h.

typedef itk::SmartPointer<Self> mitk::PointLocator::Pointer

Definition at line 50 of file mitkPointLocator.h.

typedef PointLocator mitk::PointLocator::Self

Definition at line 50 of file mitkPointLocator.h.

typedef Object mitk::PointLocator::Superclass

Definition at line 50 of file mitkPointLocator.h.

Constructor & Destructor Documentation

mitk::PointLocator::PointLocator ( ) [protected]

constructor

Definition at line 23 of file mitkPointLocator.cpp.

                               :
  m_SearchTreeInitialized(false),
  m_VtkPoints(NULL), m_MitkPoints(NULL),
  m_ItkPoints(NULL),
  m_ANNK(1), m_ANNDimension(3),
  m_ANNEpsilon(0), m_ANNDataPoints(NULL),
  m_ANNQueryPoint(NULL), m_ANNPointIndexes(NULL),
  m_ANNDistances(NULL), m_ANNTree(NULL)
{

}

mitk::PointLocator::~PointLocator ( ) [protected]

destructor

Definition at line 37 of file mitkPointLocator.cpp.

{
  if ( m_SearchTreeInitialized )
    DestroyANN();
}

Member Function Documentation

void mitk::PointLocator::DestroyANN ( ) [protected]

releases all memory occupied by the ann search tree and internal point set arrays

Definition at line 233 of file mitkPointLocator.cpp.

References annDeallocPt(), and annDeallocPts().

{
  m_SearchTreeInitialized = false;
  if ( m_ANNQueryPoint != NULL )
    annDeallocPt( m_ANNQueryPoint );
  if ( m_ANNDataPoints != NULL )
    annDeallocPts( m_ANNDataPoints );
  if ( m_ANNPointIndexes != NULL )
    delete[] m_ANNPointIndexes;
  if ( m_ANNDistances != NULL )
    delete[] m_ANNDistances;
  if ( m_ANNTree != NULL )
    delete m_ANNTree;
}

mitk::PointLocator::IdType mitk::PointLocator::FindClosestPoint ( mitk::PointSet::PointType point )

Finds the nearest neighbour in the point set previously defined by SetPoints(). The Id of the point is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the nearest neighbour will be determined

Returns:: the id of the nearest neighbour of the given point. The id corresponds to the id which is given in the original point set.

Definition at line 185 of file mitkPointLocator.cpp.

{
  m_ANNQueryPoint[0] = point[0];
  m_ANNQueryPoint[1] = point[1];
  m_ANNQueryPoint[2] = point[2];
  return FindClosestPoint( m_ANNQueryPoint );
}

IdType mitk::PointLocator::FindClosestPoint ( const MyANNpoint & point ) [protected]

Finds the nearest neighbour in the point set previously defined by SetPoints(). The Id of the point is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the nearest neighbour will be determined

Returns:: the id of the nearest neighbour of the given point. The id corresponds to the id which is given in the original point set.

mitk::PointLocator::IdType mitk::PointLocator::FindClosestPoint ( const vtkFloatingPointType point[3] )

Finds the nearest neighbour in the point set previously defined by SetPoints(). The Id of the point is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the nearest neighbour will be determined

Returns:: the id of the nearest neighbour of the given point. The id corresponds to the id which is given in the original point set.

Definition at line 165 of file mitkPointLocator.cpp.

{
  m_ANNQueryPoint[0] = point[0];
  m_ANNQueryPoint[1] = point[1];
  m_ANNQueryPoint[2] = point[2];
  return FindClosestPoint( m_ANNQueryPoint );
}

mitk::PointLocator::IdType mitk::PointLocator::FindClosestPoint	(	vtkFloatingPointType	x,
		vtkFloatingPointType	y,
		vtkFloatingPointType	z
	)

Finds the nearest neighbour in the point set previously defined by SetPoints(). The Id of the point is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

x	the x coordinated of the query point, for whom the nearest neighbour will be determined
y	the x coordinated of the query point, for whom the nearest neighbour will be determined
z	the x coordinated of the query point, for whom the nearest neighbour will be determined

Returns:: the id of the nearest neighbour of the given point. The id corresponds to the id which is given in the original point set.

Definition at line 175 of file mitkPointLocator.cpp.

{
  m_ANNQueryPoint[0] = x;
  m_ANNQueryPoint[1] = y;
  m_ANNQueryPoint[2] = z;
  return FindClosestPoint( m_ANNQueryPoint );
}

bool mitk::PointLocator::FindClosestPointAndDistance	(	mitk::PointSet::PointType	point,
		IdType *	id,
		DistanceType *	dist
	)

Finds the nearest neighbour in the point set previously defined by SetPoints(). The Index and minimal distance between this point and the closest point of the point set is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the minimal distance will be determined

Returns:: the index of and distance (in world coordinates) between the nearest point in point set and the given point

Definition at line 248 of file mitkPointLocator.cpp.

{
  m_ANNQueryPoint[0] = point[0];
  m_ANNQueryPoint[1] = point[1];
  m_ANNQueryPoint[2] = point[2];

  m_ANNTree->annkSearch( m_ANNQueryPoint, m_ANNK, m_ANNPointIndexes, m_ANNDistances);

  *id = m_IndexToPointIdContainer[m_ANNPointIndexes[0]];
  *dist = m_ANNDistances[0];
  return true;
}

virtual const char* mitk::PointLocator::GetClassName ( ) const [virtual]

mitk::PointLocator::DistanceType mitk::PointLocator::GetMinimalDistance ( mitk::PointSet::PointType point )

Finds the nearest neighbour in the point set previously defined by SetPoints(). The minimal distance between this point and the closest point of the point set is returned. Please note, that there is no case, in which no point is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the minimal distance will be determined

Returns:: the distance in world coordinates between the nearest point in point set and the given point

Definition at line 201 of file mitkPointLocator.cpp.

{
  m_ANNQueryPoint[0] = point[0];
  m_ANNQueryPoint[1] = point[1];
  m_ANNQueryPoint[2] = point[2];
  return GetMinimalDistance( m_ANNQueryPoint );
}

DistanceType mitk::PointLocator::GetMinimalDistance ( const MyANNpoint & point ) [protected]

Finds the minimal distance between the given point and a point in the previously defined point set. The distance is returned. Please note, that there is no case, in which no distance is found, since as a precondition at least one point has to be contained in the point set.

Parameters:

point the query point, for whom the minimal distance to a point in the previously defined point set will be determined

Returns:: the distance in world coordinates between the given point and the nearest neighbour.

void mitk::PointLocator::InitANN ( ) [protected]

Initializes the ann search tree using previously defined points

Definition at line 218 of file mitkPointLocator.cpp.

References annAllocPt().

{
  if ( m_SearchTreeInitialized )
    DestroyANN();
  
  m_ANNQueryPoint = annAllocPt( m_ANNDimension );
  m_ANNPointIndexes = new ANNidx[m_ANNK];
  m_ANNDistances = new ANNdist[m_ANNK];
  m_ANNTree = new ANNkd_tree( m_ANNDataPoints, m_IndexToPointIdContainer.size(), m_ANNDimension );
  
  m_SearchTreeInitialized = true;
}

static Pointer mitk::PointLocator::New ( ) [static]

Referenced by mitkPointLocatorTest(), and mitk::SurfaceInteractor::SurfaceInteractor().

void mitk::PointLocator::SetPoints ( ITKPointSet * pointSet )

Sets the point which will be used for nearest-neighbour searches. Note there must be at least one point in the point set.

Parameters:

points the point set containing points for nearest neighbours searches.

Definition at line 123 of file mitkPointLocator.cpp.

References annAllocPts().

{
  if ( pointSet == NULL )
  {
    itkWarningMacro("Points are NULL!");  
    return;
  }

  if(m_ItkPoints)
  {
    if ( (m_ItkPoints == pointSet) && (m_ItkPoints->GetMTime() == pointSet->GetMTime()) )
    {
      return; //no need to recalculate search tree
    }
  }
  m_ItkPoints = pointSet;

  size_t size = pointSet->GetNumberOfPoints();
  if ( m_ANNDataPoints != NULL )
    delete[] m_ANNDataPoints;
  m_ANNDataPoints = annAllocPts( size, m_ANNDimension );
  m_IndexToPointIdContainer.clear();
  m_IndexToPointIdContainer.resize( size );
  size_t counter = 0;
  ITKPointSet::PointsContainerConstPointer pointsContainer = pointSet->GetPoints();
  ITKPointSet::PointsContainer::ConstIterator it;    
  ITKPointSet::PointType currentPoint;
  ITKPointSet::PointsContainer::ElementIdentifier currentId;
  for( it = pointsContainer->Begin(); it != pointsContainer->End(); ++it, ++counter )
  {
    currentPoint = it->Value();
    currentId = it->Index();
    (m_ANNDataPoints[counter])[0] = currentPoint[0];
    (m_ANNDataPoints[counter])[1] = currentPoint[1];
    (m_ANNDataPoints[counter])[2] = currentPoint[2];
    m_IndexToPointIdContainer[counter] = currentId;
  }
  InitANN();
}

void mitk::PointLocator::SetPoints ( vtkPointSet * points )

Sets the point which will be used for nearest-neighbour searches. Note there must be at least one point in the point set.

Parameters:

points the point set containing points for nearest neighbours searches.

Definition at line 45 of file mitkPointLocator.cpp.

References annAllocPts().

{
  if ( pointSet == NULL )
  {
     itkWarningMacro("Points are NULL!");  
     return;
  }
  vtkPoints* points = pointSet->GetPoints();

  if(m_VtkPoints)
  {
    if ( (m_VtkPoints == points) && (m_VtkPoints->GetMTime() == points->GetMTime()) )
    {
      return; //no need to recalculate search tree
    }
  }
  m_VtkPoints = points;

  size_t size = points->GetNumberOfPoints();
  if ( m_ANNDataPoints != NULL )
    delete[] m_ANNDataPoints;
  m_ANNDataPoints = annAllocPts( size, m_ANNDimension );
  m_IndexToPointIdContainer.clear();
  m_IndexToPointIdContainer.resize( size );
  for( vtkIdType i = 0; (unsigned)i < size; ++i )
  {
    vtkFloatingPointType* currentPoint = points->GetPoint( i );
    (m_ANNDataPoints[i])[0] = currentPoint[0];
    (m_ANNDataPoints[i])[1] = currentPoint[1];
    (m_ANNDataPoints[i])[2] = currentPoint[2];
    m_IndexToPointIdContainer[i] = i;
  }
  InitANN();
}

void mitk::PointLocator::SetPoints ( mitk::PointSet * points )

Sets the point which will be used for nearest-neighbour searches. Note there must be at least one point in the point set.

Parameters:

points the point set containing points for nearest neighbours searches.

Definition at line 82 of file mitkPointLocator.cpp.

References annAllocPts(), mitk::BaseData::GetMTime(), mitk::PointSet::GetPointSet(), and mitk::PointSet::GetSize().

{
  if ( points == NULL )
  {
     itkWarningMacro("Points are NULL!");  
     return;
  }

  if(m_MitkPoints)
  {
    if ( (m_MitkPoints == points) && (m_MitkPoints->GetMTime() == points->GetMTime()) )
    {
      return; //no need to recalculate search tree
    }
  }
  m_MitkPoints = points;

  size_t size = points->GetSize();
  if ( m_ANNDataPoints != NULL )
    delete[] m_ANNDataPoints;
  m_ANNDataPoints = annAllocPts( size, m_ANNDimension );
  m_IndexToPointIdContainer.clear();
  m_IndexToPointIdContainer.resize( size );
  size_t counter = 0;
  mitk::PointSet::PointsContainer* pointsContainer = points->GetPointSet()->GetPoints();
  mitk::PointSet::PointsContainer::Iterator it;    
  mitk::PointSet::PointType currentPoint;
  mitk::PointSet::PointsContainer::ElementIdentifier currentId;
  for( it = pointsContainer->Begin(); it != pointsContainer->End(); ++it, ++counter )
  {
    currentPoint = it->Value();
    currentId = it->Index();
    (m_ANNDataPoints[counter])[0] = currentPoint[0];
    (m_ANNDataPoints[counter])[1] = currentPoint[1];
    (m_ANNDataPoints[counter])[2] = currentPoint[2];
    m_IndexToPointIdContainer[counter] = currentId;
  }
  InitANN();
}