00001 /*========================================================================= 00002 00003 Library : Image Registration Toolkit (IRTK) 00004 Module : $Id: vtkKDTreePointLocator.h 13 2009-03-23 11:56:35Z dr $ 00005 Copyright : Imperial College, Department of Computing 00006 Visual Information Processing (VIP), 2008 onwards 00007 Date : $Date: 2009-03-23 11:56:35 +0000 (Mon, 23 Mar 2009) $ 00008 Version : $Revision: 13 $ 00009 Changes : $Author: dr $ 00010 00011 =========================================================================*/ 00012 00013 #ifdef HAS_VTK 00014 00015 #ifndef __vtkKDTreePointLocator_h 00016 #define __vtkKDTreePointLocator_h 00017 00018 #include "vtkLocator.h" 00019 #include "vtkPoints.h" 00020 #include "vtkIdList.h" 00021 #include <irtkImage.h> 00022 00023 class vtkKDTreeNode; 00024 class PointData; 00025 00026 class vtkKDTreePointLocator : public vtkLocator 00027 { 00028 public: 00029 ~vtkKDTreePointLocator(); 00030 static vtkKDTreePointLocator *New(); 00031 const char *GetClassName() { 00032 return "vtkKDTreePointLocator"; 00033 }; 00034 //void PrintSelf(ostream& os, vtkIndent indent); 00035 00036 vtkTypeRevisionMacro(vtkKDTreePointLocator,vtkLocator); 00037 00038 // Description: 00039 // Construct with 10 records per terminal bucket 00040 vtkKDTreePointLocator(); 00041 00042 // Description: 00043 // Specify the average number of points in each bucket. 00044 vtkSetClampMacro(NumberOfPointsPerBucket,int,1,VTK_LARGE_INTEGER); 00045 vtkGetMacro(NumberOfPointsPerBucket,int); 00046 00047 // Description: 00048 // Given a position x, return the id of the point closest to it. The 00049 // dimensionality of x should be the same as GetDataDimension 00050 // Calls BuildLocator, so this method may throw an exception. 00051 virtual int FindClosestPoint(double *x); 00052 00053 // Description: 00054 // Given a position x when the input data dimensionality is 3, 00055 // returns the id of the point closest to it. If GetDataDimension != 3, 00056 // returns -1. 00057 // Calls BuildLocator, so this method may throw an exception. 00058 int FindClosestPoint(double x, double y, double z); 00059 00060 // Description: 00061 // Find the closest N points to a position. This returns the closest 00062 // N points to a position. A faster method could be created that returned 00063 // N close points to a position, but neccesarily the exact N closest. 00064 // The returned points are sorted from closest to farthest. 00065 /* virtual void FindClosestNPoints(int N, float x[3], vtkIdList *result) 00066 virtual void FindClosestNPoints(int N, float x, float y, float z, 00067 vtkIdList *result); 00068 */ 00069 // Description: 00070 // Find all points within a specified radius R of position x. 00071 // The result is not sorted in any specific manner. 00072 /* virtual void FindPointsWithinRadius(float R, float x[3], vtkIdList *result); 00073 virtual void FindPointsWithinRadius(float R, float x, float y, float z, 00074 vtkIdList *result); 00075 */ 00076 // Description: 00077 // See vtkLocator interface documentation. 00078 void FreeSearchStructure(); 00079 00080 // Description: 00081 // Builds the internal search structure. If no input data set has been 00082 // assigned or if its dimensionality is indeterminate, this method 00083 // throws an exception. 00084 // Note: this method is NOT thread-safe 00085 void BuildLocator(); 00086 00087 // This method is unimplemented. The interface description is vague 00088 // enough that I don't know what it's supposed to do. 00089 void GenerateRepresentation(int level, vtkPolyData *pd); 00090 00091 #ifdef _DEBUG 00092 // Description: 00093 // Test method that verifies internal data structure consistency. 00094 // xmlOutputFName is the filename of an XML file to be written that 00095 // encodes the KD-Tree. If xmlOutputFName == NULL, no file is written. 00096 // TreeIsConsistent returns false if: 00097 // 1) Any points are found in the wrong KDTree bins 00098 // 2) Any points were left out of the KDTree 00099 // 3) Any points were included in two tree bins 00100 // 4) Any illegal point IDs are stored in the tree 00101 // Calls BuildLocator, so this method may throw an exception. 00102 bool TreeIsConsistent(const char *xmlOutputFName = NULL); 00103 #endif 00104 00105 // Description: 00106 // Determines the dimensionality of the input data. Note: this only works 00107 // if the data set is a vtkPointSet, vtkImageData, or vtkRectilinearGrid. 00108 // For all other data types, -1 is returned and vtkWarningMacro is called. 00109 virtual int GetDataDimension(); 00110 00111 protected: 00112 // Description: 00113 // Recursively builds a KD-tree from the points given. 00114 // Precondition: GetDataDimension should return a valid result 00115 // Note: this method is NOT thread-safe. 00116 vtkKDTreeNode *BuildTree(int numPoints, PointData *pts); 00117 00118 int NumberOfPointsPerBucket; //Used with previous boolean to control subdivide 00119 vtkKDTreeNode *Root; 00120 00121 // Description: 00122 // Recursive method that finds the single closest data set point to 00123 // a given point in 3D. Based on [Friedman, pg. 224-5]. 00124 // Assumes that the tree structure has been built before calling. 00125 bool SearchForClosestPoint( 00126 double *x, vtkKDTreeNode *node, 00127 int &closestPointId, double &closestPointDistanceSquared, 00128 double *closestPoint, double extent[6]); 00129 00130 // Description: 00131 // Based on [Friedman, pg. 225]. Slightly adapted. We used the Euclidean 00132 // distance for the DISSIM and COORDINATE DISTANCE functions. Instead of 00133 // taking the square root (e.g. doing DISSIM) on the sum, we squared the 00134 // PQD[1] number (e.g. doing inverse(DISSIM)). 00135 // Assumes that the tree structure has been built before calling. 00136 bool BoundsOverlapBall(double *x, 00137 double closestPointDistanceSquared, double extent[6]); 00138 }; 00139 00140 #endif 00141 00142 #endif