Quadtree for 2D collision detection

by

Your quadtree structure isn’t optimal. You’re right to store 4 subtrees per node, but actual objects should only be stored inside the leaves, not inner nodes. Therefore the collection holding the actual objects needs to be moved to the leaves.

Let’s have a look at the implementation of the operations:

  1. Insert an object into the quadtree:
    Check if the object intersects the current node. If so, recurse. If you’ve reached the leaf level, insert the object into the collection.
  2. Delete an object from the quadtree:
    Execute the exact same steps as if inserting the object, but when you’ve reached the leaf level delete it from the collection.
  3. Test if an object intersects any object inside the quadtree:
    Execute the exact same steps as if inserting the object, but when you’ve reached the leaf level check for collision with all the objects in the collection.
  4. Test for all collisions between all objects inside the quadtree:
    For every object in the quadtree execute the single object collision test.
  5. Update the quadtree:
    Delete all objects from the quadtree whose position has been modified and insert them again.

This has several advantages:

  • By only storing objects in the leaves it is very easy to handle operations on the quadtree (fewer special cases)
  • The quadtree can have leaves with different depth, thus allowing you to adapt the density of the quadtree depending on the spatial region it covers. This adaption can happen at runtime, thus keeping the object/node ratio optimal.

Only disatvantage:

  • Objects can belong to several collections inside the quadtree. You’re going to need an extra linear collection outside the quadtree to enumerate every object without duplicates.

More Related Contents:

  1. Efficient (and well explained) implementation of a Quadtree for 2D collision detection [closed]
  2. How do I prove or disprove that this function is Ω(n^1.5)?
  3. How does a hash table work?
  4. How do I express mutually recursive data structures in safe Rust?
  5. Firebase data structure and url
  6. Implement graph-like data structure in Rust
  7. lenses, fclabels, data-accessor – which library for structure access and mutation is better
  8. Advantages of Binary Search Trees over Hash Tables
  9. Difference between binary tree and binary search tree
  10. Data structure: insert, remove, contains, get random element, all at O(1)
  11. Are duplicate keys allowed in the definition of binary search trees?
  12. Searching a number in a rotated sorted Array
  13. Efficient implementation of immutable (double) LinkedList
  14. Why hashmap lookup is O(1) i.e. constant time?
  15. What is the left-child, right-sibling representation of a tree? Why would you use it?
  16. Test whether a list contains a specific value in Clojure
  17. Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”?
  18. Chained Hash Tables vs. Open-Addressed Hash Tables
  19. Linked List vs Vector
  20. Data structure for quick time interval look up
  21. Is using flexible array members in C bad practice?
  22. Why start an ArrayList with an initial capacity?
  23. Passing data of a non-primitive type between activities in android
  24. How do I make and use a Queue in Objective-C?
  25. Implementing -hash / -isEqual: / -isEqualTo…: for Objective-C collections
  26. Why are hash table expansions usually done by doubling the size?
  27. Table like java data structure
  28. Why are entries in addition order in a .Net Dictionary?
  29. Finding the shortest path nodes with breadth first search
  30. Why do hash keys have different order when printing?

Leave a Comment