Coding Challenge #98.1: Quadtree - Part 1

Подписаться 1,7 млн

Просмотров 304 тыс.

50% 1

In this multi-part coding challenge, I implement a Quadtree data structure in JavaScript and visualize it with p5.js. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Quadtree Parts 1 & 2: editor.p5js.org/codingtrain/s...
🕹️ Quadtree - Part 3: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Quadtree - Part 2: • Coding Challenge #98.2...
📺 Quadtree - Part 3: • Coding Challenge #98.3...
🎥 Next video: • Coding Challenge #99: ...
🎥 All videos: • Coding Challenges
References:
💾 Quadtree repo: github.com/CodingTrain/QuadTree
🗄 Quadtree on Wikipedia: en.wikipedia.org/wiki/Quadtree
Live Stream Archive:
🔴 Quadtree Live Stream: • Live Stream #128: Quad...
Related Coding Challenges:
🚂 #65 Binary Tree: • Coding Challenge #65.1...
🚂 #68 Breadth-First Search: • Coding Challenge #68: ...
🚂 #72 Frogger: • Coding Challenge #72: ...
Timestamps:
0:00 Introducing today's topic: Quadtrees
1:34 N squared problem
4:30 Big O notation
8:23 QuadTree class
11:15 Capacity
12:26 Insert points
13:30 Create a subdivide function
20:11 Recursively add points
21:12 Check if point is within boundary
26:49 Visualize the Quadtree
30:30 Use mouse clicks to add points
32:43 Edge cases
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#quadtreedatastructure #quadtreecollisiondetection #javascript #p5js

Опубликовано:

5 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 362

@StarContract 6 лет назад

Just started teaching collision detection, those references are priceless 👌

@Em-bi7tn 5 лет назад

I was going crazy from how dry every fucking person talking about Algorithms is. This keeps my attention, thank you!! What I needed!!

@jasonedward 4 года назад

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 RU-vid know I was looking for this and put this in my recommendations the next day??? Crazy

@deepnomusic Год назад

Omg this is exactly what I need for my simulation, THANK YOU so much for how clear you explain these stuffs!!!

@simeon2396 6 лет назад

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!

@redhen 6 лет назад

That's an interesting question.

@TheCodingTrain 6 лет назад

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!

@simeon2396 6 лет назад

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

@Smikay 6 лет назад

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

@TheCodingTrain 6 лет назад

Thanks for all this feedback! Suggestions for improvements can now be added as issues or pull requests to: github.com/CodingTrain/QuadTree

@ThomasChen-ur2gt 6 лет назад

This is the thing I wanted to learn but can't find any good tutorial. Thank you so much!

@pursuitofcat 3 года назад

Just amazing man. So simply explained a "rather" complex looking data-structure.

@dudley0007 4 года назад

first video I've seen from this channel. Just subscribed. Well described and actually very fun to watch. Cheers.

@ArnoldsKtm 5 лет назад

This was great. Never knew about a Quadtree.

@johnydl 6 лет назад

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

@CallmeSam00 4 года назад

You sir, are a credit to your profession. Thank you for making such an understandable, for the layman even, introduction to this topic!

@JannisAdmek 4 года назад

just watched your pak choi recipe video :) Looks delicious

@an0nsaiko890 3 года назад

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)

@ronaldc8634 3 года назад

Yup, this was the comment I was looking for

@davidmooers4072 Год назад

Wouldn’t it be log4(1000) since it’s a quadtree?

@Shannxy 11 месяцев назад

@@davidmooers4072 log4(N) can be expressed in terms of log2(N) as: log4(N) = log2(N) / log2(4) = 0.5 * log2(N)

@pavelrahl6284 5 лет назад

I really like your enthusiasm!

@sdegueldre 6 лет назад

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.

@sigmareaver680 5 лет назад

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

@Maxparata 5 лет назад

@@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.

@therealdnold 21 день назад

23:43 I love how he leans on his code editor and takes a look to the right xD

@Otakutaru 6 лет назад

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.

@IDontReadReplies42069 4 месяца назад

that defeats the purpose, because then you have to iterate over all of them always

@Otakutaru 4 месяца назад

@@IDontReadReplies42069 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.

@PeterVC 6 лет назад

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 ?

@Chevifier Год назад

Thats exactly whats happening.

@rileymeggison326 3 года назад

All my tension was relieved when he said the word "visualize"😂

@ben_jammin242 4 года назад

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

@sethmoeckel7853 6 лет назад

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.

@mirza5373 Месяц назад

How to do that? Can you explain lil bit more about the algorithm?

@lfroggyl 6 лет назад

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.

@TheCodingTrain 6 лет назад

Great tip, thank you!

@tycho25 2 года назад

This method is easily applicable to octrees as well. Thanks!

@elijahlucian 4 года назад

damn. coding live is like the ultimate pair programming

@doctortrouserpants1387 2 года назад

excellent video - really helpful to see you work it out as you write it, I learned a lot, very clear and understandable. thanks - subscribed!

@alexkuhn5078 Год назад

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.

@mukulbhave Год назад

Wow. Simple, to the point demo

@mootimadness7825 6 лет назад

my fave channel :)

@Dante3085 6 лет назад

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 ?

@skaruts Год назад

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. :)

@xthomas7621 5 лет назад

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

@xiaoraymond941 3 года назад

Nice! Learned a lot!

@brookestephen Год назад

you need at most 2 xy points to define a square, and 4 xyz points for a cube, so nodes or boxes or whatever don't need dimensions, just 2 points to decide where to store a particle in each iteration. Perhaps you only add quad levels when you're adding a second point at that same node... and not until then... with a preset maximum depth.. moving already noded points to downstream quads. Perhaps this datastructure can be used in real time, with particles assigning themselves to the proper node at certain times, and events are raised when other particles are within their zone of interaction? Real Particles have a size, so edge-cases become even more complicated!

@orr4945 6 лет назад

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 :)

@TheCodingTrain 6 лет назад

Yes, thank you for these corrections!

@TheCodingTrain 6 лет назад

Yes, thank you for these corrections!

@ilieschamkar6767 3 года назад

So instead of using log10, we should use ln or it's a generic log?

@orr4945 3 года назад

@@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

@ilieschamkar6767 3 года назад

@@orr4945 I've read in a comment that technically it should be log4, because we are dividing each quadtree four times Thanks nonetheless :D

@Error-pb6ee Год назад

great class! i enjoined and learn a lot! thank you!

@TheCodingTrain 6 лет назад

Wow, so much excellent feedback! I've created this repo -github.com/CodingTrain/QuadTree - in order to allow pull requests to improve the implementation.

@JariOrSomething 6 лет назад

The link is broken, remove the ")" at the end of the url :)

@TheCodingTrain 6 лет назад

thanks should be fixed now.

@rasmadrak 3 года назад

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"

@Pompiduskus 6 лет назад

Awesome vids. =))) Super nice

@StarContract 6 лет назад

A general note about optimization: In many programming languages it's not a good idea to use the *new* keyword every call to update(). Reason being - in many cases this means that the operating system needs to talk to your hardware to allocate extra memory for the new object, and it carries a lot of overhead. This can be avoided in many cases. For example, in the case of the quadtree, it is possible to bound from above the maximum number of nodes that you'll ever want to use (probably depends on the max number of allowed collidable objects. What you can do is a technique called pooling. You pre create an array full of rectangles ready to be use() and release(). When you want a rectangle you query this array and get a reference returned to you, and you just set the values, and set a flag to 'used'. When you're done, it simply sets the same flag to 'free'. Since the quad tree is potentially and probably rebuilt every frame, this can significantly boost performance. Note: it doesn't reduce the amount of operations, but it cuts overhead which in practical scenarios might play an important role. For further reading Google 'pooling programming'.

@IDontReadReplies42069 4 месяца назад

lol, who are you teaching? I'd say this is pretty common knowledge.

@avananana 5 лет назад

"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)

@jjppmm29 6 лет назад

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

@shubhratiwari473 6 лет назад

Thank you sir you are the best

@drallisimo34 4 года назад

cool tut!!!

@theodopoulos 2 месяца назад

Thank you!

@jasonw519 5 лет назад

I like your video. it is very straighforward.

@CodeVault 6 лет назад

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;

@TheCodingTrain 6 лет назад

Oh, great tip, thank you!

@linnealager6146 9 дней назад

Grid is better for moving objects with similar size. If the objects are static and of varying size, a quadtree is very helpful.

@jacksondice5435 3 года назад

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.

@MrRys 6 лет назад

When you were talking about the west on the right side, I was like "wow I never noticed, your camera records in mirrored image"

@TheCodingTrain 6 лет назад

😂

@allfreetechhub 4 года назад

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?

@youngsambyun5854 3 года назад

Thank you !!!

@AlexanderBollbach 6 лет назад

can you do some videos on 2d physics engines? hit detection, collision resolution, angular momentum, etc? its too hard to learn on my own!

@dvdrtrgn 2 года назад

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 2 года назад

Thanks for the feedback! Are there some specific moments or bits of code you can share that I should take a closer look at?

@dvdrtrgn 2 года назад

@@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!

@maribakumon 4 года назад

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?

@Shannxy 11 месяцев назад

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?

@LeslieSolorzanov 3 года назад

That bell is going to drive me crazy. D:

@IbakonFerba 6 лет назад

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 3 года назад

I don't understand why there is no response to this valid question. Do you have anything that you can add to this yourself?

@rocksfire4390 3 года назад

@@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.

@Fogmeister 3 года назад

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?

@kayfoster7385 3 года назад

@@Fogmeister however you want i guess. but i think it would treat two points as 1 though it takes 2 slots in your array.

@Fogmeister 3 года назад

@@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.

@Blazs120gl 6 лет назад

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!

@ChrisFotosMusic 4 года назад

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?

@danielmalka6824 Год назад

hi thats a great video! wonder, can i just use the QuadTreeNode ? it seems that i can save some cpu.. no?

@adri2350 6 лет назад

You're a genius !! When I see that I wan't learn Javascript !

@pekerchou2119 Год назад

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.

@JCOpUntukIndonesia 6 лет назад

Hi Dan, I love your channel so much and Thanks for the videos. I kinda curious, do processing or p5 have a matrix calculation built in it so that we can perform a vectorized calculation?

@Boom2219 6 лет назад

Matrix and vector arithmetic is very simple to implement yourself if it doesn't.

@JCOpUntukIndonesia 6 лет назад

Thanks Conrad. Sure do, but if we implement them ourselves, can we really avoid the for loop? while if there are built-in matrix calculation, we can avoid looping with vectorized code and the implementation would be faster of course.

@OneShot_cest_mieux 6 лет назад

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.

@redhen 6 лет назад

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.

@OneShot_cest_mieux 6 лет назад

Red Hen dev yes it's that

@nnhovogliadiscri 4 года назад

I love you!

@i.c.weiner556 6 лет назад

Have you considered using quaternary numbers to reference section?

@Freedomkwok 2 года назад

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?

@brucewernick6542 Год назад

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.

@brucewernick6542 Год назад

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.

@Flocksta 2 года назад

How would you make the squares to be more like rectangles or any other shape? So they are not even squares within squares.

@aleph618 11 месяцев назад

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!

@damnit258 6 лет назад

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 !

@Megasyl200 6 лет назад

17:30 -> with es6 you can do something like : let { x, y, w, h } = this.boundary;

@TheCodingTrain 6 лет назад

thanks for the tip!

@Ubayla 6 лет назад

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.

@danielturcotte6213 3 года назад

@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 = []; }

@axelbrinck_ 4 года назад

can you use quadtrees to detect collision if you are not using points but circles?

@lumichlle1422 4 года назад

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!

@CivilF11 4 года назад

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!

@tycho25 2 года назад

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

@relart6682 4 года назад

Hello! I have a problem with the insertion function, I dont know java, Im using GML(gamemaker language) which is object oriented. I've been watching this video for like 8 hrs straight trying to figure out how to store object or class(if its how you describe it in java?) coordinates in to an array(which is the points array). is it the object you're storing in the array or is it the objects coordinate? or both? or am i doing it wrong? any tips? thankyou for giving a time! :)

@CivilF11 4 года назад

So one thing that might help is that this is done in javascript, not java! Fundamentally different languages. In his code, he is storing Point objects (objects are *instances* of a class) in the points array. The points themselves then contain the coordinates. So, he would call a points coordinate by saying this.points[0].x; I do not personally know GML or how strongly typed it is, but what you want in this example is an **array** of **points**. So like you said, it is the object he is storing in the array.

@1schwererziehbar1 Год назад

This man does the equals sign at the beginning of the Google query.

@loic.bertrand 6 лет назад

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 ^^

@redhen 6 лет назад

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.

@misode 6 лет назад

No they aren't. A point is only in one of the four quadtree's.

@misode 6 лет назад

Actually what's happening is when a fifth point is added, the four original points are not divided into the four quadtree's.

@justalaugher 5 лет назад

I was laughing so badly hahaha.

@Besmudged 6 лет назад

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)

@ABaumstumpf 6 лет назад

His tree is a bit "special" :P

@downstream0114 3 года назад

How does it handle points on the edges of quads.. and the edge of the outermost..

@therationalplanner1574 3 года назад

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

@pgrafhamster9160 4 года назад

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?

@alexandresoutonogueira7675 2 года назад

36:30 hurts my eyes. just return a conditional with an OR operation with the 4 method calls

@viniciusdemoraesnascimento7055 3 года назад

Great Shiffman!!! o/

@AnthonyCook78 4 года назад

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.

@CivilF11 4 года назад

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!

@frederikja2210 5 лет назад

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!

@br3nto 4 месяца назад

Why quad and not binary here? Why divide the space by 4 instead of 2? Does it make the implementation easier with 4?

@BB-dv8nu 6 лет назад

Nice! I always wonderd how colision detection is reduced to a useful amount of checks.

@dutchdykefinger 2 года назад

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

@sagramor 6 лет назад

Thanks for that wonderful channel) Your videos make coding fun! I hope one million subscribers get very quickly \_0_0_/

@kjanimates Год назад

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;

@TheJuliMf 6 лет назад

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)

@TheCodingTrain 6 лет назад

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.

@svens3722 5 лет назад

one question. Where is the x Position from the boundary, its centered or its topleft Corner or something?

@angelrodriguez1776 4 года назад

x and y of the boundary are it's top-left position. (x, y) are offset by width and height (or w and h in his examples)

@Tasarran Год назад

In your insert function, you almost had it, you only have to put the equal on two sides, solves the point in both.

@jmfairlie 6 лет назад

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);

@TheCodingTrain 6 лет назад

Thanks for the tip!

@sanchitverma2892 5 лет назад

UwU

@Johnsmith-fr5zj 6 лет назад

I did a collision detection quadtree for 2d polygons and it took me 10 plus hours 😂

@wiscatbijles 6 лет назад

The number of checks is actually 10 choose 2. 10! / (8! * 2!) = 90 / 2 = 45. The combination rule!

@haozhou1791 5 лет назад

Create video. I have a question. What should I do if I have to deal with polygons instead of points? For example, I want to check how many polygons intersect (contains, contained or overlap) with certain region? I guess this is called Region QuadTree. Do you have similar tutorial? Thanks.

@haozhou1791 5 лет назад

Do you have any RTree tutorial video?

@JpmMantovani45 6 лет назад

You're so awesome, thanks for all

@adobeadobe1616 11 месяцев назад

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.

@GTexperience_Channel 10 месяцев назад

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?

@robbie_ Год назад

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.