---

Common/vtkPointLocator.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Visualization Toolkit
  Module:    $RCSfile: vtkPointLocator.h,v $
  Language:  C++


Copyright (c) 1993-2001 Ken Martin, Will Schroeder, Bill Lorensen 
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

 * Redistributions of source code must retain the above copyright notice,
   this list of conditions and the following disclaimer.

 * Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

 * Neither name of Ken Martin, Will Schroeder, or Bill Lorensen nor the names
   of any contributors may be used to endorse or promote products derived
   from this software without specific prior written permission.

 * Modified source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

=========================================================================*/
#ifndef __vtkPointLocator_h
#define __vtkPointLocator_h

#include "vtkLocator.h"
#include "vtkPoints.h"

class vtkIdList;
class vtkNeighborPoints;

class VTK_COMMON_EXPORT vtkPointLocator : public vtkLocator
{
public:
  static vtkPointLocator *New();

  vtkTypeMacro(vtkPointLocator,vtkLocator);
  void PrintSelf(ostream& os, vtkIndent indent);


  vtkSetVector3Macro(Divisions,int);
  vtkGetVectorMacro(Divisions,int,3);


  vtkSetClampMacro(NumberOfPointsPerBucket,int,1,VTK_LARGE_INTEGER);
  vtkGetMacro(NumberOfPointsPerBucket,int);


  virtual vtkIdType FindClosestPoint(const float x[3]);
  vtkIdType FindClosestPoint(float x, float y, float z);


  vtkIdType FindClosestPointWithinRadius(float radius, const float x[3],
                                         float& dist2);
  vtkIdType FindClosestPointWithinRadius(float radius, const float x[3], 
                                         float inputDataLength, float& dist2);

  virtual int InitPointInsertion(vtkPoints *newPts, const float bounds[6]);


  virtual int InitPointInsertion(vtkPoints *newPts, const float bounds[6], 
                                 vtkIdType estSize);

  virtual void InsertPoint(vtkIdType ptId, const float x[3]);

  virtual vtkIdType InsertNextPoint(const float x[3]);


  vtkIdType IsInsertedPoint(float x, float  y, float z)
    {
    float xyz[3];
    xyz[0] = x; xyz[1] = y; xyz[2] = z;
    return this->IsInsertedPoint (xyz);
    };
  virtual vtkIdType IsInsertedPoint(const float x[3]);

  virtual int InsertUniquePoint(const float x[3], vtkIdType &ptId);

  virtual vtkIdType FindClosestInsertedPoint(const float x[3]);


  virtual void FindClosestNPoints(int N, const float x[3], vtkIdList *result);
  virtual void FindClosestNPoints(int N, float x, float y, float z,
                                  vtkIdList *result);


  virtual void FindDistributedPoints(int N, const float x[3], 
                                     vtkIdList *result, int M);
  virtual void FindDistributedPoints(int N, float x, float y, 
                                     float z, vtkIdList *result, int M);


  virtual void FindPointsWithinRadius(float R, const float x[3],
                                      vtkIdList *result);
  virtual void FindPointsWithinRadius(float R, float x, float y, float z, 
                                      vtkIdList *result);
  
  virtual vtkIdList *GetPointsInBucket(const float x[3], int ijk[3]);


  void Initialize();
  void FreeSearchStructure();
  void BuildLocator();
  void GenerateRepresentation(int level, vtkPolyData *pd);

protected:
  vtkPointLocator();
  ~vtkPointLocator();

  // place points in appropriate buckets
  void GetBucketNeighbors(vtkNeighborPoints* buckets,
                          const int ijk[3], const int ndivs[3], int level);
  void GetOverlappingBuckets(vtkNeighborPoints* buckets, 
                             const float x[3], const int ijk[3], float dist,
                             int level);
  void GetOverlappingBuckets(vtkNeighborPoints* buckets,
                             const float x[3], float dist,
                             int prevMinLevel[3],
                             int prevMaxLevel[3]);
  void GenerateFace(int face, int i, int j, int k, 
                    vtkPoints *pts, vtkCellArray *polys);
  float Distance2ToBucket(const float x[3], const int nei[3]);
  float Distance2ToBounds(const float x[3], const float bounds[6]);

  vtkPoints *Points; // Used for merging points
  int Divisions[3]; // Number of sub-divisions in x-y-z directions
  int NumberOfPointsPerBucket; //Used with previous boolean to control subdivide
  float Bounds[6]; // bounds of points
  vtkIdList **HashTable; // lists of point ids in buckets
  vtkIdType NumberOfBuckets; // total size of hash table
  float H[3]; // width of each bucket in x-y-z directions

  float InsertionTol2;
  vtkIdType InsertionPointId;

  float InsertionLevel; 
private:
  vtkPointLocator(const vtkPointLocator&);  // Not implemented.
  void operator=(const vtkPointLocator&);  // Not implemented.
};

#endif

---