nearest method

List nearest(dynamic point, int maxNodes, [ int? maxDistance ])

Find the maxNodes of nearest Nodes. Distance is calculated via Metric function. Max distance can be set with maxDistance param

Implementation

List<dynamic> nearest(point, int maxNodes, [int? maxDistance]) {
  var i, result;
  BinaryHeap bestNodes;

  if (_metric == null) {
    throw Exception(
        'Metric function undefined. Please notice that, after deserialization, you must redefine the metric function.');
  }

  bestNodes = BinaryHeap((e) {
    return -e[1];
  });

  void nearestSearch(node) {
    var bestChild,
        dimension = _dimensions[node.dimension],
        ownDistance = _metric!(point, node.obj),
        linearPoint = {},
        linearDistance,
        otherChild,
        i;

    void saveNode(node, distance) {
      bestNodes.push([node, distance]);
      if (bestNodes.size() > maxNodes) {
        bestNodes.pop();
      }
    }

    for (i = 0; i < _dimensions.length; i += 1) {
      if (i == node.dimension) {
        linearPoint[_dimensions[i]] = point[_dimensions[i]];
      } else {
        linearPoint[_dimensions[i]] = node.obj[_dimensions[i]];
      }
    }

    linearDistance = _metric!(linearPoint, node.obj);

    if (node.right == null && node.left == null) {
      if (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1]) {
        saveNode(node, ownDistance);
      }
      return;
    }

    if (node.right == null) {
      bestChild = node.left;
    } else if (node.left == null) {
      bestChild = node.right;
    } else {
      if (point[dimension] < node.obj[dimension]) {
        bestChild = node.left;
      } else {
        bestChild = node.right;
      }
    }

    nearestSearch(bestChild);

    if (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1]) {
      saveNode(node, ownDistance);
    }

    if (bestNodes.size() < maxNodes ||
        linearDistance.abs() < bestNodes.peek()[1]) {
      if (bestChild == node.left) {
        otherChild = node.right;
      } else {
        otherChild = node.left;
      }
      if (otherChild != null) {
        nearestSearch(otherChild);
      }
    }
  }

  if (maxDistance != null) {
    for (i = 0; i < maxNodes; i += 1) {
      bestNodes.push([null, maxDistance]);
    }
  }

  if (_root != null) {
    nearestSearch(_root);
  }

  result = [];

  for (i = 0; i < min(maxNodes, bestNodes.content.length); i += 1) {
    if (bestNodes.content[i][0] != null) {
      result.add([bestNodes.content[i][0].obj, bestNodes.content[i][1]]);
    }
  }

  return result;
}