nearestNeighbourKWithMaxD method

List<Object> nearestNeighbourKWithMaxD(BoundablePair initBndPair, double maxDistance, int k)

Implementation

List<Object> nearestNeighbourKWithMaxD(
    BoundablePair initBndPair, double maxDistance, int k) {
  double distanceLowerBound = maxDistance;

  // initialize internal structures
  PriorityQueue priQ = new PriorityQueue();

  // initialize queue
  priQ.add(initBndPair);

  PriorityQueue kNearestNeighbors = new PriorityQueue();

  while (!priQ.isEmpty() && distanceLowerBound >= 0.0) {
    // pop head of queue and expand one side of pair
    BoundablePair bndPair = priQ.poll() as BoundablePair;
    double pairDistance = bndPair.getDistance();

    /**
     * If the distance for the first node in the queue
     * is >= the current maximum distance in the k queue , all other nodes
     * in the queue must also have a greater distance.
     * So the current minDistance must be the true minimum,
     * and we are done.
     */
    if (pairDistance >= distanceLowerBound) {
      break;
    }
    /**
     * If the pair members are leaves
     * then their distance is the exact lower bound.
     * Update the distanceLowerBound to reflect this
     * (which must be smaller, due to the test
     * immediately prior to this).
     */
    if (bndPair.isLeaves()) {
      // assert: currentDistance < minimumDistanceFound

      if (kNearestNeighbors.size() < k) {
        kNearestNeighbors.add(bndPair);
      } else {
        BoundablePair bp1 = kNearestNeighbors.peek() as BoundablePair;
        if (bp1.getDistance() > pairDistance) {
          kNearestNeighbors.poll();
          kNearestNeighbors.add(bndPair);
        }
        /*
  		   * minDistance should be the farthest point in the K nearest neighbor queue.
  		   */
        BoundablePair bp2 = kNearestNeighbors.peek() as BoundablePair;
        distanceLowerBound = bp2.getDistance();
      }
    } else {
      /**
       * Otherwise, expand one side of the pair,
       * (the choice of which side to expand is heuristically determined)
       * and insert the new expanded pairs into the queue
       */
      bndPair.expandToQueue(priQ, distanceLowerBound);
    }
  }
  // done - return items with min distance

  return getItems(kNearestNeighbors);
}