Coding Challenge #98.2: Quadtree - Part 2
VloĆŸit
- Äas pĆidĂĄn 23. 07. 2024
- In this multi-part coding challenge, I implement a Quadtree data structure in JavaScript and visualize it with p5.js. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
đčïž Quadtree Parts 1 & 2: editor.p5js.org/codingtrain/s...
đčïž Quadtree - Part 3: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
đș Quadtree - Part 1: âą Coding Challenge #98.1...
đș Quadtree - Part 3: âą Coding Challenge #98.3...
đ„ Next video: âą Coding Challenge #99: ...
đ„ All videos: âą Coding Challenges
References:
đŸ Quadtree repo: github.com/CodingTrain/QuadTree
đ Quadtree on Wikipedia: en.wikipedia.org/wiki/Quadtree
Live Stream Archive:
đŽ Quadtree Live Stream: âą Live Stream #128: Quad...
Related Coding Challenges:
đ #65 Binary Tree: âą Coding Challenge #65.1...
đ #68 Breadth-First Search: âą Coding Challenge #68: ...
đ #72 Frogger: âą Coding Challenge #72: ...
Timestamps:
0:00 Quadtree Part 2--query the data structure for points contained within a rectangular boundary
1:45 Write a query function to get all the points within a rectangle
3:16 Write an intersection function
6:14 Create an array of "found" points
13:00 Draw points within the rectangle
15:21 Sanity check--how many points are being counted
16:57 Adjust the rectangle with the mouse
18:44 Return the points array
19:42 Up next: apply the quadtrees algorithm to a collision detection problem
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
đ Website: thecodingtrain.com/
đŸ Share Your Creation! thecodingtrain.com/guides/pas...
đ© Suggest Topics: github.com/CodingTrain/Sugges...
đĄ GitHub: github.com/CodingTrain
đŹ Discord: / discord
đ Membership: czcams.com/users/thecodingtrainjoin
đ Store: standard.tv/codingtrain
đïž Twitter: / thecodingtrain
đž Instagram: / the.coding.train
đ„ Coding Challenges: âą Coding Challenges
đ„ Intro to Programming: âą Start learning here!
đ p5.js: p5js.org
đ p5.js Web Editor: editor.p5js.org/
đ Processing: processing.org
đ Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#quadtreedatastructure #quadtreecollisiondetection #javascript #p5js
i love the "pretty good pretty good" with some points staying white XD
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.
Thanks for this excellent feedback!
Thank you for this trick, did you come up with it?
@@khoavo5758 Yes, I believe so. I might have been inspired by another quadtree video or article, but I don't remember seeing this particular optimization. (It's been two years.)
pushing in this case is still good, but you push all of them, because concatenating is not parallelizable.
@@kenhaley4 It was published by Behley in Efficient Radius Neighbor Search in Three-dimensional Point Clouds
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.
Right?! That was so satisfying
It's always so satisfying to see the edits that you request in the livestream.
I remember you saying something along the lines of "Right now would be a good time for one of those speed up things."
The fast forward is cool
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.
Nice one. I'd love to see more on data structures like this! :)
this is the first channel that makes me feel like i'm learning with my professor. you got what it takes to be a teacher lol
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
Absolutely loved both the videos! Awesome job.
your affinity with coding is amazing. I'd love to start coding like that. Right now my programs are spaghetti like crazy.
I'm kinda sorta amazed this works or is faster than the usual method. I always thought of doing this but never quite knew what method to use. This was very helpful. Appreciated.
Awesome video Dan ! Would love to see more data structures. I was looking for reference because I wanted to implement this in my Love2D game.
Can't wait for part three. These videos really make Quadtrees easier to understand, yet I can't quite imagine how the collision detection part would use a quadtree. Would you check a using static bounding range containing your moving object? Would the range you use to query depend on the objects speed? Can't wait.
Man you are awesome and deserve so many more subscribers
I have to agree with a comment in the previous video: You Node should either
- Be a Leaf, containing Points
- Be a non-leaf, containing 4 subtrees.
because currently you have a (small) inefficiency in that any check _will_ check the 10 points in a node, even if they would have been placed in a different bucket.
So, yeah, the "divide" function should go through all the points currently in the node and push them onto the children.
After tge first video I thought I understood the quadtree. This video really showed me how it all works together. I hadn't understood that this would be passed a boundry to search within and it returns the points it finds within.
I thought the boid, from your flock challenge, would pass in it's location and the qtree would find what qtree leaf it was in and return the points in the leaf. I was thinking that it would give some weird results on what points the boid would see.
It was very nice to see where I was thinking about it all wrong and I loved the green highlight effect tied to the mouse cursor.
Keep up the great work!
Dan you are the best! Tihs week I watched your neural network series and its amazing! YOU are amazing. I always struggled to understand how to put all the theory behind the neural network into code and you did that in such a way that answered all my questions. Thank you for that! Love your channel
Thank you for this nice feedback!
It is well deserved! Also, when I was following your tutorial on the neural network I implemented it in such a way that it can have multiple hidden layers set by the user. I know you probably can do it by yourself but would be nice if you wanted to check it out. Just a ps I'm currently still watching your neuroevolution part of the series, so I don't have the code from the next videos.
The staring at that intersects() function was perfect đđŒ
Great argument! I love your channel.
I appreciate the edditing
one of the best tutorials i've seen :)
This was awesome!
excellent video
Very nice example. Very useful for my project.
Really interesting. I was wondering whether you'd done anything on voronoi maps? Would also be interesting to do a four colouring algorithm for such a map too.
Hey there! Just subscribed to your channel, and might I say it's awesome to see someone who shows what programming is really like. Typos and bulk text editing galore hahaha. I just wanted to point out that BST and KD/Quadtrees all suffer in the basic implementation from a kryptonite known as the ordered list. Your implementation here isnt quite as prone to it, but BST (Binary Search Trees) lose their tree structure when loaded with ordered data. Just wanted to point that out to anyone looking to use this and immediately loads say gridded data with it. Random input data is good, but the best is starting from the center and working your way out. Theres also self balancing trees, like used in the C++ (my language) STL, but those concepts take all the fun out of it. Anyway, cheers and like you channel so far.
This video shows the pros and cons of dynamic type programming language at the same time)))
Really love you videos! It makes learning Javascript so easy and fun. This is on a much earlier video, but if I wanted to change the "Flowers" on your Space Invaders coding challenge to an image, how would I do that?
TheCodingTrain: They are not not not not not not not not overlapping
Computer: True
Make a tutorial for being a great person like you... inspiring as always.
Please cover the Vehicle Routing Problem đ. Ive been enjoying your series on quad trees and the TSP problems :-)!
Im now realizing that your code is getting cleaner with every challenge.
I had a thought about my comment on a previous video
When you subdivide modify the maximum number of points to 0 and move the items in the array into the leavesWhen the rest reaches
Oh should've watched this way earlier... fun fact in processing this can work on 60fps - 10 000 000 points with a range of a circle with 100 radius (I added circle as a boundary in the quadtree) but beforehand u'd have to disable all the showing and printing on the screen. :D
So beautiful
It would be a good thing to show how much faster it goes when you use a quadtree =)
you may concatenate multiple arrays using one concat function with multiple arrays as parameters
Should not the range be less every time you query it in the children quads?
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?
Can you explain in the next video Camera Culling with quadtree mode too? with the collisions. Thank you, you help me a lot with this videos ^^
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
How do you go about querying a radius around a point?
In the future, could you modify the quadtree to allow you to add rectangles to it, instead of points?
A cool 3rd part could be animating the particles randomly and seeing the quad tree update itself in real time :)
Doh! I wrote this before the end. Sounds like thatâs may be included in what youâre planning. Awesome. Nice work, loving these videos!
quadtree divisionof 2D Sandpile (using 333-set) base 4 arithmetic using fractal colours (ie.palette selection based on how deep the quadtree is ). Mouse position adds to the sandpile using gaussian window function.
Needs 9 segments instead of 4
awezome, i really want to see the code for this if you still have it
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?
I got a question does this. mean that you dont use the variable that you declined in the top or in a part of a code instead you use a variable that has not the value of the variable but the same name? I wonder myself every time but I dont really get it
I'm very thankfull for every answer :D
Minute 3: I recommend to say to boxes: come as x-interval and y-interval. And then I speak to those intervals like: Do you overlap?
is possible to use this to find the nearst nighbours in a distance range
You count the same point multiples times. you must add the points to the array only if its not divided! I want to watch them live!
Technically this implementation is a bit faulty.. when you subdivide, you should also insert all current points into each child QuadTree aswell, as you can see, in your implementation, you get cells that have very large numbers over the capacity, and I think that this is the reason
EDIT: this is also the reason why the QuadTree did not look as you thought it would.. with random for me, each quadtree looks unique, and intuitively as you would expect for the explanation he gave..
Dude. Just upload your tutorial. You seem to know better than him in this subject.
@@agent-33 well, fundamentally, this is a huge flaw with what the quadtree is supposed to do, so i had to point it out
@@agent-33 i think he actually fixes this in a future part on the quadtree, as well
@@agent-33 It's not rude to note flaws in someone's implementation, it's how we make each other better devs.
"you get cells that have very large numbers over the capacity" - no you don't. It looks that way because some points belong to parent tree and others to its subdivides. They simply share the same space.
Iâve just finished translating this into Processing
I just added a circular search tool so you can search for points within a certain distance from any x y coordinate
what if we have sized particle instead of zero-dimension points?
what is the name of the atom theme that he is using?
The reason some subdivisions contain more than 4 points is because the subdivision should also put all the points in the current rectangle into its children and leave it empty. Here, the parent is still at capacity with subdivision, so the visualisation is kind of misleading on which rectangle contains the points.
i'm trying to do this in java, and i think a lot of the things that he does can only be done in js.
at like 13:00 before he deletes it he logs "points" but points is just an empty array, right? so how did it give 160???
Try to make a challange for octatree
More fast forward please thanks
But seriously, this is pretty cool!
you have the power to do that yourself too :D just press the right arrow key or on mobile tap the videoplay red line a little further right. and you can also just play the video at 1.x speed
For ranged forces and such, I would use a downgraded quadtree. Doesn't matter how many points are in each cell always constant size and number. This version would be much more suited for collisions.
Shouldn't there also be a method for removing a point from the tree? Or do you just keep the structure of the tree the same and remove the point from the quadrant it is in? I think restructuring the tree would help performance, but maybe it wouldn't help enough to justify the cost of restructuring.
How are only 2% of views clicking thumbs up???? All hail the algorithm.
Hey dan, I really enjoyed this coding challenge and I'm really happy to have rediscovered your channel after you were the person that initially taught me how to programm :) I have been programming a lot of neural network and genetic algorithm stuff lately and this was a fun way to mix it up a bit again. I tried to achieve something similar to you going off of memory and I'm absolutely amazed at the performance improvement this method can get you.
While tooling around in processing a bit I discovered this cool pattern, I just think it looks amazing: drive.google.com/drive/u/0/folders/168OcQNHCYH54csQQp20fTdu9YkJUKbcd
Please keep on doing what you are doing you are a great and inspiring person :)
Surely if a rectangle is subdivided it doesnât need its points anymore and you can add them to its subdivisions?
There's a bunch of redundant checks going on because when you subdivide a node of the tree, you are keeping the N points at that node. Those N points then have to be checked regardless of what quadrant they would end up in. Instead, as soon as you subdivide, you could move all the points down into the correct quadrant.
If it were me, I'd probably try to codify that behaviour in the classes, having a different node class for branches and leaves. Then the node never has to ask "am I subdivided?" That would require some redesign, as when a node changed from a leaf to a branch you would have to change out the reference the parent has to it.
If I were doing this in production code, I'd probably even try to make the structure immutable, or, ideally, persistent.
From what I understand this would make querying a bit better but inserting a bit slower since you'd still have to check every moved point to which quadrant it goes on insert/subdivision. I don't think there's a significant gain there if you are using the tree for animation.
Would really have liked a performance comparison
coming in part 3!
Awesome as always! Your channel and specially your coding challenges, really brings back memories from my demoscene coding days. I have a couple/three challenges for you! First is this network threshold linking thing: espen.sandelarsen.com/dev/js/gfx/graphEffects/ second is the Burning ship fractal: espen.sandelarsen.com/dev/js/gfx/shipJS/ and the last I will leave the implementation to you is the Buddabrot fractal. Keep up the awesome work!
thanks for the nice feedback and suggestions!
the first one isn't simple made by linking every point in a quadtree in the end?
If the points are close enough to be in a quadtree, then draw a stroke line
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?
Yes! You can always check all the points in an array and have it work, the idea is here is to try to reduce the number of points you have to check to speed up programs with many many points!
Thank you đ
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!
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 ?
That's what I'm thinking as well. In any case I think that that's a more relevant use case than having stationary points. If you're using quad trees to reduce the number of collision computations you have to make for example within a particle system then you have a moving system, and then these operations and their cost become quite important.
I'm thinking the same thing. But rebuilding the whole tree everytime things move could be disastrous, performance-wise, defeating the whole purpose. To avoid that we'd need a routine to check whether moving a point leaves it within the boundary of its qtree node--if not, go ahead and delete it and re-insert it. If so, do nothing. With particles moving slowly, perhaps only a small subset of the qtree would be affected in each generation.
It's not disastrous to rebuild the tree each time! Sure there are ways to improve but even with this the number of computation cycles are reduced significantly from n*n! See: codingtrain.github.io/QuadTree/examples/intersection_qtree/
Wow. I stand corrected! :-/ What was I thinking?
I must have been thinking the tree would need to be rebuilt for each individual particle move, but that's obviously not the case. In fact we don't even need to touch the tree as particles move, until the end of the generation. Lesson learned.
Can you make Pinball with Javascript?
oh! i do see a glitch ... i'm having difficulty wrapping my head around it, though. when "dividing" ... some points will end up in differing quadrants...so it' LOOKS like five are in one quadrant when there isn't? i'm totally confused. shouldn't some points in the points array get "moved" into the new quadrant? ugh...so weird.
i see it too ( in sw+1/nw+1 there are 5 points...). i replicated his code 1:1. the problem: if you add many points at +10,+10 it will crash because of infinite loop. if you add many points at +10,+10 and differ the position +/- just a little many, many new quads have to be added, but wont... sorry, but the code isnt really working in the end - but i learned a lot of the video.
Hey, this is SUPER LATE but I think I sorted out a solution to this issue.
When you subdivide, you should also be iterating through this.points and inserting them into the child qtrees. Then set this.points = [ ] since you've just handed them over to the children, and then set this.capacity to 0 so it will automatically throw subsequent points to the child qutrees. This will ensure that every quadrant only ever has max 4 points.
Frogger for intersecting rect() wasn't it?
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
No. You're assuming all the points are at the bottom leaves of the quadtree, which isn't true. When a node is subdivided, the points that it already contains are left there, and the children are created empty.
There is much discussion here about whether it would be better to push the existing points down to the lower level, but Dan decided not to do that, and personally, I think it's better this way. Suppose all the points got pushed into the same quadrant. Now, the next point being inserted would cause another subdivide. This could cause many more subdivisions, especially if lots of points were clustered into a very small region.
Ken Haley ok thanks. I did not realize the points where not put into the lower subdivisions
Ken haley - but like this it simply is not a quad-tree and he has some problems too - you can clearly see that he has quads with more than 6!! dots inside.
your point is valid in the case of the boundary that encompasses multiple sections/quads and multiple levels of detail. it would be faster in that case to count the points in the highest level quad than recurse through all of its lower levels for the same result. the ultimate issue with not pushing the points into smaller subdivisions is that the quadtrees greater purpose is for the inter-particle collisions. pushing the points into the lower subdivisions/leaf nodes allows for at most (capacity - 1) collision calculations per particle(less with optimizations). if the dense regions are not subdivided as you think they should be then the number of inter-particle collision calculations is any number greater and approaches the n squared problem size as opposed to the desired nlog(n) size.
sorry for my long response, thank you for reading.
Thank you for this discussion!
you add points multiple time. You only need to add the points to found if the qtree havent divide!
my rectangle intersect function(s) in javascript. This would be a great include into p5 and processing as library functions, this is straight outta my utility library.
/////////////////////////////////////////////////////////////////////
//returns true if one range intersects another range
/////////////////////////////////////////////////////////////////////
function rangeInt(min1,max1,min2,max2){
return Math.max(min1,max1) >= Math.min(min2,max2) &&
Math.min(min1,max1)
To invert the boolean expression you just swap all operators and invert all entries.
In this case:
> -> >=
|| -> &&
you could have checked if two boxes were overlapping using a AABB, so something like ((p1.center.x - p2.center.x) < (p1.half.x + p2.half.x) || (p1.center.y - p2.center.y) < (p1.half.y + p2.half.y)) ? true : false;
quicksort collisions, every frame
collision box test
hierarchical boundary layers
first is the box, then maybe a circle, then something more accurate, functions, voxels, triangles
You have this habit of always adding like 5 lines of white space just to remove it again after only writing one line in that space.
Aren't the points supposed to only be in the leafs of the quadTree ? I am at 7:34 so maybe you correct that later in the video :D
At 9:06 I agree :p
Posted a similar question on part 1, usually, kd-trees only have point values stored inside the leaves
Maybe in his repo but not by the end of this video
This has been raised by many comments, I should implement this and see how much it improvements performance. From what I understand is that it is "good enough" with leaving the points on the parent nodes. The algorithm as described on the wikipedia page for quadtree, for example, doesn't include passing the points down the tree as it subdivides.
en.wikipedia.org/wiki/Quadtree#Pseudo_code
okay, nice! It should improve running-time with the query operations, but increase the running-time on constructing the tree. The effect might not seem apparent if you're doing both at the same time
Linear search is faster than your quadtree if you test processing times...
what language is that
javascript
Description Squad I guess ? đ€
Code Tetris!
Processing version:
github.com/dudenas/QuadTree/tree/master/part2
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*
As it is the tree has points in multiple levels of the subtree not just the leaves so to speak but no point is duplicated it's either in a branch or a leaf but not both
I love your vids but reading your code with all of the non-symmetrical white space makes my ADHD go insane :)
For challange100 how about you upgrade you flappy birds game to be played by am an evolutionary neural network
nice you did it, lel
look at 16:24, you have one single point but your count is 13 (actually your count is wrong for every refresh the page)
Was hoping someone else noticed :p
Also, I think he is incrementing the counter each time a point is found on each level, instead of just on one level
ĐŃ ĐżĐŸŃĐ”ĐŒŃ ĐœĐ° ŃŃŃŃĐșĐŸĐŒ ŃŃŃбД ŃĐ°ĐșĐŸĐłĐŸ ĐœĐ”Ń?
let points = prizes
shouldn't the parent's points be passed down to the children?
The return at line 87 in quadtree.js can cause an error. You don't actually need it.
@12:55 ... Random seed + Unit test
@13:25 Visualisation wins again!
@14:50 Unit test FTW
@5:30 Unit test
He didn't say "I'm gonna do something goofy"
i just want to state to anyone wanting to implement the code, this was one of the more confusing coding trains I have watched. I implemented this in about 1/3 the time it took to watch the videos, all i did was look at the wikipedia pseudo code.
I have an immediate use for this structure and wanted to implement it and was overjoyed to see a CT on this, usually I love this content and it does a good job distilling the concepts for me, but this one will probably lose you.
My version of Flocking with Quadtree :) krzysztofn1993.github.io/Flocking/ -> if you open up console, you can change few parameters.
A little bit of changes from me: avg position, avg speed and repelling force are calculated in same loop so it should be faster. In quadtree I am pushing points from branch to leafs when subdivision happens, also thought about rounding up position of boids to two decimal places (smaller precision should speed up calculation of al in my opinionl) but not sure how to implement this and if is it possible in p5, what do you think? Sorry for my english, it is not my native language.
quad tree seem out of beginner level, but I'm crazy so i made it.
Fun to watch but your tree is bad :D