Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. Qt Development
  3. General and Desktop
  4. Searching for nearest node in n-ary tree?
QtWS25 Last Chance

Searching for nearest node in n-ary tree?

Scheduled Pinned Locked Moved Unsolved General and Desktop
treen-ary-treesearch
3 Posts 3 Posters 1.7k Views
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • A Offline
    A Offline
    alogim
    wrote on 28 Feb 2016, 20:56 last edited by
    #1

    I've got a tree data structure. The tree is composed of nodes, each like this:

    struct node
    {
      int x, y;
      QLineF edge;
      node* parent;
      QVector<node*> children;
    }
    

    x and y represent the node coordinates, edge is the link between the parent and the node itself, parent is the node's parent and children represent node's children.
    The tree grows when my application runs, reaching dimensions of tenths of thousands of nodes. Now, my application generates a random node in a certain space and must find the nearest node in the tree. Each node may potentially have thousands of children.
    At first I used a QVector in which I stored pointers to the nodes in the tree, and I simply iterated over the whole QVector to find the node that is the nearest to the generated one.
    Then I changed approach and I now start from the root node and visit each children and so on to find the nearest node, by simply accessing the pointers.
    In each case, anyway, I need to visit all the nodes since I do not know if the nearest node is the first one or the last one.

    Using a QElapsedTimer tough, I noticed that this last approach is almost always much much slower than the simpler iteration over the QVector.
    So, shall I keep the QVector approach? If, on one hand, it is faster, on the other hand it occupies more memory since it stores tenth of thousands of pointers to nodes.

    K 1 Reply Last reply 28 Feb 2016, 23:29
    0
    • M Offline
      M Offline
      mrjj
      Lifetime Qt Champion
      wrote on 28 Feb 2016, 21:11 last edited by
      #2

      hi
      When using only pointers it becomes sort of linked
      list which can be slower in many cases with modern
      hardware.
      You could have a look on
      https://www.youtube.com/watch?v=YQs6IC-vgmo
      If u are interested in it.

      I would keep the the vector approach if the extra memory use is acceptable.

      1 Reply Last reply
      1
      • A alogim
        28 Feb 2016, 20:56

        I've got a tree data structure. The tree is composed of nodes, each like this:

        struct node
        {
          int x, y;
          QLineF edge;
          node* parent;
          QVector<node*> children;
        }
        

        x and y represent the node coordinates, edge is the link between the parent and the node itself, parent is the node's parent and children represent node's children.
        The tree grows when my application runs, reaching dimensions of tenths of thousands of nodes. Now, my application generates a random node in a certain space and must find the nearest node in the tree. Each node may potentially have thousands of children.
        At first I used a QVector in which I stored pointers to the nodes in the tree, and I simply iterated over the whole QVector to find the node that is the nearest to the generated one.
        Then I changed approach and I now start from the root node and visit each children and so on to find the nearest node, by simply accessing the pointers.
        In each case, anyway, I need to visit all the nodes since I do not know if the nearest node is the first one or the last one.

        Using a QElapsedTimer tough, I noticed that this last approach is almost always much much slower than the simpler iteration over the QVector.
        So, shall I keep the QVector approach? If, on one hand, it is faster, on the other hand it occupies more memory since it stores tenth of thousands of pointers to nodes.

        K Offline
        K Offline
        kshegunov
        Moderators
        wrote on 28 Feb 2016, 23:29 last edited by kshegunov
        #3

        @alogim
        You're sort of naively using the simplest form of the tree data structure. If I understand your question correctly you should look at some BSP tree structure implementations, as they seem to suit your case quite well.

        Read and abide by the Qt Code of Conduct

        1 Reply Last reply
        0

        3/3

        28 Feb 2016, 23:29

        • Login

        • Login or register to search.
        3 out of 3
        • First post
          3/3
          Last post
        0
        • Categories
        • Recent
        • Tags
        • Popular
        • Users
        • Groups
        • Search
        • Get Qt Extensions
        • Unsolved