Quadtree Demonstrator

I created a similar sketch 3 years ago for Java mode but now I am learning Typescript and Javascript I decided it was time to recreate it for p5.js

On the way I improved the OO design and implementation of the QuadPartition class.
Anyway I hope you have some fun playing with this.

9 Likes

@quark Hello sir This is a creative work

Very cool sketch. I love the statistics.

Have you tried comparing the quadtree performance against a simple flat grid? I’ve been running simulations of tens of thousands of particles (https://twitter.com/scdollins/status/1530233496874012673) and have tried a variety of collision detectors and a flat grid of linked lists of objects per cell seems to have worked best for my applications. And it also scales nicely to 3D https://twitter.com/scdollins/status/1564615779269496844.

Dealing with a wide range of object sizes is the biggest difficulty since each object has search out to the range of the largest object it might touch. When the objects are the same size, you can set the grid spacing to the object diameter and only need to check 2x2 cells, but with bigger objects in the mix, you have to search wider. This can be helped by sorting the objects by size and entering them from smallest to largest, so each object only has to test out to the range of its own diameter.

2 Likes

Although I have used simple flat grids before I haven’t done any performance comparisons.

My main reason for doing this was to create the visual simulation of a quadtree at work and along the way enhance my knowledge of Javascript and TypeScript.

I don’t know why the pane tab and button are distorted when run in this forum if anyone has an idea please let me know.

You can see this sketch in its true glory at OpenProcessing and my website

1 Like