title
Coding Challenge #98.2: Quadtree - Part 2
description
In this multi-part coding challenge, I implement a Quadtree data structure in JavaScript and visualize it with p5.js. Code: https://thecodingtrain.com/challenges/98-quadtree
p5.js Web Editor Sketches:
đšī¸ Quadtree Parts 1 & 2: https://editor.p5js.org/codingtrain/sketches/g7LnWQ42x
đšī¸ Quadtree - Part 3: https://editor.p5js.org/codingtrain/sketches/CDMjU0GIK
Other Parts of this Challenge:
đē Quadtree - Part 1: https://youtu.be/OJxEcs0w_kE
đē Quadtree - Part 3: https://youtu.be/z0YFFg_nBjw
đĨ Next video: https://youtu.be/KtPpoMThKUs?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
đĨ All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
References:
đž Quadtree repo: https://github.com/CodingTrain/QuadTree
đ Quadtree on Wikipedia: https://en.wikipedia.org/wiki/Quadtree
Live Stream Archive:
đ´ Quadtree Live Stream: https://youtu.be/MxnqJGwu2cc
Related Coding Challenges:
đ #65 Binary Tree: https://youtu.be/ZNH0MuQ51m4
đ #68 Breadth-First Search: https://youtu.be/piBq7VD0ZSo
đ #72 Frogger: https://youtu.be/giXV6xErw0Y
Timestamps:
0:00 Quadtree Part 2--query the data structure for points contained within a rectangular boundary
1:45 Write a query function to get all the points within a rectangle
3:16 Write an intersection function
6:14 Create an array of "found" points
13:00 Draw points within the rectangle
15:21 Sanity check--how many points are being counted
16:57 Adjust the rectangle with the mouse
18:44 Return the points array
19:42 Up next: apply the quadtrees algorithm to a collision detection problem
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
đ Website: http://thecodingtrain.com/
đž Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide
đŠ Suggest Topics: https://github.com/CodingTrain/Suggestion-Box
đĄ GitHub: https://github.com/CodingTrain
đŦ Discord: https://discord.gg/hPuGy2g
đ Membership: http://youtube.com/thecodingtrain/join
đ Store: https://standard.tv/codingtrain
đī¸ Twitter: https://twitter.com/thecodingtrain
đ¸ Instagram: https://www.instagram.com/the.coding.train/
đĨ Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
đĨ Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA
đ p5.js: https://p5js.org
đ p5.js Web Editor: https://editor.p5js.org/
đ Processing: https://processing.org
đ Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct
This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new
#quadtreedatastructure #quadtreecollisiondetection #javascript #p5js
detail
{'title': 'Coding Challenge #98.2: Quadtree - Part 2', 'heatmap': [{'end': 829.437, 'start': 805.696, 'weight': 0.784}, {'end': 1160.859, 'start': 1142.049, 'weight': 0.793}, {'end': 1227.621, 'start': 1225.48, 'weight': 1}], 'summary': 'Explores efficient point retrieval using quad trees, implementing new query functions, discussing quadtree intersection and recursion, array manipulation, and optimization of point search algorithm, aiming to improve performance and simplify solutions.', 'chapters': [{'end': 76.362, 'segs': [{'end': 46.866, 'src': 'embed', 'start': 0.967, 'weight': 0, 'content': [{'end': 5.816, 'text': 'Hello, welcome to part two of my coding challenge, Quad trees.', 'start': 0.967, 'duration': 4.849}, {'end': 17.565, 'text': 'So what I want to do in this part is I want to look at how I can retrieve a list of points from a given area without having and this is going to,', 'start': 5.836, 'duration': 11.729}, {'end': 20.027, 'text': "I don't have to, I could say this boundary over here.", 'start': 17.565, 'duration': 2.462}, {'end': 21.268, 'text': 'give me all the points in that area.', 'start': 20.027, 'duration': 1.241}, {'end': 24.73, 'text': "Well, I can just look through every point and see if they're contained within that boundary.", 'start': 21.288, 'duration': 3.442}, {'end': 33.977, 'text': "But the quad tree is going to allow me to do that more efficiently by kind of looking at the sections that are near this particular range that I'm going to create.", 'start': 24.99, 'duration': 8.987}, {'end': 35.538, 'text': 'Boy, am I not explaining this well.', 'start': 34.497, 'duration': 1.041}, {'end': 37.359, 'text': 'Let me explain this visually.', 'start': 35.718, 'duration': 1.641}, {'end': 40.301, 'text': "So what I'm going to do, let me just draw a rectangle.", 'start': 38.44, 'duration': 1.861}, {'end': 45.804, 'text': 'Let me say something like stroke 0, 255, 0.', 'start': 41.042, 'duration': 4.762}, {'end': 46.866, 'text': 'Let me draw a rectangle.', 'start': 45.805, 'duration': 1.061}], 'summary': 'Exploring efficient point retrieval using quad trees for given area', 'duration': 45.899, 'max_score': 0.967, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY967.jpg'}], 'start': 0.967, 'title': 'Efficient point retrieval using quad trees', 'summary': 'Explores the use of quad trees to efficiently retrieve a list of points from a given area, providing a visual explanation of the process.', 'chapters': [{'end': 76.362, 'start': 0.967, 'title': 'Quad trees and efficient point retrieval', 'summary': 'Explores the use of quad trees to efficiently retrieve a list of points from a given area, providing a visual explanation of how the process works.', 'duration': 75.395, 'highlights': ['The quad tree allows for the efficient retrieval of points within a given boundary, improving upon the process of manually checking containment for every point.', 'The visual explanation of using a quad tree to retrieve points from a specific range enhances understanding of the concept.']}], 'duration': 75.395, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY967.jpg', 'highlights': ['The quad tree allows for the efficient retrieval of points within a given boundary, improving upon the process of manually checking containment for every point.', 'The visual explanation of using a quad tree to retrieve points from a specific range enhances understanding of the concept.']}, {'end': 359.483, 'segs': [{'end': 120.538, 'src': 'embed', 'start': 91.783, 'weight': 0, 'content': [{'end': 97.405, 'text': 'But I want to ask the quadtree for it, because the quadtree is going to have the capability of giving me those points more efficiently.', 'start': 91.783, 'duration': 5.622}, {'end': 98.966, 'text': "It's not going to have to check every single point.", 'start': 97.425, 'duration': 1.541}, {'end': 101.347, 'text': "So let's see if I can do that.", 'start': 99.566, 'duration': 1.781}, {'end': 107.03, 'text': 'So in order to do this, what I need is in the quadtree, I need a new function.', 'start': 102.227, 'duration': 4.803}, {'end': 109.591, 'text': "And I'm going to call it query.", 'start': 107.93, 'duration': 1.661}, {'end': 111.852, 'text': 'And let me put it above show.', 'start': 110.691, 'duration': 1.161}, {'end': 115.214, 'text': 'Show is just sort of a drawing stuff, which is really just for debugging at this point.', 'start': 112.192, 'duration': 3.022}, {'end': 120.538, 'text': "I'm going to write a function called query, and it's going to take as an argument a range.", 'start': 115.795, 'duration': 4.743}], 'summary': 'Implementing a query function in the quadtree to efficiently retrieve points within a specified range.', 'duration': 28.755, 'max_score': 91.783, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY91783.jpg'}, {'end': 156, 'src': 'embed', 'start': 128.764, 'weight': 3, 'content': [{'end': 135.41, 'text': 'So the first thing I need to do is I just need to say does this range and this quad tree?', 'start': 128.764, 'duration': 6.646}, {'end': 136.31, 'text': 'do they overlap??', 'start': 135.41, 'duration': 0.9}, {'end': 139.712, 'text': 'If they do, then there might be some points that I want to give you.', 'start': 137.151, 'duration': 2.561}, {'end': 141.233, 'text': 'If not, it could be ignored.', 'start': 140.012, 'duration': 1.221}, {'end': 148.696, 'text': "And if it can be ignored, that means I don't have to check any of the points that are in it or any of its nested subsections.", 'start': 141.573, 'duration': 7.123}, {'end': 156, 'text': 'So the first thing I need to say is say if this.boundary.intersects range.', 'start': 149.017, 'duration': 6.983}], 'summary': 'Checking for overlap between range and quad tree boundary.', 'duration': 27.236, 'max_score': 128.764, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY128764.jpg'}, {'end': 224.431, 'src': 'embed', 'start': 175.538, 'weight': 1, 'content': [{'end': 182.544, 'text': "well, I've kind of got a bit of a problem here, which is that the boundary is a rectangle object and I don't see an intersects function.", 'start': 175.538, 'duration': 7.006}, {'end': 186.133, 'text': 'But guess what? I can write one, so whoops, idea.', 'start': 182.624, 'duration': 3.509}, {'end': 188.675, 'text': "I'm going to write an intersects function.", 'start': 186.634, 'duration': 2.041}, {'end': 193.059, 'text': "Intersects another, I'm going to say range, why not, range.", 'start': 189.716, 'duration': 3.343}, {'end': 197.142, 'text': 'So there was another coding challenge.', 'start': 194.46, 'duration': 2.682}, {'end': 199.175, 'text': 'where I had to do this.', 'start': 198.274, 'duration': 0.901}, {'end': 200.235, 'text': "I can't remember what it was.", 'start': 199.235, 'duration': 1}, {'end': 207.24, 'text': 'It was one of my early coding challenges where I had to test do two rectangles overlap or do they not overlap?', 'start': 200.255, 'duration': 6.985}, {'end': 215.805, 'text': "And I think there's a nice way of doing this with an or basically saying hey, if any of these conditions are true, they can't possibly be overlapping.", 'start': 207.68, 'duration': 8.125}, {'end': 224.431, 'text': 'For example, if the x of this one is greater than, well, the x, this edge, if this edge is greater than that edge,', 'start': 216.105, 'duration': 8.326}], 'summary': 'Developing an intersects function for rectangle objects to test for overlap.', 'duration': 48.893, 'max_score': 175.538, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY175538.jpg'}, {'end': 364.825, 'src': 'embed', 'start': 339.459, 'weight': 5, 'content': [{'end': 345.422, 'text': 'Also, it was pointed out it was the Frogger coding challenge where I struggled through this for a very, very long time.', 'start': 339.459, 'duration': 5.963}, {'end': 348.283, 'text': 'So I could go back and check my Frogger code.', 'start': 345.662, 'duration': 2.621}, {'end': 353.166, 'text': "And I probably could also use somebody else's library that has geometry math in it.", 'start': 348.303, 'duration': 4.863}, {'end': 353.926, 'text': "But let's move on.", 'start': 353.246, 'duration': 0.68}, {'end': 355.667, 'text': 'OK, so now.', 'start': 354.926, 'duration': 0.741}, {'end': 359.483, 'text': 'If, this should work.', 'start': 358.223, 'duration': 1.26}, {'end': 364.825, 'text': "Now, what if they do intersect? If they do intersect, ah, here's what I need to do actually.", 'start': 359.763, 'duration': 5.062}], 'summary': 'Struggled with frogger coding challenge, considering using geometry library for intersection check.', 'duration': 25.366, 'max_score': 339.459, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY339459.jpg'}], 'start': 76.602, 'title': 'Improving quadtree functionality', 'summary': 'Discusses implementing a new query function in the quadtree data structure to efficiently retrieve points within a specified range, checking for overlap between a range and a quad tree, and implementing geometry logic for rectangle intersection, aiming to improve performance and simplify solutions.', 'chapters': [{'end': 128.485, 'start': 76.602, 'title': 'Quadtree function for point query', 'summary': 'Discusses implementing a new function called query in the quadtree data structure to efficiently retrieve points within a specified range instead of checking every single point, aiming to improve the performance of point retrieval.', 'duration': 51.883, 'highlights': ['Implementing a new function called query in the quadtree data structure to efficiently retrieve points within a specified range', 'The quadtree is capable of giving points more efficiently without checking every single point']}, {'end': 224.431, 'start': 128.764, 'title': 'Checking overlapping ranges', 'summary': 'Discusses checking for overlap between a range and a quad tree, developing an intersects function, and recalling a previous coding challenge related to testing if two rectangles overlap.', 'duration': 95.667, 'highlights': ['Developing an intersects function to check for overlap between a range and a quad tree, with a reference to a previous coding challenge related to testing if two rectangles overlap.', 'Discussing the need to check if a range and a quad tree overlap to determine points of interest, and the potential to optimize the process by ignoring non-overlapping cases.', 'Exploring the concept of intersecting boundaries and the plan to write an intersects function to address the absence of such functionality in the rectangle object.']}, {'end': 359.483, 'start': 225.712, 'title': 'Implementing geometry logic', 'summary': 'Discusses the challenges of implementing geometry logic, particularly in determining the intersection of two rectangles, with the speaker expressing frustration and seeking a simpler solution, while also referencing a previous struggle with the frogger coding challenge.', 'duration': 133.771, 'highlights': ['The speaker expresses frustration in writing the logic for determining the intersection of two rectangles, seeking a simpler way to approach the problem.', 'Referencing a previous struggle with the Frogger coding challenge, the speaker mentions the possibility of revisiting their Frogger code or utilizing an existing library for geometry math.', "The speaker considers the option of using someone else's library that includes geometry math, indicating a willingness to explore alternative approaches to the problem."]}], 'duration': 282.881, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY76602.jpg', 'highlights': ['Implementing a new function called query in the quadtree data structure to efficiently retrieve points within a specified range', 'Developing an intersects function to check for overlap between a range and a quad tree, with a reference to a previous coding challenge related to testing if two rectangles overlap', 'The quadtree is capable of giving points more efficiently without checking every single point', 'Discussing the need to check if a range and a quad tree overlap to determine points of interest, and the potential to optimize the process by ignoring non-overlapping cases', 'The speaker expresses frustration in writing the logic for determining the intersection of two rectangles, seeking a simpler way to approach the problem', 'Referencing a previous struggle with the Frogger coding challenge, the speaker mentions the possibility of revisiting their Frogger code or utilizing an existing library for geometry math']}, {'end': 618.798, 'segs': [{'end': 419.319, 'src': 'embed', 'start': 387.859, 'weight': 0, 'content': [{'end': 407.071, 'text': 'Otherwise. now, if they do intersect, let me look through all the points that are part of this quadtree and say if range.contains found.push.', 'start': 387.859, 'duration': 19.212}, {'end': 412.494, 'text': 'So now I know that the boundary and the range that this quadtree intersects, that range.', 'start': 407.071, 'duration': 5.423}, {'end': 416.376, 'text': "So let me check all of its points and see if they're within the range.", 'start': 412.514, 'duration': 3.862}, {'end': 417.257, 'text': 'Then I can add them.', 'start': 416.456, 'duration': 0.801}, {'end': 419.319, 'text': "Perfect, I've added them.", 'start': 418.237, 'duration': 1.082}], 'summary': 'Using quadtree to check and add points within intersecting range.', 'duration': 31.46, 'max_score': 387.859, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY387859.jpg'}, {'end': 520.88, 'src': 'embed', 'start': 492.329, 'weight': 1, 'content': [{'end': 498.576, 'text': 'and then I can say northeast, southwest, southeast.', 'start': 492.329, 'duration': 6.247}, {'end': 504.563, 'text': 'What this is going to do, and then I can return found here.', 'start': 499.177, 'duration': 5.386}, {'end': 510.089, 'text': "So what I can do is, all right, I'm going to start with an empty array.", 'start': 505.684, 'duration': 4.405}, {'end': 517.856, 'text': 'If it does intersect, just return an empty array, and all this concat stuff is going to concatenate.', 'start': 511.829, 'duration': 6.027}, {'end': 520.88, 'text': 'Concatenate should just join two arrays together.', 'start': 518.076, 'duration': 2.804}], 'summary': 'Concatenation of arrays based on intersection, returning an empty array if none found.', 'duration': 28.551, 'max_score': 492.329, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY492329.jpg'}, {'end': 582.245, 'src': 'embed', 'start': 549.909, 'weight': 2, 'content': [{'end': 552.41, 'text': "and get rid of all these extra line breaks that I don't need anymore.", 'start': 549.909, 'duration': 2.501}, {'end': 556.453, 'text': 'And now here I should have.', 'start': 553.471, 'duration': 2.982}, {'end': 564.917, 'text': 'okay, so I have this rectangle, but this is actually, I need to say a range is, and I really should make this.', 'start': 556.453, 'duration': 8.464}, {'end': 570.3, 'text': 'let range be a new rectangle, that is, 250, 250, 107, 75..', 'start': 564.917, 'duration': 5.383}, {'end': 581.585, 'text': "And I'm going to divide those by Whatever, that's fine.", 'start': 570.3, 'duration': 11.285}, {'end': 582.245, 'text': "I'll make it bigger.", 'start': 581.605, 'duration': 0.64}], 'summary': 'Creating a new rectangle with dimensions 107x75 and adjusting its size.', 'duration': 32.336, 'max_score': 549.909, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY549909.jpg'}], 'start': 359.763, 'title': 'Quadtree and recursion', 'summary': 'Covers quadtree intersection, recursion in northwest query range, and drawing/querying rectangles, discussing processes for adding points within a range, concatenating arrays, and querying points within specified dimensions.', 'chapters': [{'end': 453.193, 'start': 359.763, 'title': 'Quadtree intersection', 'summary': "Discusses the process of recursively searching through a quadtree to find and add points within a specified range, handling cases where the quadtree intersects or doesn't intersect, and checking for points within a range before adding them.", 'duration': 93.43, 'highlights': ['The chapter discusses the process of recursively searching through a quadtree to find and add points within a specified range.', "Handling cases where the quadtree intersects or doesn't intersect.", 'Checking for points within a range before adding them.']}, {'end': 547.692, 'start': 453.513, 'title': 'Recursion in northwest query range', 'summary': 'Discusses the use of recursion to find the northwest query range by concatenating arrays and checking for intersecting points, aiming to return the final array of points.', 'duration': 94.179, 'highlights': ['The process involves concatenating arrays of points from different directions, such as northwest, northeast, southwest, and southeast, to form the final array.', 'The speaker mentions the use of recursion and the technique of adding points from children if the area has been divided, contributing to the understanding of the method.', 'The concept of returning an empty array if there is no intersection, and the importance of checking for the existence of points before proceeding, are highlighted in the discussion.']}, {'end': 618.798, 'start': 549.909, 'title': 'Drawing and querying rectangles', 'summary': "Discusses drawing a rectangle and querying points within it, specifying the rectangle's dimensions and then querying the points within it using the 'qtree' and logging the array of points.", 'duration': 68.889, 'highlights': ['Defining a new rectangle with dimensions 250, 250, 107, 75 and then enlarging it by multiplying its width and height by two.', 'Drawing the rectangle at the specified coordinates and dimensions.', "Querying points within the rectangle using 'qtree.query' and logging the array of points."]}], 'duration': 259.035, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY359763.jpg', 'highlights': ['The chapter discusses the process of recursively searching through a quadtree to find and add points within a specified range.', 'The process involves concatenating arrays of points from different directions, such as northwest, northeast, southwest, and southeast, to form the final array.', 'Defining a new rectangle with dimensions 250, 250, 107, 75 and then enlarging it by multiplying its width and height by two.']}, {'end': 882.412, 'segs': [{'end': 669.449, 'src': 'embed', 'start': 642.442, 'weight': 1, 'content': [{'end': 645.805, 'text': 'The method does not change the existing array, but instead returns a new array.', 'start': 642.442, 'duration': 3.363}, {'end': 647.687, 'text': 'This is from Pierre in the chat.', 'start': 645.845, 'duration': 1.842}, {'end': 659.584, 'text': "So what the issue there is, and maybe now I kind of don't want to use this concat, because I have to write this, right? I have to say fat.", 'start': 648.908, 'duration': 10.676}, {'end': 661.685, 'text': 'I think passing the array is going to be better.', 'start': 659.824, 'duration': 1.861}, {'end': 663.266, 'text': 'So apologies.', 'start': 662.345, 'duration': 0.921}, {'end': 666.567, 'text': "I'm going to say return.", 'start': 663.286, 'duration': 3.281}, {'end': 669.449, 'text': 'I kind of like passing the array better.', 'start': 666.587, 'duration': 2.862}], 'summary': 'Pierre prefers passing the array for better performance.', 'duration': 27.007, 'max_score': 642.442, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY642442.jpg'}, {'end': 829.437, 'src': 'heatmap', 'start': 738.186, 'weight': 0, 'content': [{'end': 740.948, 'text': 'But let me just, to get this work, let me pass in.', 'start': 738.186, 'duration': 2.762}, {'end': 755.823, 'text': "I'm going to think about how to return it better in a second, but let me create an empty array and then pass it in,", 'start': 744.955, 'duration': 10.868}, {'end': 756.964, 'text': 'and then we will look at that array.', 'start': 755.823, 'duration': 1.141}, {'end': 760.927, 'text': 'So, okay.', 'start': 759.706, 'duration': 1.221}, {'end': 767.151, 'text': 'This just gets me out of here, et cetera, et cetera, et cetera.', 'start': 763.589, 'duration': 3.562}, {'end': 769.293, 'text': 'Okay, okay, here we go.', 'start': 767.311, 'duration': 1.982}, {'end': 772.18, 'text': 'All right, 160.', 'start': 770.72, 'duration': 1.46}, {'end': 773.481, 'text': 'That makes a little bit more sense.', 'start': 772.18, 'duration': 1.301}, {'end': 775.561, 'text': 'There could be 160 points in there.', 'start': 774.001, 'duration': 1.56}, {'end': 795.086, 'text': 'So let me now, in the sketch, let me say for let p of points and then stroke 0, 255, 0.', 'start': 776.622, 'duration': 18.464}, {'end': 796.148, 'text': 'I guess I already have that.', 'start': 795.087, 'duration': 1.061}, {'end': 797.468, 'text': 'Let me draw the points.', 'start': 796.208, 'duration': 1.26}, {'end': 805.316, 'text': 'And let me say point p.x, p.y.', 'start': 801.594, 'duration': 3.722}, {'end': 806.977, 'text': "So let's look and see if that worked.", 'start': 805.696, 'duration': 1.281}, {'end': 809.678, 'text': 'Hey, this is looking pretty good.', 'start': 807.317, 'duration': 2.361}, {'end': 812.68, 'text': 'Pretty, pretty, pretty good.', 'start': 809.759, 'duration': 2.921}, {'end': 815.562, 'text': "All right, let's make this rectangular range random.", 'start': 812.94, 'duration': 2.622}, {'end': 829.437, 'text': "So let's pick a random point, a random height, and let's give it some random width within 100.", 'start': 816.762, 'duration': 12.675}], 'summary': 'Creating an empty array and drawing points with random dimensions within 100.', 'duration': 77.376, 'max_score': 738.186, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY738186.jpg'}], 'start': 619.338, 'title': 'Array manipulation and debugging', 'summary': 'Discusses using the concat method for array merging and debugging array manipulation code, highlighting the shift towards using the concat method and successful implementation of randomization with 160 points.', 'chapters': [{'end': 669.449, 'start': 619.338, 'title': 'Using the concat method for array merging', 'summary': 'Discusses the use of the concat method to merge arrays, where it was initially attempted to merge arrays using a function which only returned three points, prompting a realization of the mistake and a shift towards using the concat method, which does not change the existing array but returns a new one.', 'duration': 50.111, 'highlights': ['The concat method is used to merge two or more arrays, not changing the existing array but instead returning a new one, as mentioned by Pierre in the chat.', 'Initial attempt to merge arrays using a function only returned three points, indicating a mistake in the approach.', 'Realization that using the concat method would be better, leading to a shift in approach towards passing the array and utilizing the concat method.']}, {'end': 882.412, 'start': 671.69, 'title': 'Javascript array manipulation and debugging', 'summary': 'Discusses debugging an array manipulation code, with a focus on identifying errors and implementing randomization, highlighting the need to fix a significant error that has been overlooked and the successful implementation of a random rectangular range with 160 points.', 'duration': 210.722, 'highlights': ["The significant error in the code involving mixed-up variables 'range.x', 'this.w', 'range.w', 'range.h' needs to be fixed, identified after spending an hour staring at the function.", 'The successful implementation of a random rectangular range with 160 points, demonstrating the functionality and effectiveness of the array manipulation code.', 'Debugging process involving the identification of errors and the need to fix the code to display all points correctly on the sketch, showcasing the challenges and learning experiences in debugging JavaScript array manipulation.']}], 'duration': 263.074, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY619338.jpg', 'highlights': ['Successful implementation of randomization with 160 points showcases the effectiveness of array manipulation code.', 'Realization that using the concat method would be better led to a shift in approach towards passing the array and utilizing the concat method.', 'Debugging process involved the identification of errors and the need to fix the code to display all points correctly on the sketch.']}, {'end': 1228.942, 'segs': [{'end': 985.478, 'src': 'embed', 'start': 952.434, 'weight': 0, 'content': [{'end': 953.654, 'text': '31, 27, 48, 219.', 'start': 952.434, 'duration': 1.22}, {'end': 966.085, 'text': "Now of course, I've got to look at a lot with this big range because I kind of got picked randomly through the center.", 'start': 953.655, 'duration': 12.43}, {'end': 968.867, 'text': 'But I never have to look through all the points.', 'start': 966.465, 'duration': 2.402}, {'end': 976.633, 'text': 'And so this algorithm, if I make the range the whole canvas, well then I have to look through all the points.', 'start': 969.988, 'duration': 6.645}, {'end': 985.478, 'text': "The point is if my range is something much smaller like, even if it's like 25 by 25, right?", 'start': 976.933, 'duration': 8.545}], 'summary': 'Algorithm selects points within a smaller range to reduce workload.', 'duration': 33.044, 'max_score': 952.434, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY952434.jpg'}, {'end': 1061.332, 'src': 'embed', 'start': 1028.194, 'weight': 1, 'content': [{'end': 1028.974, 'text': 'Quadtree line 87, save.', 'start': 1028.194, 'duration': 0.78}, {'end': 1039.626, 'text': 'So now you can see, as I move the rectangle, it is highlighting only the points that it finds.', 'start': 1033.584, 'duration': 6.042}, {'end': 1041.386, 'text': 'I kind of want the count back.', 'start': 1040.026, 'duration': 1.36}, {'end': 1045.387, 'text': 'Because I kind of want to know how many checks.', 'start': 1041.406, 'duration': 3.981}, {'end': 1046.228, 'text': 'But this is great.', 'start': 1045.428, 'duration': 0.8}, {'end': 1048.649, 'text': 'All right.', 'start': 1048.288, 'duration': 0.361}, {'end': 1061.332, 'text': "Woo-hoo! I think I've successfully now implemented the full quadtree, because I have both an insert function and a query function.", 'start': 1049.129, 'duration': 12.203}], 'summary': 'Implemented full quadtree with insert and query functions successfully.', 'duration': 33.138, 'max_score': 1028.194, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY1028194.jpg'}, {'end': 1170.161, 'src': 'heatmap', 'start': 1142.049, 'weight': 0.793, 'content': [{'end': 1148.39, 'text': 'And then can I just say return found down here? Is that going to work? That works.', 'start': 1142.049, 'duration': 6.341}, {'end': 1150.431, 'text': "I don't know why I thought it was so complicated.", 'start': 1148.41, 'duration': 2.021}, {'end': 1159.638, 'text': "The reason why I kind of was afraid to do that is that these are also returning the reference to the array, but it doesn't matter,", 'start': 1152.256, 'duration': 7.382}, {'end': 1160.859, 'text': "because I'm not doing anything with it.", 'start': 1159.638, 'duration': 1.221}, {'end': 1161.679, 'text': "So that's fine.", 'start': 1161.059, 'duration': 0.62}, {'end': 1170.161, 'text': 'So the only return that really counts is the very, very, very last one, which is the original call to the query function.', 'start': 1161.939, 'duration': 8.222}], 'summary': 'The only return that counts is the original call to the query function.', 'duration': 28.112, 'max_score': 1142.049, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY1142049.jpg'}, {'end': 1192.308, 'src': 'embed', 'start': 1161.059, 'weight': 2, 'content': [{'end': 1161.679, 'text': "So that's fine.", 'start': 1161.059, 'duration': 0.62}, {'end': 1170.161, 'text': 'So the only return that really counts is the very, very, very last one, which is the original call to the query function.', 'start': 1161.939, 'duration': 8.222}, {'end': 1174.023, 'text': 'So now, OK, that was much easier than I thought.', 'start': 1171.702, 'duration': 2.321}, {'end': 1176.363, 'text': 'So now at least I have the function return that array.', 'start': 1174.063, 'duration': 2.3}, {'end': 1178.764, 'text': "OK, I'm going to be done.", 'start': 1176.783, 'duration': 1.981}, {'end': 1181.385, 'text': "There's one more video I need to make.", 'start': 1179.504, 'duration': 1.881}, {'end': 1186.806, 'text': "And I think, though, there's many more videos I need to make.", 'start': 1182.125, 'duration': 4.681}, {'end': 1189.127, 'text': "But part three, it's going to come later.", 'start': 1187.127, 'duration': 2}, {'end': 1192.308, 'text': 'Hopefully, by the time you watch this, it might actually be linked to.', 'start': 1189.147, 'duration': 3.161}], 'summary': 'The speaker is working on a query function and plans to make more videos.', 'duration': 31.249, 'max_score': 1161.059, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY1161059.jpg'}, {'end': 1227.621, 'src': 'heatmap', 'start': 1225.48, 'weight': 1, 'content': [{'end': 1227.621, 'text': "And that's what's going to happen.", 'start': 1225.48, 'duration': 2.141}], 'summary': 'Unclear content, no specific information provided.', 'duration': 2.141, 'max_score': 1225.48, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY1225480.jpg'}], 'start': 882.492, 'title': 'Optimizing point search and quadtree implementation', 'summary': 'Covers optimizing a point search algorithm, reducing points from 300 to a subset of 25 by 25, and implementing a quadtree with insert and query functions, aligning with wikipedia pseudocode and addressing collision detection for a java version.', 'chapters': [{'end': 985.478, 'start': 882.492, 'title': 'Optimizing point search algorithm', 'summary': 'Explains the process of optimizing a point search algorithm to reduce the number of points to be checked, resulting in a reduction from 300 points to a subset, with a potential range of 25 by 25.', 'duration': 102.986, 'highlights': ['The algorithm was optimized to reduce the number of points to be checked from 300 to a subset, potentially as small as 25 by 25.', 'A global variable called count was used to track the number of points within a specific range, with a successful reduction to a subset of points.', "The speaker employed a 'hack check' method to increment the count, resulting in a reduction from 300 points to a subset without the need to look through all the points."]}, {'end': 1103.797, 'start': 985.918, 'title': 'Quadtree implementation and comparison', 'summary': 'Demonstrates the successful implementation of a quadtree with an insert function and a query function, highlighting the elimination of unnecessary checks and the alignment with the wikipedia pseudocode.', 'duration': 117.879, 'highlights': ['The successful implementation of both an insert function and a query function for the quadtree, indicating a comprehensive and functional quadtree implementation.', 'The elimination of unnecessary checks, leading to increased efficiency and optimization in the quadtree implementation.', 'The alignment of the implemented quadtree with the pseudocode from the Wikipedia page, showcasing the accuracy and adherence to established concepts and standards.']}, {'end': 1228.942, 'start': 1103.797, 'title': 'Implementing quad tree algorithm', 'summary': 'Discusses the process of modifying a function to return an array, while also mentioning plans to apply the quad tree algorithm to a collision detection problem and porting it to processing for a java version.', 'duration': 125.145, 'highlights': ['The chapter focuses on modifying a function to return an array and discussing the simplicity of the process, emphasizing the importance of the final return statement.', 'Plans to apply the quad tree algorithm to a collision detection problem and port it to Processing for a Java version are mentioned, with a call to action for viewers to challenge themselves with the same problem.', 'The speaker expresses a desire to create more videos, particularly focusing on implementing the quad tree algorithm for a collision detection problem and porting it to Processing for a Java version.']}], 'duration': 346.45, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/QQx_NmCIuCY/pics/QQx_NmCIuCY882492.jpg', 'highlights': ['The algorithm was optimized to reduce the number of points to be checked from 300 to a subset, potentially as small as 25 by 25.', 'The successful implementation of both an insert function and a query function for the quadtree, indicating a comprehensive and functional quadtree implementation.', 'The chapter focuses on modifying a function to return an array and discussing the simplicity of the process, emphasizing the importance of the final return statement.']}], 'highlights': ['The quad tree allows for the efficient retrieval of points within a given boundary, improving upon the process of manually checking containment for every point.', 'Implementing a new function called query in the quadtree data structure to efficiently retrieve points within a specified range', 'The algorithm was optimized to reduce the number of points to be checked from 300 to a subset, potentially as small as 25 by 25.', 'The chapter discusses the process of recursively searching through a quadtree to find and add points within a specified range.', 'Successful implementation of randomization with 160 points showcases the effectiveness of array manipulation code.']}