Coding Challenge #98.1: Quadtree - Part 1

hello welcome to a coding challenge in this coding challenge I am going to attempt to make a quadtree now you might be asking yourself and it's a perfectly appropriate question what is the quadtree what is a quadtree and why do I care well let me talk about that over here so something that you might have noticed in many many many of my videos and various things that I've made is look at this beautiful marker how really made a nice rectangle there that I create a lot of systems that have a lot of what you might call particles in them or little agents that flock around the screen or that bounce around or bump into each other at magnetic forces and one of the elements of doing it one of the elements of these kinds of scenarios is that for every particle for every dot for everything that's in my two-dimensional space I have to check its location relative to all the other ones so this one I need to check relative to all the other ones this one I need to check relative to all the other ones and that is a lot of checks for example if there are ten if I have ten particles and I want to know the distance between each particle and every other particle I need to perform ten times ten checks which is 100 now of course there are like little optimizations there that I can reduce the number a little bit but but at its core this is the idea so this is what's known as an N squared algorithm because I have n elements and I need to do something N squared amount of times which means if there were a hundred then suddenly I need to do ten thousand checks and if there were a thousand or something to do one what million checks the pinkie maybe I'm not so sure so you'll notice that these are going up by a factor of ten but these are going up by a factor of well not ten ten squared and more right because this is a hundred times this and this is a thousand times this so it's its X button so this idea here that we can we do better well I have an idea for you because I'm really thinking about this my idea is well okay what if I know I know I know I know I got this what if instead of like for this particular particle right here instead of checking all the particles why don't I just check the ones that are near it like within a slight range around where it is okay but how do I know which are the ones that are near it okay let me check all the particles and see which ones are near it but I'm then I am checking all the particles again is there a way that I somehow could create these sort of regions of particles and then ask give me just the particles within that range without having to then suddenly go through all the particles and in fact there is such a way and that one way there are many ways is known as a quadtree now the reason why it's called a quadtree is that the idea is to take a space and section it into four four sections quad and each of those sections could potentially be sectioned into four and those could be into four and the reason why it's a trie is that the sections I don't know if there might be about the cells the tiles actually include references to their sub sections and so it's like a tree and there's going to be a recursive algorithm here so we're gonna start with this idea of a rectangle and that rectangle will store a reference to four rectangles and each of those four rectangles will store a reference to four rectangles but here's the thing they only are going to need to store to store reference to these children rectangles if there are a lot of particles in their area otherwise they can just keep track of their particular particles so the idea is that I can take all of these particles register them inside of this quad tree and then the quad tree is something I can query to say hey think about this this part of the window is part of the canvas just give me everything that's there and it's going to reduce the number of checks by a lot I'm pretty sure I should go look I think this is most likely turning this into n log n so instead of N squared and this has to do with something called Big O notation which is the way of notating how expensive or how long an algorithm takes based on the number of elements that are part of that algorithm so an N algorithm is wonderful because if there's only draw I just want to draw ten things that's an N algorithm check everything against everything else that's N squared and log n is going to reduce that number quite a bit let's go to the Wikipedia page for quadtree to see if I'm right about that okay so this is the Wikipedia page for quadtree it this reminded me that I that are there that I didn't mention that there are also other kinds of trees like an ox tree which you might use for three dimensions and you could just say K tree for any generic amount of sub sectioning but but I'm gonna really just implement the sort of standard quad tree also known I believe as a point quad tree and if you look here it says operating in O log n time so you might have a thought that I got this wrong because I said n log n but I think I'm actually correct here because the idea here is that to look up a bunch of particles for one for a given area that can happen in log n times but in this where I want to check every particle against every other particle I need to do the log n thing n times so this like let's just say let's just go for let's look at the 1,000 instead instead of 1 million this would be equals one thousand times log of one thousand which is just three thousand checks this is a massive improvement a question has been asked in the chat wouldn't you have to restructure the quadtree every time an object moves and in fact the answer to that question is absolutely 100% yes this quad tree is something that work for collision detection that you have to build each frame of animation and there is a lot of time that it takes to build the quad tree but it's totally worth it because if I can get this one number down to three thousand and just think about it if I had ten thousand elements how much I'm gonna be able to reduce it it's worth building the quadtree okay so what do we need to make this quadtree I'm gonna do make an example using p5 but I'm going to and let me make another JavaScript phylum to call it quadtree je s so this is where so I even though I'm going to use p5 for this example I'm gonna write the quadtree algorithm in JavaScript with no p5 dependencies that way it can be applied you know to lots of different scenarios with other frameworks ok so what do I need to build a quadtree well I need a few kind of core elements here for example I want to have a point class and a point class is just going to be something that stores an x and a y together and again I'm gonna be doing a quadtree in two dimensions I also want to have a rectangle class and a rectangle class is going to be I could have a point you know what I'm gonna do something a little goofy I'm going to give it an X and a y and a width and a height so I need these ideas I need to be able to make and and I couldn't use a p5 vector for the point class but again I want to build this without any p5 dependencies so I need these data structures because the what I'm gonna the way I'm going to make this quadtree work is by feeding it points I'm going to say insert points into the quad tree and the quad tree is going to have as part of itself references to all these rectangular areas ok so now let's make a quad tree class so what do I need to make a quad tree now here's the thing think about this a quad tree hoo boy you might go back and look at my binary tree video tutorial or some of my other videos that have to do with recursion because it's what you might think is oh I'm going to have an array and the array is going to store a list of all of these sections or tiles or but I'm not the quadtree is actually a reference just to the large kind of parent the sort of root level rectangle that area and it's gonna have a reference to the four things the four subsections and those a lot of reference of four subsection so that's a tree so actually a quadtree only has the only bit of data that I really need and we'll call it a boundary this stop boundary and that boundary is going to be a rectangle so for example in sketch KS I might say let QT be a new quad tree and I might say let boundary EB a new rectangle and you know what I think it's gonna make life easier if the rectangle is something that we think of as centered registered around its center point and those width and height values are actually just the distance from the center to the edge so not the full not the full length of each sides but the half length so I'm gonna say the boundary is at 200 200 well with a width of 200 200 that's kind of awkward but fine because it's 400 400 okay so I'm going to create this quad tree with a boundary console dot log Q T so this is like a beginning point a starting point so let's take a look rectangle is not defined because I forgot to reference my new JavaScript file here in my HTML file quad tree as a boundary of a rectangle it has these properties so so far no errors we're moving along now what do I need to do next the thing that I want to do with any quad tree is I want to say something like let me make a little loop and I'm gonna just do it one time and I'm gonna say a point I'm gonna make a random point and a random area in the canvas and I want to say quad tree insert that point the idea is that what I want to do is I want to take all the points that are within this space and these points might represent particles any type of moving age entity but right now I'm just gonna build the static quadtree with static points I want to insert them into the quadri so an important aspect of the quadtree is a property known as capacity so how big is the quadtree when do I choose that I need to subdivide for example if I start putting particles in this section here oh maybe once there's 10 particles in that section it's gotten too big I need to subdivide it so we can we could a typical thing might actually be to just have that actually be one as soon as there's more than one particle in that area subdivide but let's give it let's pick the number 4 it's kind of an arbitrary capacity and it might make sense to create a quadtree with a given capacity so when you create it so I'm gonna say capacity equals n so now in sketch I'm gonna do quadtree boundary comma 4 so this is a quadtree with each section each rectangle having a capacity of 4 ok was just pointed out to be that I did have a mistake here this should be height you know it is a square so width and height are equal but if I want to set myself up for success in the future let's try to correct that put height there ok so now I need to go here and I need sure what do I need to do I need to write this insert function insert and what do I want to insert a point and OH what I need to do here so oh wait a second I'm missing something super important what is the quadtree what is each tile need to have associated with it well we know it needs its boundary we now know it needs its capacity but it also needs to keep track of a bunch of points that are part of it so what I can do here is say as long as the length of the points array is less than the capacity then I can just say this dot points push push what the point I've inserted the point now what if the capacity is full well if the capacity is full then what I need to do is subdivide so I'm going to make this into a separate function I think if you look at the Wikipedia page the algorithm that's outlined there kind of does the same thing so I want to make a function called subdivide and what that function does is it takes any rectangle object remember that has an X Y and a width and a height and subdivide it into four sections over there and so all I need to do is compute these four points and these four width in Heights and I'm going to store those in variables and a way that you could do this right I think I've done this is like top left top right bottom right bottom left another thing that I've seen done is on north so north east is this Northwest Southwest southeast and so that's the sort of convenient way I can refer to these styles these subsections as Northwest northeast Southwest southeast so just to be kind of concise about the words I'm going to use I probably should type these all the way out actually so let's do this this dot north-west equals a new quadtree so I need to make all of these subdivisions south north east south west south east okay so this is gonna work so each one of these I'm making a new quad tree for each one of these set subsections but they need to when you make a quadtree you need to give it a boundary so what I need to do is say I'm gonna say let North let North West equal a new rectangle that is so North West is up here X plus width divided by 2y minus height divided by 2 and then with divided by 2 height divided by 2 so I'm gonna make a new rectangle that at this dot X plus this hot w divided by 2 comma this stop Y minus this dot H divided by 2 and then this w divided by 2 this dot H divided by 2 so that is the boundary for the northwest northwest quadrant and then I'm going to pass that in here and then I'm going to do the same thing for northeast for Southwest and southeast so now though northeast would be X minus and then Southwest and southeast R plus Southwest is X plus and the southeast is X minus so does this make sense right plus minus plus minus and then minus minus plus plus so I think I've gotten all the quadrants here so I've made rectangles out all the quadrants and put them into variables now here's the thing I don't always want to subdivide right I only want to subdivide if I haven't already subdivided this quadrant this this quadtree so I could check I think what I'm going to do is I'm gonna make a variable called divided which is false and then I'm going to say if not if not this dot divided this dot subdivide and then this dot divided equals true now what I need to do is if I'm at capacity I remember I'm inserting a point the whole thing that I'm doing here is inserting a point I've made a pretty big error here I've gone off the deep end writing way too much code before testing it there is no this refers to this particular quad tree there's no this dot X what there is is this boundary X boy this is going to make this super long-winded let's do this I kind of feel silly doing this but I think this is going to make our life much easier just in terms of being able to read the code so I'm gonna make this is totally unnecessary but just to make the code more readable let's make some local variables to this function that are kind of like aliases to this longer way and then I'm gonna start over again and I'm gonna say X plus W divided by 2 y minus W divided by 2 W divided by 2 H divided by 2 and this should be H and now I'm gonna put these all back here north east south west south east and this is X plus X minus X plus X minus y minus y minus y plus y plus mi right finally West and Easter swapped Oh also West the Easter SWAT boy northeast I'm gonna do it this way northeast northwest yeah south east south west right because east west if this is the center right east to the west north to the south ok everybody I think I've got it now oh boy so now I'm gonna now I need to pass in those boundaries north east no north east north west south east south west really bad feeling that about 15 minutes of this video is me just trying to figure out north south east west the good thing is that parts done I think we're good now ok so I'm feeling pretty good about this code there still could be an error there but I'll find it later if there is so remember where we were we were checking if it hasn't been divided subdivide it and now what's the whole point remember the whole point of what I'm doing I was just saying this before I found all those errors are the chat found all those errors that I'm trying to insert to point so if I'm at capacity now I just need to insert the point in my subsections so I can actually say remember these subsections are all quadtrees so I can recursively call the insert function on those so I can say this dot North East dot insert that point so let me do it to each one of these north west south east south west so think about this I'm gonna get rid of some of this extra whitespace the idea here is that okay if I have room I'm gonna take the point and I'm done if I don't have room then I need to check do I have some children quadtrees if not ah if I don't I'll make them and then I'll just say add I'll just sort of say hey pass the buck here you take that point all four of you and all four of those will say do I have room but here's the thing I'm missing something kind of important here should I really be taking that point and I kind of made sense at the beginning that I just said well why I've room take the point but really I should be checking is this point something that's within my boundary that's the whole point of this because now that I'm gonna say hey all four of you only one of those should really actually take the point right those so what I really need to do before I even insert the point at all is I need to say something like if if this dot boundary contains the point and better yet something like if this stop boundary does not contain the point then just get out of here like I don't want to do anything if I'm ignoring I don't contain the point stop don't go any forward I'm the wrong path I'm the wrong section some other sections gonna take care of it this dot boundary dot contains well that means in my rectangle function I need a contains function that returns true or false based on some point so what I can say is I could say hey is or I can actually just return point dot X and this is going to be really long point dot X if it has to be within all of the bounds so it's got to be greater than this dot X minus this dot W and and I can put these I think on different lines just to point dot X is point dot X is less than this dot X plus this W and point dot y is less than is greater than this y plus way this is a really exciting thing in programming and point dot y is less than this dot y plus this dot H oh my goodness minus and plus right remember contain contains contains this is a function that checks if this particular point is within the boundary so is the point is a particular point within the center - the width and the center plus the width the center - the height and the center plus the height and I'm gonna stare at this code for a second to see if it's right ok I feel like that's pretty good so why not let's keep going here so if it's not in here go away otherwise if I'm not a capacity add the point if I'm not divided subdivide and then just try to insert to all my all these children points now I feel like I need insert to kind of like return true or false but I guess because at some point it's gonna be done but I think this is actually pretty good ok I had a nice suggestion from the chat which that maybe it makes sense to in the subdivide function actually set this dot divided equal to true okay so let's let's think about this how am I doing here what is this gonna do let's let's actually try running the code all right so I have a boundary its capacity is four it has a points array and it got a point that's good that's great let's add four points all right look at this I've got a boundary I've got a capacity divided is false and I've got four points great so now if I add five points it's definitely gonna have to subdivide let's see how that works let's add five whoops let's add five points now it could have changed the capacity of the smaller oh we've got a problem so look at this when I when I set in the constructor this property n as the capacity but when I make these new quadtrees I'm not passing that in so I could like do something like this but I think let's just I made this a little extra complicated but let's pass in also the capacity so that capacity needs to continue to be there now let's try with five points all right look at this it's got four points where's that fifth point where's that fifth point it's not in the North West East it's not in the North West it's not in the southeast it's in the southwest because does this seem right the point is 104 354 that sounds like South West yes West it's this way south it's this way so I think this is working I think we're kind of getting it subdivided correctly let's let's try 50 points no errors I've got a quadtree with a capacity of 4 it's got four points North East has a capacity of four it's divided it's got four points it's got a bunch of subsections which of which have this one just has one point but maybe this one has no points so I think it's is working but here's the thing is this working looking at the console is only going to get me so far I think what would help me now to see if this is working really is to visualize it so I'm gonna break with what I said at the beginning whoops which trying to purely have this I I think what I want to do I mean I kind of want the quadtree thing to be independent of p5 but I'm going to give that up just for a second because I want to write a function called quadtree show and what I'm gonna do here is I am going to write out a function called show and what is this going to do I'm gonna say stroke 255 or let's a stroke 255 no fill and I'm gonna draw a rectangle at this stop boundary dot X and this stop boundary dot Y and this dot W times two I need to say times two because p5 expects the full with this dot H times two so I'm drawing the rectangle for the boundary and then sorry I'm thinking about this for a second and then I'll write then if then I want to recursively draw any of its children boundaries so if this is divided then I can say this dot North West Show so I want to recursively north east south east south west doesn't really matter what order but just to be consistent northeast northwest southeast southwest let's take a look a rectangle is not defined quadtree jsf wrecked in p5 w is not defined line 73 oops this should be two and then let's see here background zero alright what happened here thankfully the chat is here to tell me that this is this dot boundary right I'm always confusing forgetting that the X Y width height properties are in the boundary object not part of the quadtree object itself so you can say this boundary H so let's see what happens now there we go Oh everything looks like it's right but off kilter and this is an easy one I forgot to say rect mode Center because I want to draw the rectangle space on the center there we go this looks good now let's actually draw the points point let's say for for let P of points this dot points and let's just say point O P sorry point P X P dot Y so this isn't very many points and it's very hard to see those so let's say stroke wait for and stroke wait one up here stroke wait one and let's go to sketch J s and let's make 500 points and there we go this kind of makes sense right you can see for whatever reason there are not as many points here so it didn't need to subdivide but it's sort of idea we never got anywhere to subdivide beyond just this size right is there any so what's kind of unfortunate about this is why not because I'm calling things randomly about kind of setting the points randomly the subdivisions are just like perfect it's so evenly distributed distributed that the subdivisions aren't that interesting let's change this I have an idea let's actually add let's get rid of this whoops let's say let's add let's add the draw function and I'm gonna say if I could use Mouse drag but I'm gonna say if mouse is pressed and I'm going to say because I have an idea here I'm gonna well first I want to always draw it and then I want to make a new point where the mouse is and I want to insert that point and I need that this to be a global variable now the quadtree itself I'm just gonna call it tree because I don't like QT is sort of a I think it'll pick a little bit more I guess I'd call it Q tree kind of like that Q okay so bear with me for a second what I'm doing here is I want to insert points where I'm clicking the mouse so with this show of undefined oh whoops I do not want to read Eclair Q tree with let so we can see as I draw it has to subdivide more where I am that's kind of cool is it what's why is the framerate seem so slow so let me actually insert what I wanted to do was just insert a bunch of points I think this will make it more interesting to look at like if I actually insert five random points whenever I'm clicking the mouse and we can just set these like a little bit randomly around one area and let me run this again yeah so you can see I'm just getting these like subdivisions and so now we can sort of see that what I'm doing here and is I'm getting a nice it's subdividing more where it needs more subdivisions if that makes it out I'm being asked a couple different questions from the chat number one is edge cases and what I mean by edge cases what if the point is exactly on the edge of one of those sections I didn't account for that the truth of the matter is that these random numbers and floating points but this could really happen so what I think that I need to do here is in the insert function in the contains function what I need to do probably is just consider whether it's less than or equal to and I could do that on just two edges so that it would kind of but you know what if it's on the edge of the very edge I don't know what I could do is just kind of inclusive how do you write these like this and this should take care of that because I'm gonna I'm gonna just say if you're on my edge I'm gonna I'm gonna I'm gonna take you don't worry and I probably could get not but I'm not concerned too much about the accuracy of this and you can see so same same thing and interesting it's really subdividing a lot in these areas I could so here we go so this is kind of this is kind of an interesting visual result like I almost want to go back to not drawing the points now like let me take out the points because now I'm able to draw I'm kind of like with my mouse I'm drawing this kind of interesting recursive tree pattern it's not doesn't seem like a tree but it's all if I were to unpack the way it's stored its all this nested tree of rectangle objects okay so what am I really done here I have made the quad tree but I'm missing kind of a really important point because what I want to use the quad for is to query it I want to say hey this area could you please give me all the particles back that are in that area and I think what I'm going to do is make that part 2 of this coding challenge because this first part of the coding challenge is is I can is is finished I've made the quad tree data structure and I'm storing the points in it ah there was I do want to address one question is oh yeah this will add okay so hold on I realized that so the thing is it is it is going to add it to more than one of these which is a problem so before I leave it was rightfully pointed out to me that the way I just did that with equals is that it would actually go into if it was exactly on the edge between like east and west it would end up in both of these quad trees which is a bit of a problem so there's a couple ways I could address that again though what I think what I want to do here is I want this function the 'insert function to return true or false whether it's succeeded in in in inserting the point so it should return false if it's not contained and it should return true it should return true if it is actually inserted into the points array and then I could just say if I can wrap each one of these I can actually just return the result of each one of these right so that way oh no no no no no no no I can't do this because they don't want I really have to say if it insert only if it's true return true if this is a little awkward but this is fine oh yeah you know you know me I like to refactor later so what this is gonna do is it's just going I could use an else at least I guess right because I so what I want to do is I want to find it's gonna you know I want to find where it's been where it's got inserted and then I want to return true okay so all this extra stuff I'm adding here maybe this is silly and I should have just used thought of the boundaries more carefully but this is going to guarantee that it's only ever inserted into one and it is giving slight preferential treatment to North East because it was on the boundary it's always going to go into North East as opposed will never get to North West but that's okay I think so let's just see if this is still working it is somehow I like imagining it's working faster but I don't think it actually is wonderful okay am I really at the end now ah there's a nice little there's yeah there's people are giving you all sorts of suggestions about how to improve this code I could use like an or and so I encourage you to make a much nicer version of this in your own code I'm gonna leave it like this because it's really explicit about the algorithm I do want to write some comments in here so I'm gonna finish with this first part one of quadtree I've made a quadtree in like only four and a half hours it took me and I'm gonna do a part two and in part two what I'm going to do is ask for a selection of point within a certain boundary and then I can apply that to a collision detection out a problem and make that collision detection problem much much faster okay so thanks for watching this part one and watch part two if you liked it'll be next-- and you can find a link to it in this video's description [Music]

Channel: The Coding Train

Views: 299,981

Keywords: live, programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, live stream, itp nyu, class, challenge, codingtrain, code challenge, code, quadtree tutorial, quadtree collision detection, quadtree implementation, quadtree example, quadtree data structure, quadtree representation, quadtree javascript, quadtree js

Id: OJxEcs0w_kE

Length: 38min 7sec (2287 seconds)

Published: Mon Mar 26 2018