Danni111111
Danni111111

Reputation: 45

Disadvantages to unevenly splitting nodes in a quadtree?

Scenario

I am using a quadtree to store positional data on objects that represent asteroids/planets/stars in a program to model a realistic solar system with realistic distances. The use of a quadtree was to allow a fast search for the correct object to select based on the user's current mouse position.

Issue

I noticed the default implementation of a quadtree (which splits nodes equally) was incredibly inefficient when dealing with this scenario:

distance between two objects <<< total distance covered by the quadtree

In my case, adding just two objects about 1km apart to the quadtree which is covering a total distance of 15'000'000'000km for x and y requires the generation of about ~140 nodes.

Solution

To try and reduce the number of nodes required per object in the quadtree, I changed the splitting logic to split at the point between the new object and the current node's object.

Result

Changing the splitting logic has reduced the number of nodes required, with a massive improvement in my scenario.

Example Default Quadtree (equal split)

Default (equal split)

Example New Quadtree (split dependend on old and new point position)

New (split dependend on old and new point position)

My Question

While I haven't seen any issues arise yet from the new logic I used for node splitting, I don't understand why the default implementation of quadtrees split their nodes equally. Is it not always better to have the split depend on the new and existing point? Would it not always reduce the number of nodes required, and therefore improve the efficiency of the quadtree in general?

I can only assume I have missed something here, possibly incredibly obvious.

Thanks in advance.

Upvotes: 0

Views: 108

Answers (0)

Related Questions