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
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 UA-cam know I was looking for this and put this in my recommendations the next day??? Crazy
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.
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)
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 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!
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.
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 ?
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
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.
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.
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! 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
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 = []; }
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. :)
Wow, so much excellent feedback! I've created this repo -github.com/CodingTrain/QuadTree - in order to allow pull requests to improve the implementation.
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 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.
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.
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.
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 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)
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!
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.
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?
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 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
I'm attempting to follow along hoping that it'll be more clear to me exactly how this functions, but at 10:17 my console still tells me that Rectangle is undefined even after referencing it in my HTML file. What's going on?
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.
at 19:00 u have for NE and NW y-h/2 shouldnt it be y+h/2 because its where u currently are + half of the height to go up. and SW SE should be '-' ? with your rectangles where is 0,0 ? is it top left? im trying to do x,y,w,h into top_left x1,y1 bottom right x2,y2 the math is confusing me
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"
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.
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 ?
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?
@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...
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.
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);
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.
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.
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!
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
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)
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
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?
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.
Great tutorial. Can you please help me with one question, in the class QuadTree of your code, the properties "this.northwest, this.northeast, this.southwest, and this.southeast" are all defined in subdivide() method of the class other than in the constructor method. Is it legal to do so, or is it better to put the following expressions: (this.northwest = null; this.southwest = null; this.southwest = null; this.southeast = null;) in the constructor method,then we can set their values in the subdivide() method. Many thanks for your help and time.
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;
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)
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.
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.
I’m probably really late to ask this lol, but why does he not give the points already in the parent quad tree branch to the children subdivided quad tree branch, and then remove those references to the parent one? If let’s say it were to be used as a collision detection system, wouldn’t it cause problems not doing that?
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.
It does not need to be from the center at all. I think the reason he chose the center is so that it's easier to determine the x and y coordinates of the sub boundaries. But yes you absolutely do it from the top left as well you'd just have to adjust your numbers!
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.
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.
Hey that's a really good video! I have one question: Could I theoretically use this code and somehow change it to an octree by adjusting the rectangle to a cube and adding the according z coordinates? Or if this doesn't work, is there any other way? This would be a big help! Thanks!
Absolutely you could do that! If you follow the basic theory of what he is doing, it shouldn't be terribly hard to implement! Of course drawing it to the screen is a different matter but yes you are very much correct!
Just started teaching collision detection, those references are priceless 👌
I was going crazy from how dry every fucking person talking about Algorithms is. This keeps my attention, thank you!! What I needed!!
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
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 UA-cam know I was looking for this and put this in my recommendations the next day??? Crazy
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.
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)
Omg this is exactly what I need for my simulation, THANK YOU so much for how clear you explain these stuffs!!!
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 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!
This is the thing I wanted to learn but can't find any good tutorial. Thank you so much!
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.
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.
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
first video I've seen from this channel. Just subscribed. Well described and actually very fun to watch. Cheers.
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!
Thanks a lot for the full demo this really is helping secure my understanding to use in my own projects!
This was great. Never knew about a Quadtree.
my fave channel :)
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?
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!
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
I really like your enthusiasm!
23:43 I love how he leans on his code editor and takes a look to the right xD
Top/bottom , left/right >> NE, NW, SE, SW. Change my mind
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 = [];
}
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. :)
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.
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 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.
All my tension was relieved when he said the word "visualize"😂
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.
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.
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 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)
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!
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.
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?
36:30 hurts my eyes. just return a conditional with an OR operation with the 4 method calls
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 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
I'm attempting to follow along hoping that it'll be more clear to me exactly how this functions, but at 10:17 my console still tells me that Rectangle is undefined even after referencing it in my HTML file. What's going on?
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.
at 19:00 u have for NE and NW y-h/2 shouldnt it be y+h/2 because its where u currently are + half of the height to go up.
and SW SE should be '-' ?
with your rectangles where is 0,0 ? is it top left? im trying to do x,y,w,h into top_left x1,y1 bottom right x2,y2
the math is confusing me
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"
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.
Wow. Simple, to the point demo
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 ?
Grid is better for moving objects with similar size. If the objects are static and of varying size, a quadtree is very helpful.
can you do some videos on 2d physics engines? hit detection, collision resolution, angular momentum, etc? its too hard to learn on my own!
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?
@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!
17:30 -> with es6 you can do something like : let { x, y, w, h } = this.boundary;
thanks for the tip!
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).
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
You're a genius !! When I see that I wan't learn Javascript !
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.
This method is easily applicable to octrees as well. Thanks!
Have you considered using quaternary numbers to reference section?
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
How would you make the squares to be more like rectangles or any other shape? So they are not even squares within squares.
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!
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
How does it handle points on the edges of quads.. and the edge of the outermost..
excellent video - really helpful to see you work it out as you write it, I learned a lot, very clear and understandable. thanks - subscribed!
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
How are you viewing all that information from the console? Like the Size of the rectangle
Console.log( any variable, like the quadtree ) will print all that information to the browser console
This workflow series might help! ua-cam.com/play/PLRqwX-V7Uu6YxDKpFzf_2D84p0cyk4T7X.html&disable_polymer=true
oops, wrong link! ua-cam.com/play/PLRqwX-V7Uu6Zu_uqEA6NqhLzKLACwU74X.html
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
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?
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.
did I catch a bug or I missed some step, the first point before the capacity is not divide into any of the four region?
Nice! Learned a lot!
Great tutorial. Can you please help me with one question, in the class QuadTree of your code, the properties "this.northwest, this.northeast, this.southwest, and this.southeast" are all defined in subdivide() method of the class other than in the constructor method. Is it legal to do so, or is it better to put the following expressions: (this.northwest = null; this.southwest = null; this.southwest = null; this.southeast = null;) in the constructor method,then we can set their values in the subdivide() method. Many thanks for your help and time.
great class! i enjoined and learn a lot! thank you!
That bell is going to drive me crazy. 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;
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 :)
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)
Why quad and not binary here? Why divide the space by 4 instead of 2? Does it make the implementation easier with 4?
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.
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.
I’m probably really late to ask this lol, but why does he not give the points already in the parent quad tree branch to the children subdivided quad tree branch, and then remove those references to the parent one? If let’s say it were to be used as a collision detection system, wouldn’t it cause problems not doing that?
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.
Does the quadtree need to divided from the center point or can it be from the top left? Seems unnecessarily complicated to break out from the center.
It does not need to be from the center at all. I think the reason he chose the center is so that it's easier to determine the x and y coordinates of the sub boundaries. But yes you absolutely do it from the top left as well you'd just have to adjust your numbers!
you helped me a lot, thanks
But it's not really done yet. You are not redistributing the points in the sub sections
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
hi thats a great video! wonder, can i just use the QuadTreeNode ? it seems that i can save some cpu.. no?
6:05 isn't the default log base 10? if you use a base 2 log the equation is more like 1000 * 10 = 10'000, not 3000
An optimization would be to calculate half_width and half_height once at the beginning locally instead of calculating it multiple times per quadrant.
can you use quadtrees to detect collision if you are not using points but circles?
In your insert function, you almost had it, you only have to put the equal on two sides, solves the point in both.
The number of checks is actually 10 choose 2. 10! / (8! * 2!) = 90 / 2 = 45. The combination rule!
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.
Awesome vids. =))) Super nice
I like your video. it is very straighforward.
Hey that's a really good video! I have one question: Could I theoretically use this code and somehow change it to an octree by adjusting the rectangle to a cube and adding the according z coordinates? Or if this doesn't work, is there any other way? This would be a big help! Thanks!
Absolutely you could do that! If you follow the basic theory of what he is doing, it shouldn't be terribly hard to implement! Of course drawing it to the screen is a different matter but yes you are very much correct!
I did exactly that. I would suggest creating the children in a for loop instead of assigning each of them a variable upon subdivision, though