You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
245 lines
10 KiB
245 lines
10 KiB
/*=========================================================================
|
|
|
|
Program: Visualization Toolkit
|
|
Module: $RCSfile: vtkPointLocator.h,v $
|
|
|
|
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
|
|
All rights reserved.
|
|
See Copyright.txt or http://www.kitware.com/Copyright.htm 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 notice for more information.
|
|
|
|
=========================================================================*/
|
|
// .NAME vtkPointLocator - quickly locate points in 3-space
|
|
// .SECTION Description
|
|
// vtkPointLocator is a spatial search object to quickly locate points in 3D.
|
|
// vtkPointLocator works by dividing a specified region of space into a regular
|
|
// array of "rectangular" buckets, and then keeping a list of points that
|
|
// lie in each bucket. Typical operation involves giving a position in 3D
|
|
// and finding the closest point.
|
|
//
|
|
// vtkPointLocator has two distinct methods of interaction. In the first
|
|
// method, you supply it with a dataset, and it operates on the points in
|
|
// the dataset. In the second method, you supply it with an array of points,
|
|
// and the object operates on the array.
|
|
|
|
// .SECTION Caveats
|
|
// Many other types of spatial locators have been developed such as
|
|
// octrees and kd-trees. These are often more efficient for the
|
|
// operations described here.
|
|
|
|
// .SECTION See Also
|
|
// vtkCellPicker vtkPointPicker
|
|
|
|
#ifndef __vtkPointLocator_h
|
|
#define __vtkPointLocator_h
|
|
|
|
#include "vtkLocator.h"
|
|
|
|
class vtkCellArray;
|
|
class vtkIdList;
|
|
class vtkNeighborPoints;
|
|
class vtkPoints;
|
|
|
|
class VTK_FILTERING_EXPORT vtkPointLocator : public vtkLocator
|
|
{
|
|
public:
|
|
// Description:
|
|
// Construct with automatic computation of divisions, averaging
|
|
// 25 points per bucket.
|
|
static vtkPointLocator *New();
|
|
|
|
vtkTypeRevisionMacro(vtkPointLocator,vtkLocator);
|
|
void PrintSelf(ostream& os, vtkIndent indent);
|
|
|
|
// Description:
|
|
// Set the number of divisions in x-y-z directions.
|
|
vtkSetVector3Macro(Divisions,int);
|
|
vtkGetVectorMacro(Divisions,int,3);
|
|
|
|
// Description:
|
|
// Specify the average number of points in each bucket.
|
|
vtkSetClampMacro(NumberOfPointsPerBucket,int,1,VTK_LARGE_INTEGER);
|
|
vtkGetMacro(NumberOfPointsPerBucket,int);
|
|
|
|
// Description:
|
|
// Given a position x, return the id of the point closest to it. Alternative
|
|
// method requires separate x-y-z values.
|
|
// These methods are thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first.
|
|
virtual vtkIdType FindClosestPoint(const double x[3]);
|
|
vtkIdType FindClosestPoint(double x, double y, double z);
|
|
|
|
// Description:
|
|
// Given a position x and a radius r, return the id of the point
|
|
// closest to the point in that radius.
|
|
// These methods are thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first. dist2 returns the squared
|
|
// distance to the point.
|
|
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3],
|
|
double& dist2);
|
|
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3],
|
|
double inputDataLength, double& dist2);
|
|
|
|
// Description:
|
|
// Initialize the point insertion process. The newPts is an object
|
|
// representing point coordinates into which incremental insertion methods
|
|
// place their data. Bounds are the box that the points lie in.
|
|
// Not thread safe.
|
|
virtual int InitPointInsertion(vtkPoints *newPts, const double bounds[6]);
|
|
|
|
// Description:
|
|
// Initialize the point insertion process. The newPts is an object
|
|
// representing point coordinates into which incremental insertion methods
|
|
// place their data. Bounds are the box that the points lie in.
|
|
// Not thread safe.
|
|
virtual int InitPointInsertion(vtkPoints *newPts, const double bounds[6],
|
|
vtkIdType estSize);
|
|
|
|
// Description:
|
|
// Incrementally insert a point into search structure with a particular
|
|
// index value. You should use the method IsInsertedPoint() to see whether
|
|
// this point has already been inserted (that is, if you desire to prevent
|
|
// duplicate points). Before using this method you must make sure that
|
|
// newPts have been supplied, the bounds has been set properly, and that
|
|
// divs are properly set. (See InitPointInsertion().)
|
|
// Not thread safe.
|
|
virtual void InsertPoint(vtkIdType ptId, const double x[3]);
|
|
|
|
// Description:
|
|
// Incrementally insert a point into search structure. The method returns
|
|
// the insertion location (i.e., point id). You should use the method
|
|
// IsInsertedPoint() to see whether this point has already been
|
|
// inserted (that is, if you desire to prevent duplicate points).
|
|
// Before using this method you must make sure that newPts have been
|
|
// supplied, the bounds has been set properly, and that divs are
|
|
// properly set. (See InitPointInsertion().)
|
|
// Not thread safe.
|
|
virtual vtkIdType InsertNextPoint(const double x[3]);
|
|
|
|
// Description:
|
|
// Determine whether point given by x[3] has been inserted into points list.
|
|
// Return id of previously inserted point if this is true, otherwise return
|
|
// -1. This method is thread safe.
|
|
vtkIdType IsInsertedPoint(double x, double y, double z)
|
|
{
|
|
double xyz[3];
|
|
xyz[0] = x; xyz[1] = y; xyz[2] = z;
|
|
return this->IsInsertedPoint (xyz);
|
|
};
|
|
virtual vtkIdType IsInsertedPoint(const double x[3]);
|
|
|
|
// Description:
|
|
// Determine whether point given by x[3] has been inserted into points list.
|
|
// Return 0 if point was already in the list, otherwise return 1. If the
|
|
// point was not in the list, it will be ADDED. In either case, the id of
|
|
// the point (newly inserted or not) is returned in the ptId argument.
|
|
// Note this combines the functionality of IsInsertedPoint() followed
|
|
// by a call to InsertNextPoint().
|
|
// This method is not thread safe.
|
|
virtual int InsertUniquePoint(const double x[3], vtkIdType &ptId);
|
|
|
|
// Description:
|
|
// Given a position x, return the id of the point closest to it. This method
|
|
// is used when performing incremental point insertion. Note that -1
|
|
// indicates that no point was found.
|
|
// This method is thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first.
|
|
virtual vtkIdType FindClosestInsertedPoint(const double x[3]);
|
|
|
|
// Description:
|
|
// Find the closest N points to a position. This returns the closest
|
|
// N points to a position. A faster method could be created that returned
|
|
// N close points to a position, but necessarily the exact N closest.
|
|
// The returned points are sorted from closest to farthest.
|
|
// These methods are thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first.
|
|
virtual void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
|
|
virtual void FindClosestNPoints(int N, double x, double y, double z,
|
|
vtkIdList *result);
|
|
|
|
// Description:
|
|
// Find the closest points to a position such that each octant of
|
|
// space around the position contains at least N points. Loosely
|
|
// limit the search to a maximum number of points evaluated, M.
|
|
// These methods are thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first.
|
|
virtual void FindDistributedPoints(int N, const double x[3],
|
|
vtkIdList *result, int M);
|
|
virtual void FindDistributedPoints(int N, double x, double y,
|
|
double z, vtkIdList *result, int M);
|
|
|
|
// Description:
|
|
// Find all points within a specified radius R of position x.
|
|
// The result is not sorted in any specific manner.
|
|
// These methods are thread safe if BuildLocator() is directly or
|
|
// indirectly called from a single thread first.
|
|
virtual void FindPointsWithinRadius(double R, const double x[3],
|
|
vtkIdList *result);
|
|
virtual void FindPointsWithinRadius(double R, double x, double y, double z,
|
|
vtkIdList *result);
|
|
|
|
// Description:
|
|
// Given a position x, return the list of points in the bucket that
|
|
// contains the point. It is possible that NULL is returned. The user
|
|
// provides an ijk array that is the indices into the locator.
|
|
// This method is thread safe.
|
|
virtual vtkIdList *GetPointsInBucket(const double x[3], int ijk[3]);
|
|
|
|
// Description:
|
|
// Provide an accessor to the points.
|
|
vtkGetObjectMacro(Points, vtkPoints);
|
|
|
|
// Description:
|
|
// Provide an accessor to the bounds.
|
|
double *GetBounds() { return this->Bounds; };
|
|
|
|
// Description:
|
|
// See vtkLocator interface documentation.
|
|
// These methods are not thread safe.
|
|
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 double x[3], const int ijk[3], double dist,
|
|
int level);
|
|
void GetOverlappingBuckets(vtkNeighborPoints* buckets,
|
|
const double x[3], double dist,
|
|
int prevMinLevel[3],
|
|
int prevMaxLevel[3]);
|
|
void GenerateFace(int face, int i, int j, int k,
|
|
vtkPoints *pts, vtkCellArray *polys);
|
|
double Distance2ToBucket(const double x[3], const int nei[3]);
|
|
double Distance2ToBounds(const double x[3], const double 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
|
|
double Bounds[6]; // bounds of points
|
|
vtkIdList **HashTable; // lists of point ids in buckets
|
|
vtkIdType NumberOfBuckets; // total size of hash table
|
|
double H[3]; // width of each bucket in x-y-z directions
|
|
|
|
double InsertionTol2;
|
|
vtkIdType InsertionPointId;
|
|
|
|
double InsertionLevel;
|
|
private:
|
|
vtkPointLocator(const vtkPointLocator&); // Not implemented.
|
|
void operator=(const vtkPointLocator&); // Not implemented.
|
|
};
|
|
|
|
#endif
|
|
|
|
|
|
|