public void splitNode ( KDTreeNode node , int numNodesCreated , double [ ] [ ] nodeRanges , double [ ] [ ] universe ) throws Exception { correctlyInitialized ( ) ; int splitDim = widestDim ( nodeRanges , universe ) ; double splitVal = m_EuclideanDistance . getMiddle ( nodeRanges [ splitDim ] ) ; 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 " + "MidPointofWidestDim splitting method. Please " + "check code." ) ; else throw new Exception ( "Right child is empty in node " + node . m_NodeNumber + ". Not possible with " + "MidPointofWidestDim splitting method. Please " + "check code." ) ; } node . m_SplitDim = splitDim ; node . m_SplitValue = splitVal ; node . m_Left = new KDTreeNode ( numNodesCreated + 1 , node . m_Start , rightStart - 1 , m_EuclideanDistance . initializeRanges ( m_InstList , node . m_Start , rightStart - 1 ) ) ; node . m_Right = new KDTreeNode ( numNodesCreated + 2 , rightStart , node . m_End , m_EuclideanDistance . initializeRanges ( m_InstList , rightStart , node . m_End ) ) ; }
Splits a node into two based on the midpoint value of the dimension in which the points have the widest spread . After splitting two new nodes are created and correctly initialised . And node . left and node . right are set appropriately .