nearestNeighbourWithPair method

List<Object>? nearestNeighbourWithPair(BoundablePair initBndPair)

Implementation

List<Object>? nearestNeighbourWithPair(BoundablePair initBndPair) {
  double distanceLowerBound = double.infinity;
  BoundablePair? minPair = null;

  // initialize search queue
  PriorityQueue priQ = new PriorityQueue();
  priQ.add(initBndPair);

  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 pair in the queue
     * is >= current minimum distance, 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
      distanceLowerBound = pairDistance;
      minPair = bndPair;
    } else {
      /**
       * Otherwise, expand one side of the pair,
       * and insert the expanded pairs into the queue.
       * The choice of which side to expand is determined heuristically.
       */
      bndPair.expandToQueue(priQ, distanceLowerBound);
    }
  }
  if (minPair == null) return null;
  // done - return items with min distance
  return [
    (minPair.getBoundable(0) as ItemBoundable).getItem(),
    (minPair.getBoundable(1) as ItemBoundable).getItem()
  ];
}