private Node buildNode ( int begin , int end ) { int d = keys [ 0 ] . length ; // Allocate the node Node node = new Node ( ) ; // Fill in basic info node . count = end - begin ; node . index = begin ; // Calculate the bounding box double [ ] lowerBound = new double [ d ] ; double [ ] upperBound = new double [ d ] ; for ( int i = 0 ; i < d ; i ++ ) { lowerBound [ i ] = keys [ index [ begin ] ] [ i ] ; upperBound [ i ] = keys [ index [ begin ] ] [ i ] ; } for ( int i = begin + 1 ; i < end ; i ++ ) { for ( int j = 0 ; j < d ; j ++ ) { double c = keys [ index [ i ] ] [ j ] ; if ( lowerBound [ j ] > c ) { lowerBound [ j ] = c ; } if ( upperBound [ j ] < c ) { upperBound [ j ] = c ; } } } // Calculate bounding box stats double maxRadius = - 1 ; for ( int i = 0 ; i < d ; i ++ ) { double radius = ( upperBound [ i ] - lowerBound [ i ] ) / 2 ; if ( radius > maxRadius ) { maxRadius = radius ; node . split = i ; node . cutoff = ( upperBound [ i ] + lowerBound [ i ] ) / 2 ; } } // If the max spread is 0, make this a leaf node if ( maxRadius == 0 ) { node . lower = node . upper = null ; return node ; } // Partition the dataset around the midpoint in this dimension. The // partitioning is done in-place by iterating from left-to-right and // right-to-left in the same way that partioning is done in quicksort. int i1 = begin , i2 = end - 1 , size = 0 ; while ( i1 <= i2 ) { boolean i1Good = ( keys [ index [ i1 ] ] [ node . split ] < node . cutoff ) ; boolean i2Good = ( keys [ index [ i2 ] ] [ node . split ] >= node . cutoff ) ; if ( ! i1Good && ! i2Good ) { int temp = index [ i1 ] ; index [ i1 ] = index [ i2 ] ; index [ i2 ] = temp ; i1Good = i2Good = true ; } if ( i1Good ) { i1 ++ ; size ++ ; } if ( i2Good ) { i2 -- ; } } // Create the child nodes node . lower = buildNode ( begin , begin + size ) ; node . upper = buildNode ( begin + size , end ) ; return node ; }
Build a k - d tree from the given set of dataset .