Unit tests for KdTree

Jump to navigation Jump to search
Revision as of 27 May 2012 at 21:21.
The highlighted comment was created in this revision.

Unit tests for KdTree

Hello Rednaxela,

I just converted your KD-tree Java code to C#. Do you have unit tests for KD-Tree? They would allow me to test if the conversion succeded.

    Ojd00:05, 6 May 2012

    I don't know if you could modified it to run the C# implementation, but K-NN algorithm benchmark has an accuracy checker with linear search, as with performance benchmark. You can give it a try.

      Nat Pavasant13:59, 7 May 2012
       

      Yeah, I didn't use any unit tests when writing the KD-Tree, just some functional tests. The most thorough of which is from the K-NN algorithm benchmark that Nat and I wrote. It repeatedly tests the KD-Trees with a very large set of random set of points against known-good results from a very very simple linear-time k-nn search.

        Rednaxela17:31, 8 May 2012
         

        I just published my C# implementation of a KD-Tree based on Rednaxela's java implementation here on robowiki.

          Ojd16:02, 22 May 2012
           

          Hi Rednaxela & Ojd,

          I'd like to have remove functionality and added the method below to KdNode. It is based on Ojd's C# variant and adjusts. KdNode needs and extra field: parent. It seems to do what I want, but feel not confident about some points:

          • do the bounds of parent nodes to be adjusted as well?
          • how to add it nicely to the NearestNeighborIterator?
          • what if you want to re-weight after n removals? (remove remainder and add again?)

          Thanks, Arie

              public boolean remove(double[] point, T value)
              {
                  KdNode<T> cursor = this;
                  while (!cursor.isLeaf()) {
                      if (point[cursor.splitDimension] > cursor.splitValue) {
                          cursor = cursor.left;
                      } else {
                          cursor = cursor.right;
                      }
                  }
                  for (int i = 0; i < cursor.size; i++) {
                      if (cursor.data[i].equals(value)) {
                          double[] cursorPoint = cursor.points[i];
                          // remove this points
                          cursor.data = ArrayUtil.remove(cursor.data, i);
                          cursor.points = ArrayUtil.remove(cursor.points, i);
          
                          // fix tree size all the way up to the root
                          KdNode<T> parent = cursor.parent;
                          do {
                              parent.size--;
                              parent = cursor.parent;
                          } while (parent != null);
          
          
                          // adjust _minBound and _maxBound after removing an item.
                          if(cursor.points.length > 0){
                              for (int j = 0; j < dimensions; j++) {
                                  if (Double.isNaN(cursorPoint[j])) {
                                      if (!Double.isNaN(minBound[j]) || !Double.isNaN(maxBound[j])) {
                                          singlePoint = false;
                                      }
                                      minBound[j] = Double.NaN;
                                      maxBound[j] = Double.NaN;
                                  }
                                  else if (minBound[j] > cursorPoint[j]) {
                                      minBound[j] = cursorPoint[i];
                                      singlePoint = false;
                                  }
                                  else if (maxBound[j] < cursorPoint[i]) {
                                      maxBound[j] = cursorPoint[i];
                                      singlePoint = false;
                                  }
                              }
                          }
                          else{
                              // last point at this cursor was removed.
                              minBound = null;
                              maxBound = null;
                          }
                          return true;
                      }
                  }
                  return false;
              }
          
            Arie22:21, 27 May 2012