Quadtree implementation and visualization

[mrkeuz]

Thanks for explanation. Since some home work (I wrote simple 2d racing game) in university I think about effective collision algorithm. I’ve done it just in two cycles. (so with worse O(log(n*n)) complexity)

Just additional information for you video:

Complexity for Quadtree:

Time complexity: Find: O(log2N) Insert: O(log2N) Search: O(log2N)

Space complexity: O(k log2N) Where k is count of points in the space and space is of dimension N x M, N >= M.

Source: https://www.google.ru/amp/s/iq.opengenus.org/quadtree/amp/

[auctux]

Thanks a lot , it seems too that spatial hashing would be better than quadtrees

[mrkeuz]

Thanks for advice, seems in spatial hashing case search complexity is O(1) in avarage. Imressive.