retrieving node from object

[emonget]

Hi, I'm looking for a quick way to retrieve the node an object belongs to? When I use retrieve(), it returns the object for given bounds, but if I want to know which node or node path is leading to the object, is there a way other than manually traversing the tree from top to bottom? Thanks,

[timohausmann]

Hey, I think the easiest way to achieve this is to modify the retrieve function and collect the nodes too while retrieving the objects.

I put together a demo showcasing this: https://timohausmann.github.io/quadtree-js/retrieve-nodes.html

In this example the retrieve function now returns an object with both objects and nodes, like { objects: Rect[], nodes: Quadtree[] } Note that multiple nodes can be retrieved, or none if there are no matching objects. Does this work for you?

Modified branch: https://github.com/timohausmann/quadtree-js/tree/retrieve-nodes

If you use the npm package you could simply overwrite the Quadtree.prototype.retrieve function with the modified version after importing it.

[emonget]

Thanks for the quick implementation! Looking at your sample it seems it does what I'm looking for. Just in case you decided to include this feature later, I just thought in the same way getIndex retrieve the first node index, perhaps a method like getLastIndex could get the deepest node in the tree,

As an aside, I put another method which collects all nodes indexes along the path leading to the object. It only works for my specific case without objects overlaping over several nodes, and a unique path to the object Also this is a quick non optimized implementation but in case it would be useful for someone else , here it is

/**
   * Path in subtree leading to the specified element
   * @param rootNode 
   * @param targetElt 
   * @returns node indices
   */
  retrievePath(rootNode: Quadtree, targetElt: Rect) {
    if (rootNode.retrieve(targetElt).length) {
      let nodesIndices: any = [];
      let nodeIndex ;
      let currentNode = rootNode;

      // until we reach the deepest node (=leaf)
      while (currentNode.nodes.length) {
        // look for the index of the next child node containing the object
        nodeIndex = currentNode.nodes.findIndex((childNode, i) => childNode.retrieve(targetElt).length);
        nodesIndices.push(nodeIndex);
        // update current node
        currentNode = currentNode.nodes[nodeIndex];
      }

      // print found path
      console.log("Matching path found: " + nodesIndices.reduce((concat, nodeIndex) => concat + " => " + nodeIndex));
      return nodesIndices;
    } else return null;
  }