Coding Challenge #98.2: Quadtree – Part 2

[ad_1]
In part 2 of the Quadtree coding challenge, I query the data structure for points contained within a rectangular boundary.

🔗 Quadtree on Wikipedia:

🎥 Frogger Coding Challenge:

🚂 The Coding Train website:
💖 Support this channel on Patreon:
To buy Coding Train merchandise:
📚 Book recommendations:

💻

🎥 For an Introduction to Programming:
🎥 For More Coding Challenges:

🔗
🔗


Posted

in

by

Tags:

Comments

31 responses to “Coding Challenge #98.2: Quadtree – Part 2”

  1. Christopher Pauly Avatar

    Why does the rectangle boundary formula calculate x-width and compare it to the target.x + width. the X value of a rectangle in p5 is it's leftmost edge already right?

  2. AniLaxsus Avatar

    what language is that

  3. Pedro Henrique Avatar

    Loved this coding challenge! I love optimization tricks. Also this was such a fun one! You deserve all my likes sir!

  4. bokkenka Avatar

    When you moved the rectangle around at the mouse location and the points went from white to green as the box passed over them and then back to white as the box left them, I honestly said, "Wow!" That was beautiful.

  5. Fakkio Avatar

    what if we have sized particle instead of zero-dimension points?

  6. Numero7 Mojeagering Avatar

    I would like to know how make an hash algorithm but I don't see any video that explains how to do it I have seen only video that explains what use for and what is it

  7. Chris Carawan Avatar

    Dear Individual Whom Edits Dans live Streams: I generally watch and love the live streams. When i miss one, Or if life gets busy, i catch up with the shorter vids. The fast forward bit while Dan checks his 'or' function of doom made me dona spit take. That was gold. Thank you. Well done.

  8. Kevin M Avatar

    Man you are awesome and deserve so many more subscribers

  9. iLiquid Avatar

    the timelapse when you just stare at the code for a few minutes made me laugh so hard
    no idea why, you just looked so funny

  10. Kaixo Music Avatar

    I feel like there's something wrong, might just be me being wrong tho. You first check every point in the baundary before you move to the child, doesnt that mean you dont actually have to move to the child? Which would mean it's kinda not working right?

  11. gabriel dhimoila Avatar

    look at 16:24, you have one single point but your count is 13 (actually your count is wrong for every refresh the page)

  12. OrangeC7 Avatar

    More fast forward please thanks
    But seriously, this is pretty cool!

  13. Elias Grage Avatar

    Why does it work just fine without these recursive functions, I tried it an there were no diffrences in finding the Points. You can save the points in an array and check if they are inside of a rectangle. Or do i overlook something?

  14. Rodolphe Peccatte Avatar

    It would be a good thing to show how much faster it goes when you use a quadtree =)

  15. k3ck3m3n Avatar

    I think lines 91-96 in quadtree.js are not needed. You got already every point inside of the rectangle by your for-loop.
    To do better you could say, if it is divided then do lines 91-96. If it's not, do the for loop. I guess this should work more efficiently.

    Anyway great video!

  16. My Andy Avatar

    Hi
    I give you challenge. Can you create impossible rush (https://play.google.com/store/apps/details?id=com.impossible.rush) in Java?
    PLEASEEEEEEEEE REPLY

  17. MaxPicAxe Avatar

    In the future, could you modify the quadtree to allow you to add rectangles to it, instead of points?

  18. MaxPicAxe Avatar

    When you subdivide the tree, shouldn't you empty out this.points, and add them to this.northwest, this.northeast, this.southwest and this.southeast? Wouldn't that make it quicker as well? I also believe you are returning duplicate points, and doing this should fix it

  19. roscocsa Avatar

    Frogger for intersecting rect() wasn't it?

  20. misode Avatar

    The return at line 87 in quadtree.js can cause an error. You don't actually need it.

  21. XKCDism Avatar

    I appreciate the edditing <3

  22. Ken Haley Avatar

    Another optimization: If the sub-quadtree you're looking at is entirely contained in the range being queried, then ALL the points of that quadtree (including those of its descendants) can simply be appended to the found array. You don't need to check each point. This could be significant if the quadtree is very large and a large range is being queried.

    With this in mind, you might want to go back to your initial idea of concatenating arrays from the child qtrees instead of pushing points into the found array one at a time.

  23. Addo White Avatar

    I came up with quite a nice bounding box intersection a while ago
    For those that are interested:
    https://gist.github.com/addowhite/0d0a83d2d46696da651ce4d42f3583a0

  24. dasten123 Avatar

    Nice one. I'd love to see more on data structures like this! 🙂

  25. Charbel Sarkis Avatar

    The fast forward is cool

  26. Edwin Straub Avatar

    Could you maybe do a follow up video where you implement what happens when you remove points from the qtree or when points move around in space/plane ?

  27. Corentin Girard Avatar

    Please don't use else after an if return: it's useless!

  28. Simon Bouchard Avatar

    you add points multiple time. You only need to add the points to found if the qtree havent divide!

  29. Sam Spohn Avatar

    i am not sure but it looks like you count points multiple times when you query. in lines 86 to 96 of the quad tree script i think you should only push points if the quadrant/ section is not divided
    //pseudo code
    if(this.divided){
    query sub sections
    }
    else{
    push points
    }

    cool video though, i learned alot

  30. John Avatar

    This was awesome!

  31. AssassinGrudge Avatar

    is possible to use this to find the nearst nighbours in a distance range

Leave a Reply

Your email address will not be published. Required fields are marked *