| 1 |
|
/*========================================================================= |
| 2 |
|
|
| 3 |
|
Program: Insight Segmentation & Registration Toolkit |
| 4 |
|
Module: $RCSfile: itkPointLocator.h.html,v $ |
| 5 |
|
Language: C++ |
| 6 |
|
Date: $Date: 2006/01/17 19:15:43 $ |
| 7 |
|
Version: $Revision: 1.4 $ |
| 8 |
|
|
| 9 |
|
Copyright (c) Insight Software Consortium. All rights reserved. |
| 10 |
|
See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details. |
| 11 |
|
|
| 12 |
|
Portions of this code are covered under the VTK copyright. |
| 13 |
|
See VTKCopyright.txt or http://www.kitware.com/VTKCopyright.htm for details. |
| 14 |
|
|
| 15 |
|
This software is distributed WITHOUT ANY WARRANTY; without even |
| 16 |
|
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR |
| 17 |
IND |
*****PURPOSE. See the above copyright notices for more information. |
| 18 |
|
|
| 19 |
|
=========================================================================*/ |
| 20 |
|
#ifndef __itkPointLocator_h |
| 21 |
|
#define __itkPointLocator_h |
| 22 |
|
|
| 23 |
|
#include "itkObject.h" |
| 24 |
|
#include "itkPoint.h" |
| 25 |
|
#include "itkNumericTraits.h" |
| 26 |
|
#include "itkBoundingBox.h" |
| 27 |
|
|
| 28 |
|
namespace itk |
| 29 |
|
{ |
| 30 |
|
|
| 31 |
|
/** \class PointLocator |
| 32 |
|
* \brief Accelerate geometric searches for points. |
| 33 |
|
* |
| 34 |
|
* This class accelerates the search for n-dimensional points. The class |
| 35 |
|
* operates by using a regular n-dimensional hypercube lattice (e.g., a 2D |
| 36 |
|
* grid, 3D volume, etc.) into which points are inserted. Each hypercube |
| 37 |
|
* (also called a bucket) contains a list of points that are contained within |
| 38 |
|
* it. |
| 39 |
|
* |
| 40 |
|
* Template parameters for PointLocator: |
| 41 |
|
* |
| 42 |
|
* TPointIdentifier = |
| 43 |
|
* The type used to access a particular point (i.e., a point's id) |
| 44 |
|
* |
| 45 |
|
* TCoordRep = |
| 46 |
|
* Numerical type with which to represent each coordinate value. |
| 47 |
|
* |
| 48 |
|
* VPointDimension = |
| 49 |
|
* Geometric dimension of space. |
| 50 |
|
*/ |
| 51 |
|
|
| 52 |
|
template < |
| 53 |
|
typename TPointIdentifier = unsigned long, |
| 54 |
|
int VPointDimension = 3, |
| 55 |
|
typename TCoordRep = float, |
| 56 |
|
typename TPointsContainer = |
| 57 |
|
VectorContainer< TPointIdentifier,Point<TCoordRep,VPointDimension> > |
| 58 |
IND |
**> |
| 59 |
|
class ITK_EXPORT PointLocator : public Object |
| 60 |
|
{ |
| 61 |
|
public: |
| 62 |
|
/** Standard class typedefs. */ |
| 63 |
|
typedef PointLocator Self; |
| 64 |
TDA |
typedef Object Superclass; |
| 65 |
TDA |
typedef SmartPointer<Self> Pointer; |
| 66 |
TDA |
typedef SmartPointer<const Self> ConstPointer; |
| 67 |
|
|
| 68 |
|
/** Method for creation through the object factory. */ |
| 69 |
|
itkNewMacro(Self); |
| 70 |
|
|
| 71 |
|
/** Standard part of every itk Object. */ |
| 72 |
|
itkTypeMacro(PointLocator, Object); |
| 73 |
|
|
| 74 |
|
/** Capture template parameter information. */ |
| 75 |
|
itkStaticConstMacro(PointDimension, unsigned int, VPointDimension); |
| 76 |
|
|
| 77 |
|
/** Hold on to the type information specified by the template parameters. |
| 78 |
|
* PointIdentifier is the type that the point handles are represented by. */ |
| 79 |
|
typedef TPointIdentifier PointIdentifier; |
| 80 |
TDA |
typedef TCoordRep CoordRepType; |
| 81 |
TDA |
typedef TPointsContainer PointsContainer; |
| 82 |
TDA |
typedef typename PointsContainer::Pointer PointsContainerPointer; |
| 83 |
TDA |
typedef Point< CoordRepType, VPointDimension > PointType; |
| 84 |
|
|
| 85 |
|
/** Some convenience typedefs. */ |
| 86 |
|
typedef BoundingBox<PointIdentifier,VPointDimension, |
| 87 |
|
CoordRepType,PointsContainer> BoundingBoxType; |
| 88 |
|
typedef typename BoundingBoxType::Pointer BoundingBoxPointer; |
| 89 |
|
|
| 90 |
|
/** Set the number of divisions in each axis direction. */ |
| 91 |
|
itkSetVectorMacro(Divisions,unsigned long,VPointDimension); |
| 92 |
|
itkGetVectorMacro(Divisions,unsigned long,VPointDimension); |
| 93 |
|
|
| 94 |
|
/** Specify the average number of points in each bucket. */ |
| 95 |
|
itkSetClampMacro(NumberOfPointsPerBucket, |
| 96 |
|
unsigned long,1,NumericTraits<unsigned long>::max()); |
| 97 |
|
itkGetMacro(NumberOfPointsPerBucket,unsigned long); |
| 98 |
|
|
| 99 |
|
/** Insert all the points contained in the PointsContainer newPts |
| 100 |
|
* into the locator. Also supply a bounding box in which the points lie. |
| 101 |
|
* This methods differs from InitIncrementalPointInsertion() in that |
| 102 |
|
* assumes that all the points are inserted at once. */ |
| 103 |
|
void InitPointInsertion(PointsContainer *newPts, BoundingBoxPointer bbox); |
| 104 |
|
|
| 105 |
|
/** Initialize the incremental point insertion process. Incremental point |
| 106 |
|
* insertion is used to insert points one at a time into the locator. The |
| 107 |
|
* supplied PointsContainer (newPts) collects the points that can be used |
| 108 |
|
* by other objects later. Bounds are the box that the points lie in. */ |
| 109 |
LEN |
void InitIncrementalPointInsertion(PointsContainer *newPts, BoundingBoxPointer bbox); |
| 110 |
|
|
| 111 |
|
#if 0 |
| 112 |
|
|
| 113 |
|
/** Given a position x, return the id of the point closest to it. Alternative |
| 114 |
|
* method requires separate x-y-z values. */ |
| 115 |
|
virtual int FindClosestPoint(float x[3]); |
| 116 |
|
int FindClosestPoint(float x, float y, float z); |
| 117 |
|
|
| 118 |
|
/** Initialize the point insertion process. The newPts is an object |
| 119 |
|
* representing point coordinates into which incremental insertion methods |
| 120 |
|
* place their data. Bounds are the box that the points lie in. */ |
| 121 |
|
virtual int InitPointInsertion(itkPoints *newPts, float bounds[6], |
| 122 |
|
int estSize); |
| 123 |
|
|
| 124 |
|
/** Incrementally insert a point into search structure with a particular |
| 125 |
|
* index value. You should use the method IsInsertedPoint() to see whether |
| 126 |
|
* this point has already been inserted (that is, if you desire to prevent |
| 127 |
|
* dulicate points). Before using this method you must make sure that |
| 128 |
|
* newPts have been supplied, the bounds has been set properly, and that |
| 129 |
|
* divs are properly set. (See InitPointInsertion().) */ |
| 130 |
|
virtual void InsertPoint(int ptId, float x[3]); |
| 131 |
|
|
| 132 |
|
/** Incrementally insert a point into search structure. The method returns |
| 133 |
|
* the insertion location (i.e., point id). You should use the method |
| 134 |
|
* IsInsertedPoint() to see whether this point has already been |
| 135 |
|
* inserted (that is, if you desire to prevent dulicate points). |
| 136 |
|
* Before using this method you must make sure that newPts have been |
| 137 |
|
* supplied, the bounds has been set properly, and that divs are |
| 138 |
|
* properly set. (See InitPointInsertion().) */ |
| 139 |
|
virtual int InsertNextPoint(float x[3]); |
| 140 |
|
|
| 141 |
|
/** Determine whether point given by x[3] has been inserted into points list. |
| 142 |
|
* Return id of previously inserted point if this is true, otherwise return |
| 143 |
|
* -1. */ |
| 144 |
|
int IsInsertedPoint(float x, float y, float z) |
| 145 |
|
{ |
| 146 |
|
float xyz[3]; |
| 147 |
|
xyz[0] = x; xyz[1] = y; xyz[2] = z; |
| 148 |
|
return this->IsInsertedPoint (xyz); |
| 149 |
|
}; |
| 150 |
|
virtual int IsInsertedPoint(float x[3]); |
| 151 |
|
|
| 152 |
|
/** Determine whether point given by x[3] has been inserted into points list. |
| 153 |
|
* Return 0 if point was already in the list, otherwise return 1. If the |
| 154 |
|
* point was not in the list, it will be ADDED. In either case, the id of |
| 155 |
|
* the point (newly inserted or not) is returned in the ptId argument. |
| 156 |
|
* Note this combines the functionality of IsInsertedPoint() followed |
| 157 |
|
* by a call to InsertNextPoint(). */ |
| 158 |
|
virtual int InsertUniquePoint(float x[3], int &ptId); |
| 159 |
|
|
| 160 |
|
/** Given a position x, return the id of the point closest to it. This method |
| 161 |
|
* is used when performing incremental point insertion. */ |
| 162 |
|
virtual int FindClosestInsertedPoint(float x[3]); |
| 163 |
|
#endif |
| 164 |
|
|
| 165 |
|
protected: |
| 166 |
|
PointLocator(); |
| 167 |
|
~PointLocator(); |
| 168 |
|
virtual void PrintSelf(std::ostream& os, Indent indent) const; |
| 169 |
|
|
| 170 |
|
#if 0 |
| 171 |
|
// place points in appropriate buckets |
| 172 |
|
void GetBucketNeighbors(int ijk[3], int ndivs[3], int level); |
| 173 |
|
void GetOverlappingBuckets(float x[3], int ijk[3], float dist, int level); |
| 174 |
|
void GetOverlappingBuckets(float x[3], float dist, int prevMinLevel[3], |
| 175 |
|
int prevMaxLevel[3]); |
| 176 |
|
void GenerateFace(int face, int i, int j, int k, |
| 177 |
|
itkPoints *pts, itkCellArray *polys); |
| 178 |
|
float Distance2ToBucket(float x[3], int nei[3]); |
| 179 |
|
float Distance2ToBounds(float x[3], float bounds[6]); |
| 180 |
|
|
| 181 |
|
|
| 182 |
|
float Bounds[6]; // bounds of points |
| 183 |
|
itkIdList **HashTable; // lists of point ids in buckets |
| 184 |
|
int NumberOfBuckets; // total size of hash table |
| 185 |
|
float H[3]; // width of each bucket in x-y-z directions |
| 186 |
|
itkNeighborPoints *Buckets; |
| 187 |
|
|
| 188 |
|
float InsertionTol2; |
| 189 |
|
float InsertionLevel; |
| 190 |
|
#endif |
| 191 |
|
|
| 192 |
|
private: |
| 193 |
|
PointLocator(const Self&); //purposely not implemented |
| 194 |
|
void operator=(const Self&); //purposely not implemented |
| 195 |
|
|
| 196 |
|
unsigned long *m_Divisions; |
| 197 |
|
unsigned long m_NumberOfPointsPerBucket; |
| 198 |
|
|
| 199 |
|
PointsContainerPointer m_Points; |
| 200 |
|
|
| 201 |
|
}; // End Class: PointLocator |
| 202 |
|
|
| 203 |
|
} // end namespace itk |
| 204 |
|
|
| 205 |
|
#ifndef ITK_MANUAL_INSTANTIATION |
| 206 |
|
#include "itkPointLocator.txx" |
| 207 |
|
#endif |
| 208 |
|
|
| 209 |
|
#endif |
| 210 |
|
|
| 211 |
EOF |
|
| 212 |
EOF,EML |
|
