text: /*=========================================================================
  
    Program:   Visualization Toolkit
    Module:    vtkKdNode.h
  
    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.
  
  =========================================================================*/
  /*----------------------------------------------------------------------------
   Copyright (c) Sandia Corporation
   See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
  ----------------------------------------------------------------------------*/
  
  /**
   * @class   vtkKdNode
   * @brief   This class represents a single spatial region
   *     in an 3D axis aligned binary spatial partitioning.  It is assumed
   *     the region bounds some set of points.  Regions are represented
   *     as nodes in a binary tree.
   *
   *
   *
   * @sa
   *      vtkKdTree vtkOBSPCuts
  */
  
  #ifndef vtkKdNode_h
  #define vtkKdNode_h
  
  #include "vtkCommonDataModelModule.h" // For export macro
  #include "vtkObject.h"
  
  class vtkCell;
  class vtkPlanesIntersection;
  
  class VTKCOMMONDATAMODEL_EXPORT vtkKdNode : public vtkObject
  {
  public:
    vtkTypeMacro(vtkKdNode, vtkObject);
    void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
  
    static vtkKdNode *New();
  
    //@{
    /**
     * Set/Get the dimension along which this region is divided.
     * (0 - x, 1 - y, 2 - z, 3 - leaf node (default)).
     */
    vtkSetMacro(Dim, int);
    vtkGetMacro(Dim, int);
    //@}
  
    /**
     * Get the location of the division plane along the axis the region
     * is divided.  See also GetDim().  The result is undertermined if
     * this node is not divided (a leaf node).
     */
    virtual double GetDivisionPosition();
  
    //@{
    /**
     * Set/Get the number of points contained in this region.
     */
    vtkSetMacro(NumberOfPoints, int);
    vtkGetMacro(NumberOfPoints, int);
    //@}
  
    //@{
    /**
     * Set/Get the bounds of the spatial region represented by this node.
     * Caller allocates storage for 6-vector in GetBounds.
     */
    void SetBounds(double x1,double x2,double y1,double y2,double z1,double z2);
    void SetBounds(const double b[6])
    {
      this->SetBounds(b[0], b[1], b[2], b[3], b[4], b[5]);
    }
    void GetBounds(double *b) const;
    //@}
  
    //@{
    /**
     * Set/Get the bounds of the points contained in this spatial region.
     * This may be smaller than the bounds of the region itself.
     * Caller allocates storage for 6-vector in GetDataBounds.
     */
    void SetDataBounds(double x1,double x2,double y1,double y2,double z1,double z2);
    void GetDataBounds(double *b) const;
    //@}
  
    /**
     * Given a pointer to NumberOfPoints points, set the DataBounds of this
     * node to the bounds of these points.
     */
    void SetDataBounds(float *v);
  
    /**
     * Get a pointer to the 3 bound minima (xmin, ymin and zmin) or the
     * 3 bound maxima (xmax, ymax, zmax).  Don't free this pointer.
     */
    double *GetMinBounds() {return this->Min;}
    double *GetMaxBounds() {return this->Max;}
  
    /**
     * Set the xmin, ymin and zmin value of the bounds of this region
     */
    void SetMinBounds(const double *mb);
  
    /**
     * Set the xmax, ymax and zmax value of the bounds of this region
     */
    void SetMaxBounds(const double *mb);
  
    /**
     * Get a pointer to the 3 data bound minima (xmin, ymin and zmin) or the
     * 3 data bound maxima (xmax, ymax, zmax).  Don't free this pointer.
     */
    double *GetMinDataBounds() {return this->MinVal;}
    double *GetMaxDataBounds() {return this->MaxVal;}
  
    /**
     * Set the xmin, ymin and zmin value of the bounds of this
     * data within this region
     */
    void SetMinDataBounds(const double *mb);
  
    /**
     * Set the xmax, ymax and zmax value of the bounds of this
     * data within this region
     */
    void SetMaxDataBounds(const double *mb);
  
    //@{
    /**
     * Set/Get the ID associated with the region described by this node.  If
     * this is not a leaf node, this value should be -1.
     */
    vtkSetMacro(ID, int);
    vtkGetMacro(ID, int);
    //@}
  
    //@{
    /**
     * If this node is not a leaf node, there are leaf nodes below it whose
     * regions represent a partitioning of this region.  The IDs of these
     * leaf nodes form a contigous set.  Set/Get the range of the IDs of
     * the leaf nodes below this node.  If this is already a leaf node, these
     * values should be the same as the ID.
     */
    vtkGetMacro(MinID, int);
    vtkGetMacro(MaxID, int);
    vtkSetMacro(MinID, int);
    vtkSetMacro(MaxID, int);
    //@}
  
    /**
     * Add the left and right children.
     */
    void AddChildNodes(vtkKdNode *left, vtkKdNode *right);
  
    /**
     * Delete the left and right children.
     */
    void DeleteChildNodes();
  
    //@{
    /**
     * Set/Get a pointer to the left child of this node.
     */
    vtkGetObjectMacro(Left, vtkKdNode);
    void SetLeft(vtkKdNode* left);
    //@}
  
    //@{
    /**
     * Set/Get a pointer to the right child of this node.
     */
    vtkGetObjectMacro(Right, vtkKdNode);
    void SetRight(vtkKdNode *right);
    //@}
  
    //@{
    /**
     * Set/Get a pointer to the parent of this node.
     */
    vtkGetObjectMacro(Up, vtkKdNode);
    void SetUp(vtkKdNode* up);
    //@}
  
    /**
     * Return 1 if this spatial region intersects the axis-aligned box given
     * by the bounds passed in.  Use the possibly smaller bounds of the points
     * within the region if useDataBounds is non-zero.
     */
    int IntersectsBox(double x1,double x2,double y1,double y2,double z1,double z2,
                      int useDataBounds);
  
    /**
     * Return 1 if this spatial region intersects a sphere described by
     * it's center and the square of it's radius. Use the possibly smaller
     * bounds of the points within the region if useDataBounds is non-zero.
     */
    int IntersectsSphere2(double x, double y, double z, double rSquared,
                          int useDataBounds);
  
    /**
     * A vtkPlanesIntersection object represents a convex 3D region bounded
     * by planes, and it is capable of computing intersections of
     * boxes with itself.  Return 1 if this spatial region intersects
     * the spatial region described by the vtkPlanesIntersection object.
     * Use the possibly smaller bounds of the points within the region
     * if useDataBounds is non-zero.
     */
    int IntersectsRegion(vtkPlanesIntersection *pi, int useDataBounds);
  
    /**
     * Return 1 if the cell specified intersects this region.  If you
     * already know the ID of the region containing the cell's centroid,
     * provide that as an argument.  If you already know the bounds of the
     * cell, provide that as well, in the form of xmin,xmax,ymin,ymax,zmin,
     * zmax.  Either of these may speed the calculation.
     * Use the possibly smaller bounds of the points within the region
     * if useDataBounds is non-zero.
     */
    int IntersectsCell(vtkCell *cell, int useDataBounds,
                       int cellRegion=-1, double *cellBounds=nullptr);
  
    /**
     * Return 1 if this spatial region entirely contains a box specified
     * by it's bounds. Use the possibly smaller
     * bounds of the points within the region if useDataBounds is non-zero.
     */
    int ContainsBox(double x1,double x2,double y1,double y2,double z1,double z2,
                    int useDataBounds);
  
    /**
     * Return 1 if this spatial region entirely contains the given point.
     * Use the possibly smaller bounds of the points within the region
     * if useDataBounds is non-zero.
     */
    int ContainsPoint(double x, double y, double z, int useDataBounds);
  
    /**
     * Calculate the distance squared from any point to the boundary of this
     * region.  Use the boundary of the points within the region if useDataBounds
     * is non-zero.
     */
    double GetDistance2ToBoundary(double x, double y, double z, int useDataBounds);
  
    /**
     * Calculate the distance squared from any point to the boundary of this
     * region.  Use the boundary of the points within the region if useDataBounds
     * is non-zero.  Set boundaryPt to the point on the boundary.
     */
    double GetDistance2ToBoundary(double x, double y, double z, double *boundaryPt,
                                  int useDataBounds);
  
    /**
     * Calculate the distance from the specified point (which is required to
     * be inside this spatial region) to an interior boundary.  An interior
     * boundary is one that is not also an boundary of the entire space
     * partitioned by the tree of vtkKdNode's.
     */
    double GetDistance2ToInnerBoundary(double x, double y, double z);
  
    //@{
    /**
     * For debugging purposes, print out this node.
     */
    void PrintNode(int depth);
    void PrintVerboseNode(int depth);
    //@}
  
  protected:
  
    vtkKdNode();
    ~vtkKdNode() VTK_OVERRIDE;
  
  private:
  
    double _GetDistance2ToBoundary(
      double x, double y, double z, double *boundaryPt,
      int innerBoundaryOnly, int useDataBounds);
  
    double Min[3];       // spatial bounds of node
    double Max[3];       // spatial bounds of node
    double MinVal[3];    // spatial bounds of data within node
    double MaxVal[3];    // spatial bounds of data within node
    int NumberOfPoints;
  
    vtkKdNode *Up;
  
    vtkKdNode *Left;
    vtkKdNode *Right;
  
    int Dim;
  
    int ID;        // region id
  
    int MinID;
    int MaxID;
  
    vtkKdNode(const vtkKdNode&) VTK_DELETE_FUNCTION;
    void operator=(const vtkKdNode&) VTK_DELETE_FUNCTION;
  };
  
  #endif
  