Quad & Oct Trees - Data Structures For Performance

Quad and Oct Trees (Octree) are balanced tree data structures which can be used to greatly speed up the performance of your program. By partitioning your data spatially, these trees allow for quick exclusion of parts of your data allowing for your algorithm to complete sooner.
Knowing when and how to use trees is an essential part of computer science.
Timeline:
0:00 Intro
0:25 Linear Search
0:50 Building an Oct Tree
1:41 Tree Representation
2:04 AABB Test
2:28 Use Cases
3:11 Caveats
#ComputerScience, #DataStructures, #OctTrees, #QuadTrees, #Performance
- Computer: amzn.to/2YxbZKw
- Monitor: amzn.to/3b1Thjo
- Laptop Dock: amzn.to/2EDuSEo
- Daily driver keyboard: amzn.to/3jhikSa
- Ergonomic Keyboard: amzn.to/3gvYzor
- Kneeling Chair (save's your back): amzn.to/2MAKywn
- Microphone (Excellent noise rejection for video calls): amzn.to/2XcpDSk
- Webcam: amzn.to/2Xb7dkN

Пікірлер: 26

  • @ademord
    @ademord3 жыл бұрын

    Great concise and organized video. Also loved you marked the separate regions in the video.

  • @tompat9166
    @tompat9166 Жыл бұрын

    Got it after 90 sec, excellent explanation. Thanks for the upload.

  • @gaming4fun419
    @gaming4fun4192 жыл бұрын

    Still waiting for the future episodes ;)

  • @matthieumoinvaziri9408
    @matthieumoinvaziri94082 жыл бұрын

    It's a very good introduction with smart contextualisation ! Good job ! 👌

  • @AngusTatchell
    @AngusTatchell2 жыл бұрын

    Great vid! Very clear and a good steer for my first nbody sim

  • @FilledStacks
    @FilledStacks3 жыл бұрын

    Nice. I used this for the collision detection the first time I had to build my own game engine. It significantly reduces the number of checks you need to do for a collision. EDIT: I write this before the use cases section haha! It works for errrrrthang you mentioned.

  • @pixeldevlog
    @pixeldevlog2 жыл бұрын

    Thanks, awesome video

  • @gio3061
    @gio3061 Жыл бұрын

    Legend, doesn't waste 1 second. Thanks!

  • @lemonke8132
    @lemonke8132 Жыл бұрын

    wow this video is great, subbed

  • @parkerrex
    @parkerrex3 жыл бұрын

    Nice one Gish. SUBBED.

  • @310gowthamsagar5
    @310gowthamsagar56 ай бұрын

    awesome content.

  • @MDLeide
    @MDLeide23 күн бұрын

    Nice video.

  • @martinelfast9763
    @martinelfast97632 жыл бұрын

    @Kayle Thanks for a great video on a very interesting topic! I would love to see a video on Dual Contouring from you, if you are not familiar its very interesting even scraching the surface, its used as a technique to create meshes. Also if I may ask what is the background music? Regards M

  • @wellingtoncarvalho1621
    @wellingtoncarvalho16216 ай бұрын

    Awesome! Maybe a video about AABB Trees?

  • @browniris6289
    @browniris6289 Жыл бұрын

    interested in the GIS bit, but you havent uploaded any episode. Do you plan on making them?

  • @neoBiteWave123
    @neoBiteWave123 Жыл бұрын

    ok good explanation i love it, but... how can i write the coding of the quadtree and octree. in essencial like a binary tree but every node has 4 nodes, ok but how can i write by the coding divide itself between 4 squares until of infinite only in the place where the random point is?

  • @FlareGunDebate
    @FlareGunDebate4 ай бұрын

    I tried to store triangles in a quadtree and it was eh brutal. Any ideas on how to spatial partition a triangulation mesh?

  • @codyheiner3636
    @codyheiner36362 жыл бұрын

    Quad/octrees vs kd-trees? What are the advantages of each, when do we choose one over the other?

  • @jonasschindler4628

    @jonasschindler4628

    2 жыл бұрын

    As far as I understood it, kd-trees disect the underlying space in an arbitrary amount of partitions, thus k, whilst Quad/octrees are somewhat a subset of kd-trees, where the space is disected into exactly 4/8 partitions.

  • @codyheiner3636

    @codyheiner3636

    2 жыл бұрын

    @@jonasschindler4628 incorrect good sir

  • @jonasschindler4628

    @jonasschindler4628

    2 жыл бұрын

    @@codyheiner3636 Ohh what's the difference then? Would you mind to explain? Kinda got interested now!

  • @codyheiner3636

    @codyheiner3636

    2 жыл бұрын

    @@jonasschindler4628 you should definitely check Wikipedia or some in depth videos for the details, but in summary: k-d trees oscillate between splitting by dimensions, e.g. split on x, then if still many points, split on y, and so on.. quad trees or octrees split on all dimensions simultaneously. And how they select the split location differs.

  • @jonasschindler4628

    @jonasschindler4628

    2 жыл бұрын

    @@codyheiner3636 Ahh okay thank you will do that.

  • @handsanitizer2457
    @handsanitizer24573 ай бұрын

    Wheres that future episode ? 😂

  • @mrspex7599
    @mrspex75992 жыл бұрын

    the music is annoying other than that cool!!

  • @sayochikun3288
    @sayochikun3288 Жыл бұрын

    didnt know andrew tate also codes