Coding Challenge #98.2: Quadtree - Part 2

[@MrBetaJacques]

i love the "pretty good pretty good" with some points staying white XD

[@kenhaley4]

Another optimization: If the sub-quadtree you're looking at is _entirely_ contained in the range being queried, then ALL the points of that quadtree (including those of its descendants) can simply be appended to the *found* array. You don't need to check each point. This could be significant if the quadtree is very large and a large range is being queried. With this in mind, you might want to go back to your initial idea of concatenating arrays from the child qtrees instead of pushing points into the *found* array one at a time.

[@TheCodingTrain]

Thanks for this excellent feedback!

[@khoavo5758]

Thank you for this trick, did you come up with it?

[@kenhaley4]

@@khoavo5758 Yes, I believe so. I might have been inspired by another quadtree video or article, but I don't remember seeing this particular optimization. (It's been two years.)

[@Illu07]

pushing in this case is still good, but you push all of them, because concatenating is not parallelizable.

[@MikeWasteland]

@@kenhaley4 It was published by Behley in Efficient Radius Neighbor Search in Three-dimensional Point Clouds

[@bokkenka]

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

[@DodaGarcia]

Right?! That was so satisfying

[@gabechevalier1567]

It's always so satisfying to see the edits that you request in the livestream. I remember you saying something along the lines of "Right now would be a good time for one of those speed up things."

[@charbelsarkis3567]

The fast forward is cool

[@Tordek]

I have to agree with a comment in the previous video: You Node should either - Be a Leaf, containing Points - Be a non-leaf, containing 4 subtrees. because currently you have a (small) inefficiency in that any check _will_ check the 10 points in a node, even if they would have been placed in a different bucket. So, yeah, the "divide" function should go through all the points currently in the node and push them onto the children.

[@tofonofo4606]

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

[@kayfoster7385]

this is the first channel that makes me feel like i'm learning with my professor. you got what it takes to be a teacher lol

[@crumpuppet]

The staring at that intersects() function was perfect 👌🏼

[@dasten123]

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

[@skeletonrowdie1768]

your affinity with coding is amazing. I'd love to start coding like that. Right now my programs are spaghetti like crazy.

[@FinnSolieChannel]

After tge first video I thought I understood the quadtree. This video really showed me how it all works together. I hadn't understood that this would be passed a boundry to search within and it returns the points it finds within. I thought the boid, from your flock challenge, would pass in it's location and the qtree would find what qtree leaf it was in and return the points in the leaf. I was thinking that it would give some weird results on what points the boid would see. It was very nice to see where I was thinking about it all wrong and I loved the green highlight effect tied to the mouse cursor. Keep up the great work!

[@LeighzerCuber]

Can't wait for part three. These videos really make Quadtrees easier to understand, yet I can't quite imagine how the collision detection part would use a quadtree. Would you check a using static bounding range containing your moving object? Would the range you use to query depend on the objects speed? Can't wait.

[@liquidexw]

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

[@kevinm2666]

Man you are awesome and deserve so many more subscribers

[@chrisbenesch5799]

Hey there! Just subscribed to your channel, and might I say it's awesome to see someone who shows what programming is really like. Typos and bulk text editing galore hahaha. I just wanted to point out that BST and KD/Quadtrees all suffer in the basic implementation from a kryptonite known as the ordered list. Your implementation here isnt quite as prone to it, but BST (Binary Search Trees) lose their tree structure when loaded with ordered data. Just wanted to point that out to anyone looking to use this and immediately loads say gridded data with it. Random input data is good, but the best is starting from the center and working your way out. Theres also self balancing trees, like used in the C++ (my language) STL, but those concepts take all the fun out of it. Anyway, cheers and like you channel so far.

[@gaschneidr]

Dan you are the best! Tihs week I watched your neural network series and its amazing! YOU are amazing. I always struggled to understand how to put all the theory behind the neural network into code and you did that in such a way that answered all my questions. Thank you for that! Love your channel

[@TheCodingTrain]

Thank you for this nice feedback!

[@gaschneidr]

It is well deserved! Also, when I was following your tutorial on the neural network I implemented it in such a way that it can have multiple hidden layers set by the user. I know you probably can do it by yourself but would be nice if you wanted to check it out. Just a ps I'm currently still watching your neuroevolution part of the series, so I don't have the code from the next videos.

[@TurnOnTheScreen]

This video shows the pros and cons of dynamic type programming language at the same time)))

[@lemonlordminecraft]

I'm kinda sorta amazed this works or is faster than the usual method. I always thought of doing this but never quite knew what method to use. This was very helpful. Appreciated.

[@johnydl]

I had a thought about my comment on a previous video When you subdivide modify the maximum number of points to 0 and move the items in the array into the leavesWhen the rest reaches

[@integralCalculus]

Absolutely loved both the videos! Awesome job.

[@RupertBruce]

quadtree divisionof 2D Sandpile (using 333-set) base 4 arithmetic using fractal colours (ie.palette selection based on how deep the quadtree is ). Mouse position adds to the sandpile using gaussian window function.

[@RupertBruce]

Needs 9 segments instead of 4

[@CyCloNeReactorCore]

awezome, i really want to see the code for this if you still have it

[@srijanpaul]

Awesome video Dan ! Would love to see more data structures. I was looking for reference because I wanted to implement this in my Love2D game.

[@CyCloNeReactorCore]

Technically this implementation is a bit faulty.. when you subdivide, you should also insert all current points into each child QuadTree aswell, as you can see, in your implementation, you get cells that have very large numbers over the capacity, and I think that this is the reason EDIT: this is also the reason why the QuadTree did not look as you thought it would.. with random for me, each quadtree looks unique, and intuitively as you would expect for the explanation he gave..

[@agent-33]

Dude. Just upload your tutorial. You seem to know better than him in this subject.

[@CyCloNeReactorCore]

@@agent-33 well, fundamentally, this is a huge flaw with what the quadtree is supposed to do, so i had to point it out

[@CyCloNeReactorCore]

@@agent-33 i think he actually fixes this in a future part on the quadtree, as well

[@DodaGarcia]

@@agent-33 It's not rude to note flaws in someone's implementation, it's how we make each other better devs.

[@QwertyNPC]

"you get cells that have very large numbers over the capacity" - no you don't. It looks that way because some points belong to parent tree and others to its subdivides. They simply share the same space.

[@Guil118]

Im now realizing that your code is getting cleaner with every challenge.

[@Kashfiii]

Make a tutorial for being a great person like you... inspiring as always.

[@youtub3ian728]

one of the best tutorials i've seen :)

[@skeletonrowdie1768]

TheCodingTrain: They are not not not not not not not not overlapping Computer: True

[@AneeshAbbineni]

For ranged forces and such, I would use a downgraded quadtree. Doesn't matter how many points are in each cell always constant size and number. This version would be much more suited for collisions.

[@DaleHawkins]

Very nice example. Very useful for my project.

[@richardbernard9873]

The reason some subdivisions contain more than 4 points is because the subdivision should also put all the points in the current rectangle into its children and leave it empty. Here, the parent is still at capacity with subdivision, so the visualisation is kind of misleading on which rectangle contains the points.

[@XKCDism]

I appreciate the edditing

[@gothor-channel]

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

[@gfdgdfgdfgdfggfdgdfgdfgdfg9709]

excellent video

[@likeyou3317]

Oh should've watched this way earlier... fun fact in processing this can work on 60fps - 10 000 000 points with a range of a circle with 100 radius (I added circle as a boundary in the quadtree) but beforehand u'd have to disable all the showing and printing on the screen. :D

[@pascha4527]

You count the same point multiples times. you must add the points to the array only if its not divided! I want to watch them live!

[@ben_jammin242]

Please cover the Vehicle Routing Problem 🙏. Ive been enjoying your series on quad trees and the TSP problems :-)!

[@riccardofantin8159]

Great argument! I love your channel.

[@deltametaYT]

A cool 3rd part could be animating the particles randomly and seeing the quad tree update itself in real time :)

[@deltametaYT]

Doh! I wrote this before the end. Sounds like that’s may be included in what you’re planning. Awesome. Nice work, loving these videos!

[@jensBendig]

Minute 3: I recommend to say to boxes: come as x-interval and y-interval. And then I speak to those intervals like: Do you overlap?

[@johncerpa3782]

This was awesome!

[@trejkaz]

There's a bunch of redundant checks going on because when you subdivide a node of the tree, you are keeping the N points at that node. Those N points then have to be checked regardless of what quadrant they would end up in. Instead, as soon as you subdivide, you could move all the points down into the correct quadrant. If it were me, I'd probably try to codify that behaviour in the classes, having a different node class for branches and leaves. Then the node never has to ask "am I subdivided?" That would require some redesign, as when a node changed from a leaf to a branch you would have to change out the reference the parent has to it. If I were doing this in production code, I'd probably even try to make the structure immutable, or, ideally, persistent.

[@QwertyNPC]

From what I understand this would make querying a bit better but inserting a bit slower since you'd still have to check every moved point to which quadrant it goes on insert/subdivision. I don't think there's a significant gain there if you are using the tree for animation.

[@Besmudged]

you may concatenate multiple arrays using one concat function with multiple arrays as parameters

[@sdegueldre]

Would really have liked a performance comparison

[@TheCodingTrain]

coming in part 3!

[@gumbilicious1]

my rectangle intersect function(s) in javascript. This would be a great include into p5 and processing as library functions, this is straight outta my utility library. ///////////////////////////////////////////////////////////////////// //returns true if one range intersects another range ///////////////////////////////////////////////////////////////////// function rangeInt(min1,max1,min2,max2){ return Math.max(min1,max1) >= Math.min(min2,max2) && Math.min(min1,max1)

[@k3ck3m3n]

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

[@rallymax2]

How are only 2% of views clicking thumbs up???? All hail the algorithm.

[@cristiiancu4814]

Try to make a challange for octatree

[@BleachWizz]

To invert the boolean expression you just swap all operators and invert all entries. In this case: > -> >= || -> &&

[@tabletopjam4894]

I’ve just finished translating this into Processing

[@tabletopjam4894]

I just added a circular search tool so you can search for points within a certain distance from any x y coordinate

[@kylemrosko321]

Really love you videos! It makes learning Javascript so easy and fun. This is on a much earlier video, but if I wanted to change the "Flowers" on your Space Invaders coding challenge to an image, how would I do that?

[@AmazingMaxStuff]

Should not the range be less every time you query it in the children quads?

[@misode]

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

[@OrangeC7]

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

[@NinjarioPicmin]

you have the power to do that yourself too :D just press the right arrow key or on mobile tap the videoplay red line a little further right. and you can also just play the video at 1.x speed

[@tycho25]

How do you go about querying a radius around a point?

[@aleixgabarro3247]

Can you explain in the next video Camera Culling with quadtree mode too? with the collisions. Thank you, you help me a lot with this videos ^^

[@APaleDot]

Shouldn't there also be a method for removing a point from the tree? Or do you just keep the structure of the tree the same and remove the point from the quadrant it is in? I think restructuring the tree would help performance, but maybe it wouldn't help enough to justify the cost of restructuring.

[@woltherfx]

Surely if a rectangle is subdivided it doesn’t need its points anymore and you can add them to its subdivisions?

[@ritikkhatri]

So beautiful

[@Daniel-wu9ui]

you could have checked if two boxes were overlapping using a AABB, so something like ((p1.center.x - p2.center.x) < (p1.half.x + p2.half.x) || (p1.center.y - p2.center.y) < (p1.half.y + p2.half.y)) ? true : false;

[@MaxPicAxe]

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

[@Jkauppa]

quicksort collisions, every frame

[@Jkauppa]

collision box test

[@Jkauppa]

hierarchical boundary layers

[@Jkauppa]

first is the box, then maybe a circle, then something more accurate, functions, voxels, triangles

[@gumbilicious1]

i just want to state to anyone wanting to implement the code, this was one of the more confusing coding trains I have watched. I implemented this in about 1/3 the time it took to watch the videos, all i did was look at the wikipedia pseudo code. I have an immediate use for this structure and wanted to implement it and was overjoyed to see a CT on this, usually I love this content and it does a good job distilling the concepts for me, but this one will probably lose you.

[@twistedsim]

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

[@espensandelarsen3539]

Awesome as always! Your channel and specially your coding challenges, really brings back memories from my demoscene coding days. I have a couple/three challenges for you! First is this network threshold linking thing: espen.sandelarsen.com/dev/js/gfx/graphEffects/ second is the Burning ship fractal: espen.sandelarsen.com/dev/js/gfx/shipJS/ and the last I will leave the implementation to you is the Buddabrot fractal. Keep up the awesome work!

[@TheCodingTrain]

thanks for the nice feedback and suggestions!

[@ilieschamkar6767]

the first one isn't simple made by linking every point in a quadtree in the end? If the points are close enough to be in a quadtree, then draw a stroke line

[@Blarggnugget]

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

[@kenhaley4]

No. You're assuming all the points are at the bottom leaves of the quadtree, which isn't true. When a node is subdivided, the points that it already contains are left there, and the children are created empty. There is much discussion here about whether it would be better to push the existing points down to the lower level, but Dan decided not to do that, and personally, I think it's better this way. Suppose all the points got pushed into the same quadrant. Now, the next point being inserted would cause another subdivide. This could cause many more subdivisions, especially if lots of points were clustered into a very small region.

[@Blarggnugget]

Ken Haley ok thanks. I did not realize the points where not put into the lower subdivisions

[@ABaumstumpf]

Ken haley - but like this it simply is not a quad-tree and he has some problems too - you can clearly see that he has quads with more than 6!! dots inside.

[@Blarggnugget]

your point is valid in the case of the boundary that encompasses multiple sections/quads and multiple levels of detail. it would be faster in that case to count the points in the highest level quad than recurse through all of its lower levels for the same result. the ultimate issue with not pushing the points into smaller subdivisions is that the quadtrees greater purpose is for the inter-particle collisions. pushing the points into the lower subdivisions/leaf nodes allows for at most (capacity - 1) collision calculations per particle(less with optimizations). if the dense regions are not subdivided as you think they should be then the number of inter-particle collision calculations is any number greater and approaches the n squared problem size as opposed to the desired nlog(n) size. sorry for my long response, thank you for reading.

[@TheCodingTrain]

Thank you for this discussion!

[@teamredstudio7012]

You have this habit of always adding like 5 lines of white space just to remove it again after only writing one line in that space.

[@stedi1986]

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

[@stedi1986]

That's what I'm thinking as well. In any case I think that that's a more relevant use case than having stationary points. If you're using quad trees to reduce the number of collision computations you have to make for example within a particle system then you have a moving system, and then these operations and their cost become quite important.

[@kenhaley4]

I'm thinking the same thing. But rebuilding the whole tree everytime things move could be disastrous, performance-wise, defeating the whole purpose. To avoid that we'd need a routine to check whether moving a point leaves it within the boundary of its qtree node--if not, go ahead and delete it and re-insert it. If so, do nothing. With particles moving slowly, perhaps only a small subset of the qtree would be affected in each generation.

[@TheCodingTrain]

It's not disastrous to rebuild the tree each time! Sure there are ways to improve but even with this the number of computation cycles are reduced significantly from n*n! See: codingtrain.github.io/QuadTree/examples/intersection_qtree/

[@kenhaley4]

Wow. I stand corrected! :-/ What was I thinking? I must have been thinking the tree would need to be rebuilt for each individual particle move, but that's obviously not the case. In fact we don't even need to touch the tree as particles move, until the end of the generation. Lesson learned.

[@A_Lesser_Man]

oh! i do see a glitch ... i'm having difficulty wrapping my head around it, though. when "dividing" ... some points will end up in differing quadrants...so it' LOOKS like five are in one quadrant when there isn't? i'm totally confused. shouldn't some points in the points array get "moved" into the new quadrant? ugh...so weird.

[@marcelennix5457]

i see it too ( in sw+1/nw+1 there are 5 points...). i replicated his code 1:1. the problem: if you add many points at +10,+10 it will crash because of infinite loop. if you add many points at +10,+10 and differ the position +/- just a little many, many new quads have to be added, but wont... sorry, but the code isnt really working in the end - but i learned a lot of the video.

[@NickHendriks]

Hey, this is SUPER LATE but I think I sorted out a solution to this issue. When you subdivide, you should also be iterating through this.points and inserting them into the child qtrees. Then set this.points = [ ] since you've just handed them over to the children, and then set this.capacity to 0 so it will automatically throw subsequent points to the child qutrees. This will ensure that every quadrant only ever has max 4 points.

[@NinjaDuckSauce]

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

[@numero7mojeangering]

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

[@Kaixo]

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

[@manuelhexe]

Can you make Pinball with Javascript?

[@therationalplanner1574]

Linear search is faster than your quadtree if you test processing times...

[@AssassinGrudge]

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

[@Fakkio2]

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

[@kingappl7187]

I got a question does this. mean that you dont use the variable that you declined in the top or in a part of a code instead you use a variable that has not the value of the variable but the same name? I wonder myself every time but I dont really get it I'm very thankfull for every answer :D

[@titouant1936]

Aren't the points supposed to only be in the leafs of the quadTree ? I am at 7:34 so maybe you correct that later in the video :D

[@titouant1936]

At 9:06 I agree :p

[@Besmudged]

Posted a similar question on part 1, usually, kd-trees only have point values stored inside the leaves

[@titouant1936]

Maybe in his repo but not by the end of this video

[@TheCodingTrain]

This has been raised by many comments, I should implement this and see how much it improvements performance. From what I understand is that it is "good enough" with leaving the points on the parent nodes. The algorithm as described on the wikipedia page for quadtree, for example, doesn't include passing the points down the tree as it subdivides. en.wikipedia.org/wiki/Quadtree#Pseudo_code

[@Besmudged]

okay, nice! It should improve running-time with the query operations, but increase the running-time on constructing the tree. The effect might not seem apparent if you're doing both at the same time

[@doshi050050]

what is the name of the atom theme that he is using?

[@OneShot_cest_mieux]

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

[@mickyr171]

Was hoping someone else noticed :p

[@dcs_0]

Also, I think he is incrementing the counter each time a point is found on each level, instead of just on one level

[@lepruconx]

i'm trying to do this in java, and i think a lot of the things that he does can only be done in js. at like 13:00 before he deletes it he logs "points" but points is just an empty array, right? so how did it give 160???

[@mindaugasdudenas624]

Processing version: github.com/dudenas/QuadTree/tree/master/part2

[@Naej7]

Description Squad I guess ? 🤔

[@roscocsa]

Frogger for intersecting rect() wasn't it?

[@eliasgrage2220]

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

[@TheCodingTrain]

Yes! You can always check all the points in an array and have it work, the idea is here is to try to reduce the number of points you have to check to speed up programs with many many points!

[@eliasgrage2220]

Thank you 👌

[@RupertBruce]

@12:55 ... Random seed + Unit test

[@RupertBruce]

@13:25 Visualisation wins again!

[@RupertBruce]

@14:50 Unit test FTW

[@RupertBruce]

@5:30 Unit test

[@isaacbaptista2167]

shouldn't the parent's points be passed down to the children?

[@MaxPicAxe]

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

[@johnydl]

As it is the tree has points in multiple levels of the subtree not just the leaves so to speak but no point is duplicated it's either in a branch or a leaf but not both

[@WindImHaar]

Hey dan, I really enjoyed this coding challenge and I'm really happy to have rediscovered your channel after you were the person that initially taught me how to programm :) I have been programming a lot of neural network and genetic algorithm stuff lately and this was a fun way to mix it up a bit again. I tried to achieve something similar to you going off of memory and I'm absolutely amazed at the performance improvement this method can get you. While tooling around in processing a bit I discovered this cool pattern, I just think it looks amazing: drive.google.com/drive/u/0/folders/168OcQNHCYH54csQQp20fTdu9YkJUKbcd Please keep on doing what you are doing you are a great and inspiring person :)

[@dashl5069]

I love your vids but reading your code with all of the non-symmetrical white space makes my ADHD go insane :)

[@AnthonyCook78]

let points = prizes

[@brandonhuynh6153]

Code Tetris!

[@oj0024]

For challange100 how about you upgrade you flappy birds game to be played by am an evolutionary neural network

[@oj0024]

nice you did it, lel

[@AdamBast]

He didn't say "I'm gonna do something goofy"

[@torcher5023]

Ну почему на русском ютубе такого нет?

[@anilaxsus6376]

what language is that

[@DavidSuper13]

javascript

[@kkrzys17]

My version of Flocking with Quadtree :) krzysztofn1993.github.io/Flocking/ -> if you open up console, you can change few parameters. A little bit of changes from me: avg position, avg speed and repelling force are calculated in same loop so it should be faster. In quadtree I am pushing points from branch to leafs when subdivision happens, also thought about rounding up position of boids to two decimal places (smaller precision should speed up calculation of al in my opinionl) but not sure how to implement this and if is it possible in p5, what do you think? Sorry for my english, it is not my native language.

[@m.c.4674]

quad tree seem out of beginner level, but I'm crazy so i made it.

[@ifelseprog]

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

[@IbakonFerba]

Corentin Girard idk how this works in interpreted languages, but in complier languages like C++ the compiler is probably intelligent enough to just ignore it, it is incredible how smart some compilers are. I mean, it is not necessary to write the else, but it probably does not hurt either and with the else it might be more readable to some people, and Dan always tries to write easy to read code ;)

[@ifelseprog]

You just have to understand what "return" means ^^ this has nothing to do with the compiler intelligence. Return basically means "end this function and give this result back" so nothing is executed in a function after a return statement... :)

[@IbakonFerba]

Corentin Girard I know, I was just saying that I think that performance wise it does not matter, it is just a "visual" thing

[@noxabellus]

lol get over it its much more readable and is compiled away

[@storerestore]

On the other hand, using else even when it has no distinct effect clarifies the control flow. It's a matter of style.

[@Donaldo]

Fun to watch but your tree is bad :D