WOW! I have been following your P5 videos for months and didn't even know this concept existed. But yesterday I managed to build a quadtree on my own with no tutorial to decrease my grids processing time and I got it right just by imagining the outcome I wanted and messing around. So how the hell did TH-cam know I was looking for this and put this in my recommendations the next day??? Crazy
great video. A small note : at 6:06 its actually *log2(1000) = 10 (with round up) * 1000 = 10.000* because the log in this case has base 2 (not 10 as the calculator has by default)
33:35 there is a problem here, you can clearly see that some squares contain more than 4 points yet did not subdivide. I suspect this is, as was pointed out by others, because a tree that is subdivided is still allowed to contain points.
There is a bug in the rectangle.contains function, where he is including points in a rectangle where p.x >= (r.x - r.w). This is wrong. Should just be p.x >= r.x
@@sigmareaver680 Are you sure? The rectangle has its "pivot" in its center, so if the point get past the center on the left, it returns false, and it means it does not contains it although it does. I think it's correct. by subtracting by the x.position by the width we make sure that the comparing point does not get past the further left limit.
This was a really good low level breakdown of the programming aspect of Quadtrees. Trying to implement this in PyGame. I've watched too many videos on Quadtree theory that I was going nowhere with. Thanks 👍😃
I think you missed an important thing! When you put for example 11 points in a quadtree (with capacity 10), only the 11th point is stored in one of it's quadrants. Wouldn't it be better if all the 11 points are divided between the 4 quadrants? So what I mean is this: Shouldn't only the most specific quadrants (the leafs of your tree) hold the points? Then you could go recursively down the tree to find the quadrants that are not divided (the leafs) and there you find all the points that are in that specific quadrant. Because now you have points that are stored in a "higher" quadrant (one of the parent quadtrees) and exceed the capacity of a "lower" quadrant. In other words: the capacity of a small quadrant can be exceeded because because you also store points in quadtrees that are divided. Ps: I love your videos! Especially your coding challenges!
This definitely could be done, but I'm not sure how much it would improve efficiency in the end. And for simplicity it works "good enough" without doing so. I'd love to try adding this as a feature and see how it works!
I guess the only "slower" part about this approach is the construction: you have to give the points of a quadtree to its quadrant instead of keeping them stored in the quadtree itself. But the efficiency of the important part will stay the same: the search for points in a quadrant. Because you go down the tree no matter what! The amount of points you check is the same in both approaches. I just found it a bit weird that in your design, there can be more points than the capacity in a quadrant. Capacity doesn't mean " max amount of points in an area" anymore when quadrants that are subdivided hold points themselves! It thought " max amount of points in an area" was the purpose of this variable? Much love Simeon
The problem comes when you are comparing the points; where you shouldn't be comparing any points in a quadrant that has been divided. The comparisons should only ever occur in the smallest child so having 10 points in the parent even though it has been divided is not true to the algorithm
In subdivide you could refactor by setting w and h to this.boundary.w/2 and thus.boundary.h/2 and reduce the number of divisions for that section to 2 from 16 I think others have said but only the lowest limbs of the tree should have the points, because two points could be on top of one another but one could be several steps away based on what order they were added to the array. One way to do this would be to refactor the if !this.divided, if it's divided then its point array should be kept empty so the point down through the tree, if it's not divided and there's space add the point here else subdivide and hand off the collected points from this branch down the tree structure. You also do more checks than you need to for what rectangle each point is in because you check it in the rectangle and you check it after it arrives rather than before you send it, 16 checks for every layer the point passes through, if instead you check it's in the global rectangle at the start (4 checks for the top layer) then it can go in the tree and for each sub layer it passes through you only need to check if it's in the North vs South and East vs West, so 2 checks per layer seudocode: if inBoundaries(point) then tree.insert(point) and if point.y
Really helpful tutorial, thank you very much. One small tip: At 17:40 you could've used the destructuring syntax from ES2015 like so: let {x, y, w, h} = this.boundary;
At 18:00, when you created local variables to the function to make it more readable, you should've let w = this.boundary.width / 2, and let h = this.boundary.height/2, that way your formulas would be even more short and readable.
I wish I'd known about quadtrees before I wrote my 3D diffusion-limited aggregation sim in Processing. It has 12,000 particles which is 144,000,000 checks per frame. As you can imagine, it's incredibly slow!
Oh! So that’s what a quad tree is. I want to say, you explained it really well and it was easy to follow, and being able to follow is a big compliment, because I wasn’t wearing my contacts, and was watching on my phone, so most people would be hard to watc, but you are easy :P
Another way to do it would be, instead of "broadcasting" the new point to all the subdivisions and let them figure it out, to push the point to only the subdivision that could take it. It doesn't really matter when to do the check, but it seems to me more logical to let the parent feed each child instead of throwing them the pot... I know... best analogy EVER.
@@BobrLovr yeah, I don't know what I was thinking 5 years ago but it made sense. I guess what I tried to say is, feed the points to the root, and let it route the points ONLY to their corresponding quad, so that quad can then route the point again. Binary search, but 2d.
Don't forget to make use of your editor. You can forward highlight the duplicates of "this." and replace them with nothing, when you are refactoring at 18:02
You can partially rebuild quadtree sections... you can change only the sections of a quadtree where the points change. Given its all a tree, just implement some tree-shaking to eliminate dead points and add new ones whenever your graph changes. Should be much faster.
2 things: First - the iteration number or complexity of the old one, nor the optimized one isn't bigening in an exponential rate... It's by a n^2 factor. Second - the log calculation you have done on the calculator(on the Internet) is by a base of 10, while your nlogn complexity is not. Just thought you should know... Love your channel keep it going :)
I applied the QuadTree to a chart of dynamic nodes. It seemed to work but it feels a bit clumsy. Now, I came across the KDTree that seems to be more appropriate to my problem. It is used to find nearest neighbors in a multi-dimensional space. I think it could also work for your example. The code is much smaller and the logic is easier to apply.
I searched your vids and see that you have actually touched on the subject in this one. #70: Nearest Neighbors Recommendation Engine. But, you don't actually refer to the KDTree.
A minor thing I'm usually mindful of when writing non-exercise code: I might call those rectangles Quadrant, or something like that, just because one's brain will never expect a Rectangle to have its origin point at the center. Someone else reading the code might get the wrong idea, and also not feel the need to double check if it works as expected. Or I might read the code in 6 months and get the wrong idea myself. :)
I love this guy! It would go a long way if he would spend a couple hours learning js a little more idiomatically. It hurts to watch the editing and operations struggles 🙏🏽
@@TheCodingTrain Look into default parameters (to set capacity), destructuring assignment (un-nesting props, let {x, y, w, h} = this.boundary @ 17:30), and spread syntax (for return arrays/objects). Also, check out multiple cursors for fast simultaneous edits in your vscode/atom. You are awesome!
I was stuck with this point, thinking why my implementation doesn't match the one in this video. Still not sure, why he did (y - h/2) for north. Is there an external concave lens used in the camera?
I don't think so -- since each quad only renders (shows) its own points, not the points of the parent quad, which has already rendered the points held in its own array. In other words, the function works by a parent quad rendering its own points, and then calling the show function for its child quads and *not its own show function again*. The confusion (if I'm correct here) is about what 'recursion' mean here. In a sense, this isn't true recursion, because the function isn't calling itself, but the equivalent function belonging to a different (child) object. So, the 'recursion' here refers to the recursive nature of the parent-child quad relation for this data structure.
Wow, so much excellent feedback! I've created this repo -github.com/CodingTrain/QuadTree - in order to allow pull requests to improve the implementation.
I love the scheme for mapping conventional x and y coordinates to cardinal directions. I always imagine a map of the US: everything gets higher as you move toward Florida.
When inserting a point and you are over capacity and you subdivide and put that one point in one of the subtrees, shouldn't the points from the current tree also be distributed into those subtrees? So that only leafs have points ?
I felt your pain trying to figure out what to call the nodes of the tree also linear interpolation makes figuring out how to set the values so much easier
30:08 That larger cell near the top left definitely has more than 4 points. The QuadTrees should be pushing their points down to their child tree when they subdivide. Right now cells have their own points AND their children have points. Unless you're not just using the leaves for storing the points, then go off I guess. Also seems weird to instantiate a new QuadTree every time you subdivide, but that's just silliness with the naming.
@Ubayla Correct. I think he needs to add within insert(point) after this section if (this.points.length < this.capacity && !this.divided) { ... } Here: if (!this.divided) { this.subdivide(); for (var i = 0; i < this.points.length; i++) { this.insert(this.points[i]); // Move points. down into divided quadrants } // Empty parent node's points this.points = []; }
"this is a thousand times THIS" *pointing at 1 million and then 10 thousand*. Not sure if I'm positive about this, Dan, how did elementary school go for you? Loved it x)
The parent should probably check which quadrant to insert into, instead of having each child check and verify. That way it's possible to bypass the boundary check completely if the point was sent from a parent. i.e "insertRandom" vs "insertInto"
Sorry for my bad english, I am french. You are drawing each point many times in your show function, because you should draw them when a quadtree is not subdivided.
Salut! I think that would be true for a tree system that passes its objects (points) down to a child node (quad). This quadtree system keeps its own points, and only passes points to a child quad that are *in addition to* its capacity. ...je pense.
at 36:00 instead of all those "if/else if" you can do: return this.northeast.insert(point) || this.northwest.insert(point) || this.southeast.insert(point) || this.southwest.insert(point);
The one thing that drives me crazy is that you didnt move the existing points down into the divided subtrees. This would create major problems when trying to query based on a sub-tree.
mostly through a combination a grid/tile engine implementation and being smart about what to even check with the information on the direction of the vectors mostly (ie, don't check the direction noone's going) when you break down things into bigger tiles, you can avoid having to check a ton of expensive pixel or vector calculations because you can already determine the objects aren't close enough by their tile/grid coordinates, and can already break out, which is most of the time for most checks when you have a lot of objects going around, so it scales like crazy with a lot of objects. you can even choose to store the tile/grid coordinate AND the relative offset in the objects themselves, it's way more data, but saves a couple of divisions and rounds in the main loop for when you need that extra object count. if you just dupe the same monolithic object a gazillion times it's pretty cheap. big saver there but if they are close, then check their offset from that tile center, only when that passes, do the expensive stuff that can still use raymarching to cheapen up the finer calculations, but most of that can be avoided by a simple grid coordinate system combined with the the object's relative position offset, to just break out all the non-contenders as quickly as possible. the gains are already huge on a simple flat tile grid with no children. when you think about it, an octree is really just a glorified tile/grid engine type of thingie :D
In the subdivide function, instead of setting the x,y,w,h manually, you could instead have javascript do it for you! By replacing those with let { x, y, w, h } = this.boundary;
if you have what 1-dimesional are in numbered partitions (certain width, 1-100, step-1, step-neighbors-0-to-n closest), then you can quickly narrow down, without having a central complicated structure, but the quad-octree binary tree is fine
In the end, I think you do not need a QuadTree and Rectangle class. You can combine both of them into a QuadTreeNode, like you would normally do on a tree (there is no Tree but TreeNode)
Thanks, yes it's true! Thank you for the feedback! I wanted to have a Rectangle class so that the end user of the library could create geometry regions (also a "Circle" for example) without having the make a full node.
@6:05, I think you're wrong in the calculation. The quadtree separates the square into 4 parts, shouldn't that mean that you'll check n*log4(n) times? Not n*log10(n) times. It should be around 5000 checks and not 3000. Either way it's a massive improvement compared to doing a million checks...
19:23 As you look done redoing your cardinal directions I have to ask why the north ones have -y and the south ones have +y? For normal math where the origo is bottom left you would have to swap the + and - for the y, so I'm wondering if your origo is for the top left?
The one thing that is confusing me, and that I notice in yours aswell, is that you can draw more than the capacity in a square? If two are drawn before the first division, they are not counted for any further divisions in the given square. Not sure how much this matters, I think thats just for debugging and the algorithm still works, but not sure if thats a problem or not.
Why is it a problem towards the end 35:20 that the points are not part of multiple quads? wouldn't it actually be better in some cases to have them be part of multiple quads? so that way the particle/point is being collision checked in both of the quads. Sorry for commenting so late but only just had the need to watch this vid, keep up the nice work man!
For everyone who is interested I've implemented and tested QuadTree against naive and "spatial hash grid"(SHG) algorithms. Here are results of these tests relative to naive algorithm: 100 entities: QuadTree is 20% slower, SHG is 2x faster. 500 entities: QuadTree is 3x faster, SHG is 8x faster. 1000 entities: QuadTree is 4.5x faster, SHG is 18x faster. 5000 entities: QuadTree is 17x faster, SHG is 88x faster. 10000 entities: QuadTree is 25x faster, SHG is 151x faster. As you can see SHG is much faster than quadtree, it is also mush simpler to implement and consumes less memory. Though you should take this with grain of salt, as my implementation may lack something important.
a parent quad tree should either contain up to N points, or it should be "subdivided". Your code allows a parent quadrant to hold points and sub quadrants.
Usually you only check each particle to another particle once. You don't check the particle to itself and you check particle A to B and but not B to A again. But I'm sure you know that but just skipped over that. What would be more interesting is a fast way of dividing a surface into triangles on each particle. Like you have a 2D plane with "obstacles" and
26:13 Wait, the roots still have points in them even after being divided? A quad tree section should give all its points to its subsections, not just the one that divided it.
Not necessarily. In a binary search tree, you’d have to have a value in each node to know whether to go “left” (less than the value in that node) or “right” (greater than the value in that node). Often, though, a database would have a n-ary tree for its indexes where it would scan a whole list of numbers, with a child node “between” each value for the values between those values. You still need at least one value in each node to know whether to go “right” or”left” when looking for a specific value.
Shouldnt the Points that are in a quad be removed from that quad when it is subdivided and added to the correct child quads? So the points are allways the leafs of the tree?
@@pravinpoudel1307 yes that is how it "should" be. when subdividing all points should be pushed into the 4 new quadtress and ofc removed from the parent. this way the ending quadtree of each quadtree are the containers of the data, not the parent nodes. this makes data collection when you need it easier because you don't have to check EVERY tree, just the ones that are not subdivided.
@@kayfoster7385 ah yeah, I've done this myself now and you can set a "max depth" for the entir tree. So that if you do get this scenario your don't end up with infinite recursion.
I guess it really depends on what kind of data you've got. If it's more or less distributed evenly, not bunched up (e.g. not a gravity sim), I would think this method very slow compared to something like spatial hashing.
5:52 That's not entirely true. If two algoithms have the same big O, it does not mean they perform the same. It just means the graphs of them have (about) the same shape. Also, you didn't type the bas of the log you were computing. It's worst-case log base 4, but the base can be higher.
6:06 is clearly wrong for the BigO notation The Computer Science log() function is typically base 2. So log_2(1000) is roughly 10 because 2**10 = 1024. Google's result clearly calculactes the log with base 10 instead: log_10(1000) = 3
So big question here: aren't u supposed to not have points in the connecting nodes of a quad tree? U are assigning points till a square is full, then for the next point you subdivide. But aren't u supposed to reassign the points that u already had assigned to the square to the subdivided squares?
Great video! one question though, every internal node in the tree currently contains 4 points itself with this piece of code, while its children also contain 4 points each, which comes down to 4*4 + 4 = 20 points for each internal quadtree node with height 1. Aren't KD-trees defined to use only their leaves to store points in? (4*4=16)
I tried your algorithm against a linear search (also using the same search window) and for some reason the linear search is going faster than the quadtree search? tried changing number of points, bucket size and searcharea / quadrants' size.
Tried to follow it up in processing, but somehow I missed few things, would be good if you would check the code more often just to see what results should I expect at a given point and time.
well, polynomial is true but not very specific : O(n) and O(n^10) would also be polynomial. I guess the right term here is quadratic ! :) Absolutely love your video, keep up the good work with this amazing energy !
@@TheCodingTrain And then it is not log10(n) but log2(n), and 2exp10 is 1024, so for n:=1000 elements, it should take about 1000 x 10 = 10000 computational steps (not 3000)
Quick Question: At 25:10 When he does things like not passing the required number of arguments to the QuadTree Constructor. Why is there no error while editing the code and or running it ?
I have a question about quadtrees for collision detection. Why not just establish a fixed grid where each square corresponds to an array, and when an object enters a square it gets pushed into that square's array, and then each object only checks for collisions between itself and other objects in the same array as it?
md sohail I started with his Processing tutorials and worked my way through most of them. This was sufficient for me to implement all his challenges myself. I love Processing, since it's a full programming enivronment for graphics that requires nearly no previous knowledge to begin with.
Try either of these playlists to start from scratch! th-cam.com/users/shiffmanplaylists?view=50&shelf_id=14&sort=dd th-cam.com/users/shiffmanplaylists?view=50&shelf_id=2&sort=dd
3:00 "There are many ways", what are the other ways, apart from quadtree, for avoiding the n^2 function? Just some names so I can make research on that. Also, does someone has a repo version where the points are stored in the leaf only instead of the tree branches? It would be nice!
Long ago, I know. One simple improvement is to not check previous pairs or itself. 1 checks 2 to 9, 2 checks 3 to 9, 3 checks 4 to 9, etc. 10 points results in 45 checks not 100. This is n choose k. There are other data structures that can be used. Search for spatial partitioning. Examples are BSP trees, k-d trees, sphere trees and Bounding Volume Hierarchies. The latter is used in real time ray tracing. BSP trees was e.g. used in the original Doom games.
Might be a silly idea but could we not give each particle a transmitter and receiver and depending on the strength of the signal could inform the particles in the vicinity of the signal. Kinda like a radar sweep for particles. The sweep area can be flexible just a matter of deciding which particle to target change his emitting code (frequency) all particles near it's location listening to signal receive a change and adjust their code to match a chain reaction could follow so all others can also relay this code to others until all match again unless you only want a certain area to have a new code to transmit and receive. (I'm just as mad as you lols);
Data structures! Hell yes one mistake tho: O(n logn) of 1000 particles would not be 3000, the log has base 2 while the one you calculated had a base 10. O(n logn) is about 9960
It's actually base 4 because when you're searching for the point, the search space is always divided by 4 (4 quadrants) at each step until you find it.
Just started teaching collision detection, those references are priceless 👌
WOW! I have been following your P5 videos for months and didn't even know this concept existed.
But yesterday I managed to build a quadtree on my own with no tutorial to decrease my grids processing time and I got it right just by imagining the outcome I wanted and messing around.
So how the hell did TH-cam know I was looking for this and put this in my recommendations the next day??? Crazy
I was going crazy from how dry every fucking person talking about Algorithms is. This keeps my attention, thank you!! What I needed!!
great video. A small note : at 6:06 its actually *log2(1000) = 10 (with round up) * 1000 = 10.000* because the log in this case has base 2 (not 10 as the calculator has by default)
Yup, this was the comment I was looking for
Wouldn’t it be log4(1000) since it’s a quadtree?
@@davidmooers4072 log4(N) can be expressed in terms of log2(N) as:
log4(N) = log2(N) / log2(4) = 0.5 * log2(N)
33:35 there is a problem here, you can clearly see that some squares contain more than 4 points yet did not subdivide. I suspect this is, as was pointed out by others, because a tree that is subdivided is still allowed to contain points.
There is a bug in the rectangle.contains function, where he is including points in a rectangle where p.x >= (r.x - r.w). This is wrong. Should just be p.x >= r.x
@@sigmareaver680 Are you sure? The rectangle has its "pivot" in its center, so if the point get past the center on the left, it returns false, and it means it does not contains it although it does.
I think it's correct. by subtracting by the x.position by the width we make sure that the comparing point does not get past the further left limit.
This was a really good low level breakdown of the programming aspect of Quadtrees. Trying to implement this in PyGame. I've watched too many videos on Quadtree theory that I was going nowhere with. Thanks 👍😃
You sir, are a credit to your profession. Thank you for making such an understandable, for the layman even, introduction to this topic!
just watched your pak choi recipe video :) Looks delicious
I think you missed an important thing!
When you put for example 11 points in a quadtree (with capacity 10), only the 11th point is stored in one of it's quadrants. Wouldn't it be better if all the 11 points are divided between the 4 quadrants? So what I mean is this: Shouldn't only the most specific quadrants (the leafs of your tree) hold the points? Then you could go recursively down the tree to find the quadrants that are not divided (the leafs) and there you find all the points that are in that specific quadrant. Because now you have points that are stored in a "higher" quadrant (one of the parent quadtrees) and exceed the capacity of a "lower" quadrant. In other words: the capacity of a small quadrant can be exceeded because because you also store points in quadtrees that are divided.
Ps: I love your videos! Especially your coding challenges!
That's an interesting question.
This definitely could be done, but I'm not sure how much it would improve efficiency in the end. And for simplicity it works "good enough" without doing so. I'd love to try adding this as a feature and see how it works!
I guess the only "slower" part about this approach is the construction: you have to give the points of a quadtree to its quadrant instead of keeping them stored in the quadtree itself. But the efficiency of the important part will stay the same: the search for points in a quadrant. Because you go down the tree no matter what! The amount of points you check is the same in both approaches.
I just found it a bit weird that in your design, there can be more points than the capacity in a quadrant. Capacity doesn't mean " max amount of points in an area" anymore when quadrants that are subdivided hold points themselves! It thought " max amount of points in an area" was the purpose of this variable?
Much love
Simeon
The problem comes when you are comparing the points; where you shouldn't be comparing any points in a quadrant that has been divided. The comparisons should only ever occur in the smallest child so having 10 points in the parent even though it has been divided is not true to the algorithm
Thanks for all this feedback! Suggestions for improvements can now be added as issues or pull requests to: github.com/CodingTrain/QuadTree
Omg this is exactly what I need for my simulation, THANK YOU so much for how clear you explain these stuffs!!!
This is the thing I wanted to learn but can't find any good tutorial. Thank you so much!
In subdivide you could refactor by setting w and h to this.boundary.w/2 and thus.boundary.h/2 and reduce the number of divisions for that section to 2 from 16
I think others have said but only the lowest limbs of the tree should have the points, because two points could be on top of one another but one could be several steps away based on what order they were added to the array. One way to do this would be to refactor the if !this.divided, if it's divided then its point array should be kept empty so the point down through the tree, if it's not divided and there's space add the point here else subdivide and hand off the collected points from this branch down the tree structure.
You also do more checks than you need to for what rectangle each point is in because you check it in the rectangle and you check it after it arrives rather than before you send it, 16 checks for every layer the point passes through, if instead you check it's in the global rectangle at the start (4 checks for the top layer) then it can go in the tree and for each sub layer it passes through you only need to check if it's in the North vs South and East vs West, so 2 checks per layer seudocode: if inBoundaries(point) then tree.insert(point) and if point.y
Really helpful tutorial, thank you very much. One small tip:
At 17:40 you could've used the destructuring syntax from ES2015 like so:
let {x, y, w, h} = this.boundary;
Oh, great tip, thank you!
Just amazing man. So simply explained a "rather" complex looking data-structure.
At 18:00, when you created local variables to the function to make it more readable, you should've let w = this.boundary.width / 2, and let h = this.boundary.height/2, that way your formulas would be even more short and readable.
Great tip, thank you!
first video I've seen from this channel. Just subscribed. Well described and actually very fun to watch. Cheers.
I wish I'd known about quadtrees before I wrote my 3D diffusion-limited aggregation sim in Processing. It has 12,000 particles which is 144,000,000 checks per frame. As you can imagine, it's incredibly slow!
Oh! So that’s what a quad tree is. I want to say, you explained it really well and it was easy to follow, and being able to follow is a big compliment, because I wasn’t wearing my contacts, and was watching on my phone, so most people would be hard to watc, but you are easy :P
Thanks a lot for the full demo this really is helping secure my understanding to use in my own projects!
Another way to do it would be, instead of "broadcasting" the new point to all the subdivisions and let them figure it out, to push the point to only the subdivision that could take it. It doesn't really matter when to do the check, but it seems to me more logical to let the parent feed each child instead of throwing them the pot... I know... best analogy EVER.
that defeats the purpose, because then you have to iterate over all of them always
@@BobrLovr yeah, I don't know what I was thinking 5 years ago but it made sense. I guess what I tried to say is, feed the points to the root, and let it route the points ONLY to their corresponding quad, so that quad can then route the point again. Binary search, but 2d.
damn. coding live is like the ultimate pair programming
Don't forget to make use of your editor. You can forward highlight the duplicates of "this." and replace them with nothing, when you are refactoring at 18:02
You can partially rebuild quadtree sections... you can change only the sections of a quadtree where the points change. Given its all a tree, just implement some tree-shaking to eliminate dead points and add new ones whenever your graph changes. Should be much faster.
How to do that? Can you explain lil bit more about the algorithm?
2 things:
First - the iteration number or complexity of the old one, nor the optimized one isn't bigening in an exponential rate... It's by a n^2 factor.
Second - the log calculation you have done on the calculator(on the Internet) is by a base of 10, while your nlogn complexity is not.
Just thought you should know...
Love your channel keep it going :)
Yes, thank you for these corrections!
Yes, thank you for these corrections!
So instead of using log10, we should use ln or it's a generic log?
@@ilieschamkar6767 I'm going to have to rewatch the video to answer that, my comment was 3 years ago 😅
I'll try to remember to do it later
@@orr4945 I've read in a comment that technically it should be log4, because we are dividing each quadtree four times
Thanks nonetheless :D
I applied the QuadTree to a chart of dynamic nodes. It seemed to work but it feels a bit clumsy. Now, I came across the KDTree that seems to be more appropriate to my problem. It is used to find nearest neighbors in a multi-dimensional space. I think it could also work for your example. The code is much smaller and the logic is easier to apply.
I searched your vids and see that you have actually touched on the subject in this one. #70: Nearest Neighbors Recommendation Engine. But, you don't actually refer to the KDTree.
All my tension was relieved when he said the word "visualize"😂
A minor thing I'm usually mindful of when writing non-exercise code: I might call those rectangles Quadrant, or something like that, just because one's brain will never expect a Rectangle to have its origin point at the center. Someone else reading the code might get the wrong idea, and also not feel the need to double check if it works as expected. Or I might read the code in 6 months and get the wrong idea myself. :)
I really like your enthusiasm!
Top/bottom , left/right >> NE, NW, SE, SW. Change my mind
I love this guy! It would go a long way if he would spend a couple hours learning js a little more idiomatically. It hurts to watch the editing and operations struggles 🙏🏽
Thanks for the feedback! Are there some specific moments or bits of code you can share that I should take a closer look at?
@@TheCodingTrain Look into default parameters (to set capacity), destructuring assignment (un-nesting props, let {x, y, w, h} = this.boundary @ 17:30), and spread syntax (for return arrays/objects). Also, check out multiple cursors for fast simultaneous edits in your vscode/atom. You are awesome!
When you were talking about the west on the right side, I was like "wow I never noticed, your camera records in mirrored image"
😂
I was stuck with this point, thinking why my implementation doesn't match the one in this video.
Still not sure, why he did (y - h/2) for north.
Is there an external concave lens used in the camera?
This was great. Never knew about a Quadtree.
29:21 I think the points are drawn multiple times because that happens in the recursive function show(), maybe that's why it becomes very slow ^^
I don't think so -- since each quad only renders (shows) its own points, not the points of the parent quad, which has already rendered the points held in its own array. In other words, the function works by a parent quad rendering its own points, and then calling the show function for its child quads and *not its own show function again*.
The confusion (if I'm correct here) is about what 'recursion' mean here. In a sense, this isn't true recursion, because the function isn't calling itself, but the equivalent function belonging to a different (child) object. So, the 'recursion' here refers to the recursive nature of the parent-child quad relation for this data structure.
No they aren't. A point is only in one of the four quadtree's.
Actually what's happening is when a fifth point is added, the four original points are not divided into the four quadtree's.
Wow, so much excellent feedback! I've created this repo -github.com/CodingTrain/QuadTree - in order to allow pull requests to improve the implementation.
The link is broken, remove the ")" at the end of the url :)
thanks should be fixed now.
I love the scheme for mapping conventional x and y coordinates to cardinal directions. I always imagine a map of the US: everything gets higher as you move toward Florida.
When inserting a point and you are over capacity and you subdivide and put that one point in one of the subtrees, shouldn't the points from the current tree also be distributed into those subtrees? So that only leafs have points ?
Thats exactly whats happening.
I felt your pain trying to figure out what to call the nodes of the tree
also linear interpolation makes figuring out how to set the values so much easier
23:43 I love how he leans on his code editor and takes a look to the right xD
30:08 That larger cell near the top left definitely has more than 4 points.
The QuadTrees should be pushing their points down to their child tree when they subdivide. Right now cells have their own points AND their children have points. Unless you're not just using the leaves for storing the points, then go off I guess.
Also seems weird to instantiate a new QuadTree every time you subdivide, but that's just silliness with the naming.
@Ubayla
Correct. I think he needs to add within insert(point) after this section
if (this.points.length < this.capacity && !this.divided) {
...
}
Here:
if (!this.divided) {
this.subdivide();
for (var i = 0; i < this.points.length; i++) {
this.insert(this.points[i]); // Move points. down into divided quadrants
}
// Empty parent node's points
this.points = [];
}
my fave channel :)
Grid is better for moving objects with similar size. If the objects are static and of varying size, a quadtree is very helpful.
"this is a thousand times THIS" *pointing at 1 million and then 10 thousand*. Not sure if I'm positive about this, Dan, how did elementary school go for you?
Loved it x)
The parent should probably check which quadrant to insert into, instead of having each child check and verify. That way it's possible to bypass the boundary check completely if the point was sent from a parent. i.e "insertRandom" vs "insertInto"
17:30 -> with es6 you can do something like : let { x, y, w, h } = this.boundary;
thanks for the tip!
Sorry for my bad english, I am french. You are drawing each point many times in your show function, because you should draw them when a quadtree is not subdivided.
Salut! I think that would be true for a tree system that passes its objects (points) down to a child node (quad). This quadtree system keeps its own points, and only passes points to a child quad that are *in addition to* its capacity.
...je pense.
Red Hen dev yes it's that
at 36:00 instead of all those "if/else if" you can do:
return this.northeast.insert(point) || this.northwest.insert(point) || this.southeast.insert(point) || this.southwest.insert(point);
Thanks for the tip!
UwU
The one thing that drives me crazy is that you didnt move the existing points down into the divided subtrees. This would create major problems when trying to query based on a sub-tree.
36:30 hurts my eyes. just return a conditional with an OR operation with the 4 method calls
Wow. Simple, to the point demo
This method is easily applicable to octrees as well. Thanks!
In your insert function, you almost had it, you only have to put the equal on two sides, solves the point in both.
You're a genius !! When I see that I wan't learn Javascript !
excellent video - really helpful to see you work it out as you write it, I learned a lot, very clear and understandable. thanks - subscribed!
can you do some videos on 2d physics engines? hit detection, collision resolution, angular momentum, etc? its too hard to learn on my own!
That bell is going to drive me crazy. D:
i do not watch ur channel all the time but when i do see some of ur videos [ usually randomly ] i feel like i won't release !
Nice! I always wonderd how colision detection is reduced to a useful amount of checks.
mostly through a combination a grid/tile engine implementation and being smart about what to even check with the information on the direction of the vectors mostly (ie, don't check the direction noone's going)
when you break down things into bigger tiles, you can avoid having to check a ton of expensive pixel or vector calculations
because you can already determine the objects aren't close enough by their tile/grid coordinates, and can already break out, which is most of the time for most checks when you have a lot of objects going around, so it scales like crazy with a lot of objects.
you can even choose to store the tile/grid coordinate AND the relative offset in the objects themselves,
it's way more data, but saves a couple of divisions and rounds in the main loop for when you need that extra object count.
if you just dupe the same monolithic object a gazillion times it's pretty cheap.
big saver there
but if they are close, then check their offset from that tile center, only when that passes, do the expensive stuff
that can still use raymarching to cheapen up the finer calculations, but most of that can be avoided by a simple grid coordinate system combined with the the object's relative position offset, to just break out all the non-contenders as quickly as possible.
the gains are already huge on a simple flat tile grid with no children.
when you think about it, an octree is really just a glorified tile/grid engine type of thingie :D
In the subdivide function, instead of setting the x,y,w,h manually, you could instead have javascript do it for you! By replacing those with
let { x, y, w, h } = this.boundary;
if you have what 1-dimesional are in numbered partitions (certain width, 1-100, step-1, step-neighbors-0-to-n closest), then you can quickly narrow down, without having a central complicated structure, but the quad-octree binary tree is fine
you can detach the three or two coordinates, to 1-d checks
if you can skip completely any step you would be using n^2 comparisons, then you have defeated the need what you were going to non-needingly do
pair-wise tests, instead, do what
a solution structure
abstract
An optimization would be to calculate half_width and half_height once at the beginning locally instead of calculating it multiple times per quadrant.
In the end, I think you do not need a QuadTree and Rectangle class. You can combine both of them into a QuadTreeNode, like you would normally do on a tree (there is no Tree but TreeNode)
Thanks, yes it's true! Thank you for the feedback! I wanted to have a Rectangle class so that the end user of the library could create geometry regions (also a "Circle" for example) without having the make a full node.
@6:05, I think you're wrong in the calculation.
The quadtree separates the square into 4 parts, shouldn't that mean that you'll check n*log4(n) times? Not n*log10(n) times.
It should be around 5000 checks and not 3000. Either way it's a massive improvement compared to doing a million checks...
Yes, you are correct!
you helped me a lot, thanks
19:23 As you look done redoing your cardinal directions I have to ask why the north ones have -y and the south ones have +y?
For normal math where the origo is bottom left you would have to swap the + and - for the y, so I'm wondering if your origo is for the top left?
The one thing that is confusing me, and that I notice in yours aswell, is that you can draw more than the capacity in a square? If two are drawn before the first division, they are not counted for any further divisions in the given square. Not sure how much this matters, I think thats just for debugging and the algorithm still works, but not sure if thats a problem or not.
This man does the equals sign at the beginning of the Google query.
Why is it a problem towards the end 35:20 that the points are not part of multiple quads? wouldn't it actually be better in some cases to have them be part of multiple quads? so that way the particle/point is being collision checked in both of the quads.
Sorry for commenting so late but only just had the need to watch this vid, keep up the nice work man!
For everyone who is interested I've implemented and tested QuadTree against naive and "spatial hash grid"(SHG) algorithms. Here are results of these tests relative to naive algorithm:
100 entities: QuadTree is 20% slower, SHG is 2x faster.
500 entities: QuadTree is 3x faster, SHG is 8x faster.
1000 entities: QuadTree is 4.5x faster, SHG is 18x faster.
5000 entities: QuadTree is 17x faster, SHG is 88x faster.
10000 entities: QuadTree is 25x faster, SHG is 151x faster.
As you can see SHG is much faster than quadtree, it is also mush simpler to implement and consumes less memory. Though you should take this with grain of salt, as my implementation may lack something important.
a parent quad tree should either contain up to N points, or it should be "subdivided". Your code allows a parent quadrant to hold points and sub quadrants.
hm i noticed this lol
Seeing the trouble you had with ne, nw, se, sw (It challenges my brains the same btw), I wonder what your octree video shall look like :)
Usually you only check each particle to another particle once. You don't check the particle to itself and you check particle A to B and but not B to A again. But I'm sure you know that but just skipped over that.
What would be more interesting is a fast way of dividing a surface into triangles on each particle. Like you have a 2D plane with "obstacles" and
26:13 Wait, the roots still have points in them even after being divided? A quad tree section should give all its points to its subsections, not just the one that divided it.
Not necessarily. In a binary search tree, you’d have to have a value in each node to know whether to go “left” (less than the value in that node) or “right” (greater than the value in that node). Often, though, a database would have a n-ary tree for its indexes where it would scan a whole list of numbers, with a child node “between” each value for the values between those values. You still need at least one value in each node to know whether to go “right” or”left” when looking for a specific value.
@@JackFlashTech if (left !=null), if (right != null).
Shouldnt the Points that are in a quad be removed from that quad when it is subdivided and added to the correct child quads? So the points are allways the leafs of the tree?
I don't understand why there is no response to this valid question. Do you have anything that you can add to this yourself?
@@pravinpoudel1307
yes that is how it "should" be. when subdividing all points should be pushed into the 4 new quadtress and ofc removed from the parent. this way the ending quadtree of each quadtree are the containers of the data, not the parent nodes.
this makes data collection when you need it easier because you don't have to check EVERY tree, just the ones that are not subdivided.
How would it cope if you had a quad tree with a node capacity of 4 and you add to it 5 points with the exact same coordinates?
@@Fogmeister however you want i guess. but i think it would treat two points as 1 though it takes 2 slots in your array.
@@kayfoster7385 ah yeah, I've done this myself now and you can set a "max depth" for the entir tree. So that if you do get this scenario your don't end up with infinite recursion.
I guess it really depends on what kind of data you've got. If it's more or less distributed evenly, not bunched up (e.g. not a gravity sim), I would think this method very slow compared to something like spatial hashing.
5:52 That's not entirely true. If two algoithms have the same big O, it does not mean they perform the same. It just means the graphs of them have (about) the same shape. Also, you didn't type the bas of the log you were computing. It's worst-case log base 4, but the base can be higher.
great class! i enjoined and learn a lot! thank you!
6:06 is clearly wrong for the BigO notation
The Computer Science log() function is typically base 2. So log_2(1000) is roughly 10 because 2**10 = 1024.
Google's result clearly calculactes the log with base 10 instead: log_10(1000) = 3
The number of checks is actually 10 choose 2. 10! / (8! * 2!) = 90 / 2 = 45. The combination rule!
Have you considered using quaternary numbers to reference section?
17:38 const {x,y,w,h} = this.boundary
So big question here:
aren't u supposed to not have points in the connecting nodes of a quad tree? U are assigning points till a square is full, then for the next point you subdivide. But aren't u supposed to reassign the points that u already had assigned to the square to the subdivided squares?
Great video! one question though, every internal node in the tree currently contains 4 points itself with this piece of code, while its children also contain 4 points each, which comes down to 4*4 + 4 = 20 points for each internal quadtree node with height 1. Aren't KD-trees defined to use only their leaves to store points in? (4*4=16)
His tree is a bit "special" :P
The log factor in the complexity should be base 4 in the case of a quadtree, not 10.
P.S. I love your videos.
Nice! Learned a lot!
I tried your algorithm against a linear search (also using the same search window) and for some reason the linear search is going faster than the quadtree search? tried changing number of points, bucket size and searcharea / quadrants' size.
Looked for info on scene graph basics
Watched this, to be continued
Hmmm no part 2
Vid posted today, pfff gotta wait... Great info anyways, thanks!
Tried to follow it up in processing, but somehow I missed few things, would be good if you would check the code more often just to see what results should I expect at a given point and time.
github.com/dudenas/QuadTree
I was wrong, it worked at the end, but still it would be good to have a check of code from time to time.
Its not exponential >:(
Yes, oops. "polynomial" is correct, yes? Exponential would be 2^n?
yes, it's just 100 times instead of 10 times but it's ok to get confused sometimes :P
well, polynomial is true but not very specific : O(n) and O(n^10) would also be polynomial.
I guess the right term here is quadratic ! :)
Absolutely love your video, keep up the good work with this amazing energy !
@@cazoulable non-linear polynomial hahah
@@TheCodingTrain And then it is not log10(n) but log2(n), and 2exp10 is 1024, so for n:=1000 elements, it should take about 1000 x 10 = 10000 computational steps (not 3000)
I like your video. it is very straighforward.
Any graph can be a tree if you declare a root node and their leaves respectively.
hi thats a great video! wonder, can i just use the QuadTreeNode ? it seems that i can save some cpu.. no?
Quick Question: At 25:10
When he does things like not passing the required number of arguments to the QuadTree Constructor. Why is there no error while editing the code and or running it ?
Awesome vids. =))) Super nice
cool tut!!!
I have a question about quadtrees for collision detection. Why not just establish a fixed grid where each square corresponds to an array, and when an object enters a square it gets pushed into that square's array, and then each object only checks for collisions between itself and other objects in the same array as it?
I'm really enjoying the stuff u r doing..And I have been watching u since few months..I also want to try these things out..But where do I start?😶🤔
from here : th-cam.com/video/8j0UDiN7my4/w-d-xo.html
locomotive……jk :p.
md sohail I started with his Processing tutorials and worked my way through most of them. This was sufficient for me to implement all his challenges myself. I love Processing, since it's a full programming enivronment for graphics that requires nearly no previous knowledge to begin with.
Try either of these playlists to start from scratch!
th-cam.com/users/shiffmanplaylists?view=50&shelf_id=14&sort=dd
th-cam.com/users/shiffmanplaylists?view=50&shelf_id=2&sort=dd
Can you please do a video on iterators?
3:00 "There are many ways", what are the other ways, apart from quadtree, for avoiding the n^2 function?
Just some names so I can make research on that.
Also, does someone has a repo version where the points are stored in the leaf only instead of the tree branches? It would be nice!
Long ago, I know. One simple improvement is to not check previous pairs or itself. 1 checks 2 to 9, 2 checks 3 to 9, 3 checks 4 to 9, etc. 10 points results in 45 checks not 100. This is n choose k.
There are other data structures that can be used. Search for spatial partitioning. Examples are BSP trees, k-d trees, sphere trees and Bounding Volume Hierarchies. The latter is used in real time ray tracing. BSP trees was e.g. used in the original Doom games.
Might be a silly idea but could we not give each particle a transmitter and receiver and depending on the strength of the signal could inform the particles in the vicinity of the signal. Kinda like a radar sweep for particles. The sweep area can be flexible just a matter of deciding which particle to target change his emitting code (frequency) all particles near it's location listening to signal receive a change and adjust their code to match a chain reaction could follow so all others can also relay this code to others until all match again unless you only want a certain area to have a new code to transmit and receive. (I'm just as mad as you lols);
Data structures! Hell yes
one mistake tho: O(n logn) of 1000 particles would not be 3000, the log has base 2 while the one you calculated had a base 10. O(n logn) is about 9960
It's actually base 4 because when you're searching for the point, the search space is always divided by 4 (4 quadrants) at each step until you find it.
If you want to implement the printing of the quadtree without changing the structure you should use a visitor ;)