public void splitNode(KDTreeNode node,int numNodesCreated,double[][] nodeRanges,double[][] universe) throws Exception {
  correctlyInitialized();
  if (node.m_NodesRectBounds == null) {
    node.m_NodesRectBounds=new double[2][node.m_NodeRanges.length];
    for (int i=0; i < node.m_NodeRanges.length; i++) {
      node.m_NodesRectBounds[MIN][i]=node.m_NodeRanges[i][MIN];
      node.m_NodesRectBounds[MAX][i]=node.m_NodeRanges[i][MAX];
    }
  }
  double maxRectWidth=Double.NEGATIVE_INFINITY, maxPtWidth=Double.NEGATIVE_INFINITY, tempval;
  int splitDim=-1, classIdx=m_Instances.classIndex();
  for (int i=0; i < node.m_NodesRectBounds[0].length; i++) {
    if (i == classIdx)     continue;
    tempval=node.m_NodesRectBounds[MAX][i] - node.m_NodesRectBounds[MIN][i];
    if (m_NormalizeNodeWidth) {
      tempval=tempval / universe[i][WIDTH];
    }
    if (tempval > maxRectWidth && node.m_NodeRanges[i][WIDTH] > 0.0)     maxRectWidth=tempval;
  }
  for (int i=0; i < node.m_NodesRectBounds[0].length; i++) {
    if (i == classIdx)     continue;
    tempval=node.m_NodesRectBounds[MAX][i] - node.m_NodesRectBounds[MIN][i];
    if (m_NormalizeNodeWidth) {
      tempval=tempval / universe[i][WIDTH];
    }
    if (tempval >= maxRectWidth * (1 - ERR) && node.m_NodeRanges[i][WIDTH] > 0.0) {
      if (node.m_NodeRanges[i][WIDTH] > maxPtWidth) {
        maxPtWidth=node.m_NodeRanges[i][WIDTH];
        if (m_NormalizeNodeWidth)         maxPtWidth=maxPtWidth / universe[i][WIDTH];
        splitDim=i;
      }
    }
  }
  double splitVal=node.m_NodesRectBounds[MIN][splitDim] + (node.m_NodesRectBounds[MAX][splitDim] - node.m_NodesRectBounds[MIN][splitDim]) * 0.5;
  if (splitVal < node.m_NodeRanges[splitDim][MIN])   splitVal=node.m_NodeRanges[splitDim][MIN];
 else   if (splitVal >= node.m_NodeRanges[splitDim][MAX])   splitVal=node.m_NodeRanges[splitDim][MAX] - node.m_NodeRanges[splitDim][WIDTH] * 0.001;
  int rightStart=rearrangePoints(m_InstList,node.m_Start,node.m_End,splitDim,splitVal);
  if (rightStart == node.m_Start || rightStart > node.m_End) {
    if (rightStart == node.m_Start)     throw new Exception("Left child is empty in node " + node.m_NodeNumber + ". Not possible with "+ "SlidingMidPointofWidestSide splitting method. Please "+ "check code.");
 else     throw new Exception("Right child is empty in node " + node.m_NodeNumber + ". Not possible with "+ "SlidingMidPointofWidestSide splitting method. Please "+ "check code.");
  }
  node.m_SplitDim=splitDim;
  node.m_SplitValue=splitVal;
  double[][] widths=new double[2][node.m_NodesRectBounds[0].length];
  System.arraycopy(node.m_NodesRectBounds[MIN],0,widths[MIN],0,node.m_NodesRectBounds[MIN].length);
  System.arraycopy(node.m_NodesRectBounds[MAX],0,widths[MAX],0,node.m_NodesRectBounds[MAX].length);
  widths[MAX][splitDim]=splitVal;
  node.m_Left=new KDTreeNode(numNodesCreated + 1,node.m_Start,rightStart - 1,m_EuclideanDistance.initializeRanges(m_InstList,node.m_Start,rightStart - 1),widths);
  widths=new double[2][node.m_NodesRectBounds[0].length];
  System.arraycopy(node.m_NodesRectBounds[MIN],0,widths[MIN],0,node.m_NodesRectBounds[MIN].length);
  System.arraycopy(node.m_NodesRectBounds[MAX],0,widths[MAX],0,node.m_NodesRectBounds[MAX].length);
  widths[MIN][splitDim]=splitVal;
  node.m_Right=new KDTreeNode(numNodesCreated + 2,rightStart,node.m_End,m_EuclideanDistance.initializeRanges(m_InstList,rightStart,node.m_End),widths);
}

public void splitNode ( KDTreeNode node , int numNodesCreated , double [ ] [ ] nodeRanges , double [ ] [ ] universe ) throws Exception { correctlyInitialized ( ) ; if ( node . m_NodesRectBounds == null ) { node . m_NodesRectBounds = new double [ 2 ] [ node . m_NodeRanges . length ] ; for ( int i = 0 ; i < node . m_NodeRanges . length ; i ++ ) { node . m_NodesRectBounds [ MIN ] [ i ] = node . m_NodeRanges [ i ] [ MIN ] ; node . m_NodesRectBounds [ MAX ] [ i ] = node . m_NodeRanges [ i ] [ MAX ] ; } } double maxRectWidth = Double . NEGATIVE_INFINITY , maxPtWidth = Double . NEGATIVE_INFINITY , tempval ; int splitDim = - 1 , classIdx = m_Instances . classIndex ( ) ; for ( int i = 0 ; i < node . m_NodesRectBounds [ 0 ] . length ; i ++ ) { if ( i == classIdx ) continue ; tempval = node . m_NodesRectBounds [ MAX ] [ i ] - node . m_NodesRectBounds [ MIN ] [ i ] ; if ( m_NormalizeNodeWidth ) { tempval = tempval / universe [ i ] [ WIDTH ] ; } if ( tempval > maxRectWidth && node . m_NodeRanges [ i ] [ WIDTH ] > 0.0 ) maxRectWidth = tempval ; } for ( int i = 0 ; i < node . m_NodesRectBounds [ 0 ] . length ; i ++ ) { if ( i == classIdx ) continue ; tempval = node . m_NodesRectBounds [ MAX ] [ i ] - node . m_NodesRectBounds [ MIN ] [ i ] ; if ( m_NormalizeNodeWidth ) { tempval = tempval / universe [ i ] [ WIDTH ] ; } if ( tempval >= maxRectWidth * ( 1 - ERR ) && node . m_NodeRanges [ i ] [ WIDTH ] > 0.0 ) { if ( node . m_NodeRanges [ i ] [ WIDTH ] > maxPtWidth ) { maxPtWidth = node . m_NodeRanges [ i ] [ WIDTH ] ; if ( m_NormalizeNodeWidth ) maxPtWidth = maxPtWidth / universe [ i ] [ WIDTH ] ; splitDim = i ; } } } double splitVal = node . m_NodesRectBounds [ MIN ] [ splitDim ] + ( node . m_NodesRectBounds [ MAX ] [ splitDim ] - node . m_NodesRectBounds [ MIN ] [ splitDim ] ) * 0.5 ; if ( splitVal < node . m_NodeRanges [ splitDim ] [ MIN ] ) splitVal = node . m_NodeRanges [ splitDim ] [ MIN ] ; else if ( splitVal >= node . m_NodeRanges [ splitDim ] [ MAX ] ) splitVal = node . m_NodeRanges [ splitDim ] [ MAX ] - node . m_NodeRanges [ splitDim ] [ WIDTH ] * 0.001 ; int rightStart = rearrangePoints ( m_InstList , node . m_Start , node . m_End , splitDim , splitVal ) ; if ( rightStart == node . m_Start || rightStart > node . m_End ) { if ( rightStart == node . m_Start ) throw new Exception ( "Left child is empty in node " + node . m_NodeNumber + ". Not possible with " + "SlidingMidPointofWidestSide splitting method. Please " + "check code." ) ; else throw new Exception ( "Right child is empty in node " + node . m_NodeNumber + ". Not possible with " + "SlidingMidPointofWidestSide splitting method. Please " + "check code." ) ; } node . m_SplitDim = splitDim ; node . m_SplitValue = splitVal ; double [ ] [ ] widths = new double [ 2 ] [ node . m_NodesRectBounds [ 0 ] . length ] ; System . arraycopy ( node . m_NodesRectBounds [ MIN ] , 0 , widths [ MIN ] , 0 , node . m_NodesRectBounds [ MIN ] . length ) ; System . arraycopy ( node . m_NodesRectBounds [ MAX ] , 0 , widths [ MAX ] , 0 , node . m_NodesRectBounds [ MAX ] . length ) ; widths [ MAX ] [ splitDim ] = splitVal ; node . m_Left = new KDTreeNode ( numNodesCreated + 1 , node . m_Start , rightStart - 1 , m_EuclideanDistance . initializeRanges ( m_InstList , node . m_Start , rightStart - 1 ) , widths ) ; widths = new double [ 2 ] [ node . m_NodesRectBounds [ 0 ] . length ] ; System . arraycopy ( node . m_NodesRectBounds [ MIN ] , 0 , widths [ MIN ] , 0 , node . m_NodesRectBounds [ MIN ] . length ) ; System . arraycopy ( node . m_NodesRectBounds [ MAX ] , 0 , widths [ MAX ] , 0 , node . m_NodesRectBounds [ MAX ] . length ) ; widths [ MIN ] [ splitDim ] = splitVal ; node . m_Right = new KDTreeNode ( numNodesCreated + 2 , rightStart , node . m_End , m_EuclideanDistance . initializeRanges ( m_InstList , rightStart , node . m_End ) , widths ) ; }
splits a node into two based on the midpoint value of the dimension in which the node ' s rectangle is widest . if after splitting one side is empty then it is slided towards the non - empty side until there is at least one point on the empty side . the two nodes created after the whole splitting are correctly initialised . and , node . left and node . right are set appropriately .
