isWithinDistance method

bool isWithinDistance(BoundablePair initBndPair, double maxDistance)

Performs a withinDistance search on the tree node pairs. This is a different search algorithm to nearest neighbour. It can utilize the {@link BoundablePair#maximumDistance()} between tree nodes to confirm if two internal nodes must have items closer than the maxDistance, and short-circuit the search.

@param initBndPair the initial pair containing the tree root nodes @param maxDistance the maximum distance to search for @return true if two items lie within the given distance

Implementation

bool isWithinDistance(BoundablePair initBndPair, double maxDistance) {
  double distanceUpperBound = double.infinity;

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

  while (!priQ.isEmpty()) {
    // 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 > maxDistance, all other pairs
     * in the queue must have a greater distance as well.
     * So can conclude no items are within the distance
     * and terminate with result = false
     */
    if (pairDistance > maxDistance) return false;

    /**
     * If the maximum distance between the nodes
     * is less than the maxDistance,
     * than all items in the nodes must be
     * closer than the max distance.
     * Then can terminate with result = true.
     *
     * NOTE: using Envelope MinMaxDistance
     * would provide a tighter bound,
     * but not much performance improvement has been observed
     */
    if (bndPair.maximumDistance() <= maxDistance) return true;
    /**
     * If the pair items are leaves
     * then their actual distance is an upper bound.
     * Update the distanceUpperBound to reflect this
     */
    if (bndPair.isLeaves()) {
      // assert: currentDistance < minimumDistanceFound
      distanceUpperBound = pairDistance;

      /**
       * If the items are closer than maxDistance
       * can terminate with result = true.
       */
      if (distanceUpperBound <= maxDistance) return true;
    } 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, distanceUpperBound);
    }
  }
  return false;
}