CODEWITHSUNDEEP
javaalgorithmquadtree
Kaspie
Kaspie

Reputation: 187

Should Quadtrees store points only in the children?

Though we usually define a capacity for each Quadtree, It seems like all the pseudo-code algorithms I find online don't care much for the visual number of points inside a Quadtree.

Is it necessary to redistribute the points contained by a Quadtree into its children when it's being divided?

I can't seem to implement that correctly, and the pseudo-code category of Wikipedia's Quadtree only has a comment about this (but no code):

We have to add the points/data contained into this quad array to the new quads if we want that only the last node holds the data

Upvotes: 0

Views: 474

Answers (1)

Alireza Ghasemi
Alireza Ghasemi

Reputation: 579

Assuming that the question is about a Point Quadtree, let's have a review.

Is it necessary to redistribute the points contained by a Quadtree into its children when it's being divided?

No, it's not necessary.

But, is it better?

Redistribution is mostly just something you turn on when performance measurements in your specific use case show your code runs faster with it enabled.

Thanks to @Mike'Pomax'Kamermans for the comment.

It depends on how you're using the quadtree.

Keep in mind that,

  • You would still define a capacity for each quadtree which acts as the dividing threshold.

  • It won't affect the overall time complexity.

  • More quadtrees will be present.

    Parents won't hold any points.

  • Pay the price at insertion.

    You have to redistribute the points when the capacity is met.

What's the impact on queries?

  • Out of range points are ceased faster.
  • Brute-forcefully checked points may decrease.
  • Checked quadtrees may increase.

Will it execute faster or slower compared to the other mode, really depends on the environment; Capacity, recursive stack overhead and points dispersion.

But, as you have paid a price at insertion time, it usually performs the queries faster.

Upvotes: 1

Related Questions