diff --git a/Modules/MitkExt/Algorithms/mitkPointLocator.h b/Modules/MitkExt/Algorithms/mitkPointLocator.h index 2ca4d6c368..205b5a602e 100644 --- a/Modules/MitkExt/Algorithms/mitkPointLocator.h +++ b/Modules/MitkExt/Algorithms/mitkPointLocator.h @@ -1,226 +1,226 @@ /*========================================================================= Program: Medical Imaging & Interaction Toolkit Language: C++ Date: $Date$ Version: $Revision$ Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. See MITKCopyright.txt or http://www.mitk.org/copyright.html for details. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the above copyright notices for more information. =========================================================================*/ #ifndef _MITK_POINT_LOCATOR__H__ #define _MITK_POINT_LOCATOR__H__ #include #include "MitkExtExports.h" #include "mitkPointSet.h" #include //forward declarations class vtkPointSet; class ANNkd_tree; namespace mitk { /** * 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. */ class MitkExt_EXPORT PointLocator : public itk::Object { public: mitkClassMacro( PointLocator, Object ); itkNewMacro( Self ); typedef int IdType; typedef float DistanceType; typedef float PixelType; typedef double CoordRepType; typedef itk::DefaultStaticMeshTraits MeshTraits; typedef itk::PointSet ITKPointSet; /** * Sets the point which will be used for nearest-neighbour searches. Note * there must be at least one point in the point set. * @param points the point set containing points for nearest neighbours searches. */ void 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. * @param points the point set containing points for nearest neighbours searches. */ void 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. * @param points the point set containing points for nearest neighbours searches. */ void SetPoints( ITKPointSet* pointSet ); /** * 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. * @param 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. */ IdType 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. * @param x the x coordinated of the query point, for whom the nearest neighbour will be determined * @param y the x coordinated of the query point, for whom the nearest neighbour will be determined * @param 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. */ IdType 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. * @param 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. */ IdType FindClosestPoint( 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. * @param 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 */ DistanceType GetMinimalDistance( mitk::PointSet::PointType point ); /** * 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. * @param 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 */ bool FindClosestPointAndDistance( mitk::PointSet::PointType point, IdType* id, DistanceType* dist); protected: // // Definition of a vector of ids // typedef std::vector IdVectorType; // // ANN related typedefs, to prevent ANN from being in the global include path. // Please note, that these line are prone to failure, if the point type in // ANN changes. Please note also, that these typedefs are only used in the header // file. The implementation always refers to the original types // typedef float* MyANNpoint; typedef int MyANNidx; typedef float MyANNdist; typedef MyANNpoint* MyANNpointArray; typedef MyANNidx* MyANNidxArray; typedef MyANNdist* MyANNdistArray; /** * constructor */ PointLocator(); /** * destructor */ ~PointLocator(); /** * Initializes the ann search tree using previously defined points */ void InitANN(); /** * releases all memory occupied by the ann search tree and internal point set arrays */ void DestroyANN(); /** * 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. * @param 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. */ IdType FindClosestPoint( const MyANNpoint& point); /** * 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. * @param 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. + * @returns the squared distance in world coordinates between the given point and the nearest neighbour. */ DistanceType GetMinimalDistance( const MyANNpoint& point); bool m_SearchTreeInitialized; IdVectorType m_IndexToPointIdContainer; vtkPoints* m_VtkPoints; mitk::PointSet* m_MitkPoints; ITKPointSet* m_ItkPoints; // // ANN related variables // 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; }; } #endif diff --git a/Modules/MitkExt/Testing/mitkPointLocatorTest.cpp b/Modules/MitkExt/Testing/mitkPointLocatorTest.cpp index 1f36e6106b..50b2e1829e 100644 --- a/Modules/MitkExt/Testing/mitkPointLocatorTest.cpp +++ b/Modules/MitkExt/Testing/mitkPointLocatorTest.cpp @@ -1,155 +1,168 @@ /*========================================================================= Program: Medical Imaging & Interaction Toolkit Language: C++ Date: $Date$ Version: $Revision$ Copyright (c) German Cancer Research Center, Division of Medical and Biological Informatics. All rights reserved. See MITKCopyright.txt or http://www.mitk.org/copyright.html for details. This software is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the above copyright notices for more information. =========================================================================*/ #include +#include #include #include #include #include #include vtkFloatingPointType GenerateRandomNumber( const vtkFloatingPointType& min = 0.0, const vtkFloatingPointType& max = 100.0 ) { return ( ( ( vtkFloatingPointType ) ( std::rand( ) ) ) / ( ( vtkFloatingPointType ) ( RAND_MAX ) ) ) * ( max - min) + min; } void GenerateRandomPoint( vtkFloatingPointType& x, vtkFloatingPointType& y, vtkFloatingPointType& z, const vtkFloatingPointType& min = 0.0, const vtkFloatingPointType& max = 100.0 ) { x = GenerateRandomNumber(min, max); y = GenerateRandomNumber(min, max); z = GenerateRandomNumber(min, max); } int mitkPointLocatorTest(int /*argc*/, char* /*argv*/[]) { + MITK_TEST_BEGIN("mitkPointLocator"); std::srand( 1 ); unsigned int num_points = 10000; // Create PointSet with randomly defined point - std::cout << "Creating random point set of 10000 points "; + MITK_TEST_OUTPUT(<< "Creating random point set of 10000 points "); vtkPoints* points = vtkPoints::New(); - if ( points == NULL ) - { - std::cout << "vtkPoints == NULL. [FAILED]" << std::endl; - return EXIT_FAILURE; - } - for (unsigned int i = 0; i < num_points ; ++i ) { points->InsertPoint(i, GenerateRandomNumber(), GenerateRandomNumber(), GenerateRandomNumber()); } - vtkPolyData* pointSet = vtkPolyData::New(); pointSet->SetPoints( points ); - points->Delete(); - - if ( (unsigned) pointSet->GetNumberOfPoints() != num_points ) - { - std::cout << "Number of points in the vtkPointSet != "<< num_points <<". [FAILED]" << std::endl; - return EXIT_FAILURE; - } - std::cout << "[PASSED]" << std::endl; + + MITK_TEST_CONDITION_REQUIRED((unsigned) pointSet->GetNumberOfPoints()== num_points,"Test number of points in vtkPointSet"); // feed the point set into a vtk point locator - std::cout << "Building vtkPointLocator "; + MITK_TEST_OUTPUT(<< "Building vtkPointLocator "); vtkPointLocator* vtkPointLoc = vtkPointLocator::New(); vtkPointLoc->SetDataSet( pointSet ); vtkPointLoc->BuildLocator(); - std::cout << "[PASSED]" << std::endl; + MITK_TEST_OUTPUT(<< "[PASSED]"); // feed the point set into the mitk point locator - std::cout << "Building mitkPointLocator "; - mitk::PointLocator::Pointer mitkPointLocator = mitk::PointLocator::New(); - mitk::PointLocator::Pointer mitkPointLocator2 = mitk::PointLocator::New(); - if ( mitkPointLocator.IsNull() ) - { - std::cout << "[FAILED]" << std::endl; - return EXIT_FAILURE; - } - else - { - std::cout << "[PASSED]" << std::endl; - } + MITK_TEST_OUTPUT(<< "Building mitkPointLocator "); + mitk::PointLocator::Pointer mitkPointLocatorInitializedByVtkPointSet = mitk::PointLocator::New(); + mitk::PointLocator::Pointer mitkPointLocatorInitializedByMITKPointSet = mitk::PointLocator::New(); + mitk::PointLocator::Pointer mitkPointLocatorInitializedByITKPointSet = mitk::PointLocator::New(); + MITK_TEST_CONDITION_REQUIRED(mitkPointLocatorInitializedByVtkPointSet.IsNotNull(), "Test whether mitkPointLocator is not null"); mitk::PointSet::Pointer mitkPointSet = mitk::PointSet::New(); + mitk::PointLocator::ITKPointSet::Pointer itkPointSet = mitk::PointLocator::ITKPointSet::New(); for ( int i=0; iGetNumberOfPoints();i++ ) { mitk::Point3D pnt; pnt[0] = pointSet->GetPoint( i )[0]; pnt[1] = pointSet->GetPoint( i )[1]; pnt[2] = pointSet->GetPoint( i )[2]; mitkPointSet->InsertPoint(i, pnt ); + mitk::PointLocator::ITKPointSet::PointType itkPoint; + itkPoint[0] = pointSet->GetPoint( i )[0]; + itkPoint[1] = pointSet->GetPoint( i )[1]; + itkPoint[2] = pointSet->GetPoint( i )[2]; + itkPointSet->SetPoint(i,itkPoint); } - std::cout << "Setting random point set "; - mitkPointLocator->SetPoints( pointSet ); - mitkPointLocator2->SetPoints( mitkPointSet ); - std::cout << "[PASSED]" << std::endl; + MITK_TEST_OUTPUT(<< "Setting random point set "); + mitkPointLocatorInitializedByVtkPointSet->SetPoints( pointSet ); + mitkPointLocatorInitializedByMITKPointSet->SetPoints( mitkPointSet ); + mitkPointLocatorInitializedByITKPointSet->SetPoints( itkPointSet ); + MITK_TEST_OUTPUT(<< "[PASSED]"); - std::cout << "Testing 1000 random points "; + MITK_TEST_OUTPUT(<< "Testing 1000 random points "); // generate N random points and calculate the closest // points with both the vtk and mitk pointlocator. // verify, that the point ids are the same. vtkFloatingPointType p[3], x, y, z; mitk::PointSet::PointType pointType; - for ( unsigned int i = 0 ; i < 1000 ; ++i ) + for ( unsigned int i = 0 ; i < 100 ; ++i ) { GenerateRandomPoint( x, y, z ); p[0] = x; p[1] = y; p[2] = z; pointType[0] = p[0]; pointType[1] = p[1]; pointType[2] = p[2]; - int closestPoint1 = vtkPointLoc->FindClosestPoint(p); - int closestPoint2 = mitkPointLocator->FindClosestPoint(p); - int closestPoint3 = mitkPointLocator->FindClosestPoint(x, y, z); - int closestPoint4 = mitkPointLocator2->FindClosestPoint(p); - int closestPoint5 = mitkPointLocator2->FindClosestPoint(pointType); - - if ( closestPoint1 != closestPoint2 ) - { - std::cout << "Id returned by vtkPointLocator doesn't match the one returned by mitk::PointLocator. [FAILED]" << std::endl; - return EXIT_FAILURE; - } - if ( closestPoint2 != closestPoint3 ) - { - std::cout << "There is a mismatch between passing coords as array and as single x/y/z coords. [FAILED]" << std::endl; - return EXIT_FAILURE; - } - if ( closestPoint2 != closestPoint4 ) - { - std::cout << "There is a mismatch between passing the points as mitkPointSet and vtkPointSet. [FAILED]" << std::endl; - return EXIT_FAILURE; - } - if ( closestPoint4 != closestPoint5 ) - { - std::cout << "There is a mismatch between passing coords as array and as single x/y/z coords when using MITK-Types. [FAILED]" << std::endl; - return EXIT_FAILURE; - } + int closestPointReference = vtkPointLoc->FindClosestPoint(p); // ground truth vtkPointLocator + int closestPointVTK1 = mitkPointLocatorInitializedByVtkPointSet->FindClosestPoint(p); + int closestPointVTK2 = mitkPointLocatorInitializedByVtkPointSet->FindClosestPoint(x, y, z); + int closestPointVTK3 = mitkPointLocatorInitializedByVtkPointSet->FindClosestPoint(pointType); + int closestPointMITK1 = mitkPointLocatorInitializedByMITKPointSet->FindClosestPoint(p); + int closestPointMITK2 = mitkPointLocatorInitializedByMITKPointSet->FindClosestPoint(x, y, z); + int closestPointMITK3 = mitkPointLocatorInitializedByMITKPointSet->FindClosestPoint(pointType); + int closestPointITK1 = mitkPointLocatorInitializedByITKPointSet->FindClosestPoint(p); + int closestPointITK2 = mitkPointLocatorInitializedByITKPointSet->FindClosestPoint(x, y, z); + int closestPointITK3 = mitkPointLocatorInitializedByITKPointSet->FindClosestPoint(pointType); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointVTK1,"Test FindClosestPoint() using a point array with a PointLocator initialized with a vtkPointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointVTK2,"Test FindClosestPoint() using single coordinates with a PointLocator initialized with a vtkPointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointVTK3,"Test FindClosestPoint() using an mitk::PointSet with a PointLocator initialized with a vtkPointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointMITK1,"Test FindClosestPoint() using a point array with a PointLocator initialized with a mitk::PointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointMITK2,"Test FindClosestPoint() using single coordinates with a PointLocator initialized with a mitk::PointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointMITK3,"Test FindClosestPoint() using an mitk::PointSet with a PointLocator initialized with a mitk::PointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointITK1,"Test FindClosestPoint() using a point array with a PointLocator initialized with a itk::PointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointITK2,"Test FindClosestPoint() using single coordinates with a PointLocator initialized with a itk::PointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointITK3,"Test FindClosestPoint() using an mitk::PointSet with a PointLocator initialized with a itk::PointSet"); + //Test GetMinimalDistance + // Get closest point + //double* closestPoint = vtkPointLoc->GetPoints()->GetPoint(closestPointReference); + double* closestPoint = pointSet->GetPoint(closestPointReference); + mitk::PointSet::PointType cP; + cP[0] = closestPoint[0]; + cP[1] = closestPoint[1]; + cP[2] = closestPoint[2]; + mitk::PointLocator::DistanceType minimalDistanceReference = cP.SquaredEuclideanDistanceTo(pointType); + + //mitk::PointLocator::DistanceType minimalDistanceReference = + // (x-closestPoint[0])*(x-closestPoint[0])+(y-closestPoint[1])*(y-closestPoint[1])+(z-closestPoint[2])*(z-closestPoint[2]); + mitk::PointLocator::DistanceType minimalDistanceVtk = mitkPointLocatorInitializedByVtkPointSet->GetMinimalDistance(pointType); + mitk::PointLocator::DistanceType minimalDistanceItk = mitkPointLocatorInitializedByITKPointSet->GetMinimalDistance(pointType); + mitk::PointLocator::DistanceType minimalDistanceMITK = mitkPointLocatorInitializedByMITKPointSet->GetMinimalDistance(pointType); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceVtk), "Test GetMinimalDistance() using a PointLocator initialized with a vtkPointSet" ); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceItk), "Test GetMinimalDistance() using a PointLocator initialized with a itkPointSet" ); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceMITK), "Test GetMinimalDistance() using a PointLocator initialized with a MITKPointSet" ); + int closestPointCombinedVtk; + mitk::PointLocator::DistanceType minimalDistanceCombinedVtk; + mitkPointLocatorInitializedByVtkPointSet->FindClosestPointAndDistance(pointType,&closestPointCombinedVtk,&minimalDistanceCombinedVtk); + int closestPointCombinedITK; + mitk::PointLocator::DistanceType minimalDistanceCombinedITK; + mitkPointLocatorInitializedByITKPointSet->FindClosestPointAndDistance(pointType,&closestPointCombinedITK,&minimalDistanceCombinedITK); + int closestPointCombinedMITK; + mitk::PointLocator::DistanceType minimalDistanceCombinedMITK; + mitkPointLocatorInitializedByMITKPointSet->FindClosestPointAndDistance(pointType,&closestPointCombinedMITK,&minimalDistanceCombinedMITK); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceCombinedVtk), "Test distance returned by FindClosestPointAndDistance() using a PointLocator initialized with a vtkPointSet" ); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceCombinedITK), "Test distance returned by FindClosestPointAndDistance() using a PointLocator initialized with a itkPointSet" ); + MITK_TEST_CONDITION_REQUIRED(mitk::Equal(minimalDistanceReference,minimalDistanceCombinedMITK), "Test distance returned by FindClosestPointAndDistance() using a PointLocator initialized with a MITKPointSet" ); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointCombinedVtk,"Test closest point returned by FindClosestPointAndDistance() using a point array with a PointLocator initialized with a vtkPointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointCombinedITK,"Test closest point returned by FindClosestPointAndDistance() using a point array with a PointLocator initialized with a itkPointSet"); + MITK_TEST_CONDITION_REQUIRED(closestPointReference==closestPointCombinedMITK,"Test closest point returned by FindClosestPointAndDistance() using a point array with a PointLocator initialized with a MITKPointSet"); } vtkPointLoc->Delete(); pointSet->Delete(); - std::cout << "[PASSED]" << std::endl; - std::cout<<"[TEST DONE]"<