nearestNeighbourWithPair method
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()
];
}