/*******************************************************************
 *                                                                 *
 *  Range Image Registration Testbed Toolkit                       *
 *  by Gerald Dalley                                               *
 *  Copyright (C) 2001 The Ohio State University                   *
 *                                                                 *
 *******************************************************************/
/*=========================================================================

  Program:   Visualization Toolkit
  Language:  C++
  
The authors hereby grant permission to use, copy, and distribute this
software and its documentation for any purpose, provided that existing
copyright notices are retained in all copies and that this notice is included
verbatim in any distributions. Additionally, the authors grant permission to
modify this software and its documentation for any purpose, provided that
such modifications are not distributed without the explicit consent of the
authors and that existing copyright notices are retained in all copies. Some
of the algorithms implemented by this software are patented, observe all
applicable patent law.

IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF,
EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN
"AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

=========================================================================*/
// .NAME vtkKDTreePointLocator - quickly locate points in 3-space
// .SECTION Description
//	Similar to vtkPointLocator.  This implementation uses a KD-Tree for
//  faster retrieval.  Also, this class does not require points that are to
//  be tested to be inside the original bounding box.
//
//  See:
//      J Friedman, J Bentley, R Finkel.  "An Algorithm for Finding Best 
//      Matches in Logarithmic Expected Time".  ACM Transactions on 
//      Mathematical Software, Vol. 3, No. 3, Sept. 1977, pp. 209-226.

#ifndef __vtkKDTreePointLocator_h
#define __vtkKDTreePointLocator_h

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

class vtkKDTreeNode;
struct PointData;

class /*VTK_EXPORT*/ vtkKDTreePointLocator : public vtkLocator
{
public:
  ~vtkKDTreePointLocator();
  static vtkKDTreePointLocator *New() {return new vtkKDTreePointLocator;};
  const char *GetClassName() {return "vtkKDTreePointLocator";};
  //void PrintSelf(ostream& os, vtkIndent indent);

  // Description:
  // Construct with 10 records per terminal bucket
  vtkKDTreePointLocator();

  // 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.
  virtual int FindClosestPoint(float x[3]);
  int FindClosestPoint(float x, float y, float z);

  // 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 neccesarily the exact N closest.
  // The returned points are sorted from closest to farthest.
/*  virtual void FindClosestNPoints(int N, float x[3], vtkIdList *result)
  virtual void FindClosestNPoints(int N, float x, float y, float z,
				  vtkIdList *result);
*/
  // Description:
  // Find all points within a specified radius R of position x.
  // The result is not sorted in any specific manner.
/*  virtual void FindPointsWithinRadius(float R, float x[3], vtkIdList *result);
  virtual void FindPointsWithinRadius(float R, float x, float y, float z, 
				      vtkIdList *result);
*/
  // Description:
  // See vtkLocator interface documentation.
  void FreeSearchStructure();
  void BuildLocator();
  // This method is unimplemented.  The interface description is vague 
  // enough that I don't know what it's supposed to do.
  void GenerateRepresentation(int level, vtkPolyData *pd);

protected:
  vtkKDTreeNode *BuildTree(int numPoints, PointData *pts);

  int NumberOfPointsPerBucket; //Used with previous boolean to control subdivide
  vtkKDTreeNode *Root;

  // Description:
  // Recursive method that finds the single closest data set point to
  // a given point in 3D.  Based on [Friedman, pg. 224-5]
  // TBD: Generalize for k-D
  bool SearchForClosestPoint(
    float *x, vtkKDTreeNode *node, 
    int &closestPointId, float &closestPointDistanceSquared, 
    float *closestPoint, float extent[6]);

  // Description:
  // Based on [Friedman, pg. 225].  Slightly adapted.  We used the Euclidean
  // distance for the DISSIM and COORDINATE DISTANCE functions.  Instead of
  // taking the square root (e.g. doing DISSIM) on the sum, we squared the
  // PQD[1] number (e.g. doing inverse(DISSIM)).  Also, we had difficulty
  // with the fast-exits, so we eliminated them.  All dimensions are always
  // evaluated.
  bool BoundsOverlapBall(float *x, 
    float closestPointDistanceSquared, float extent[6]);
};

#endif