title
Coding Challenge #148: Gift Wrapping Algorithm (Convex Hull)

description
In this coding challenge, I implement the “Gift Wrapping algorithm” (aka Jarvis march) for calculating a convex hull in JavaScript. This is a foundational topic in computational geometry! Code: https://thecodingtrain.com/challenges/148-gift-wrapping 🕹️ p5.js Web Editor Sketch: https://editor.p5js.org/codingtrain/sketches/IVE9CxBOF 🎥 Previous video: https://youtu.be/l0HoJHc-63Q?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 Next video: https://youtu.be/GTWrWM1UsnA?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH References: 🌐 Gift Wrapping Algorithm: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm 🌐 Cross Product: https://en.wikipedia.org/wiki/Cross_product 📝 The splice() Array Function: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice Videos: 🎥 ES6 Arrow Syntax: https://www.youtube.com/watch?v=mrYMzpbFz18 🔴 Coding Train Live 180: https://youtu.be/rnJgb-mYPEI?t=8107s Timestamps: 00:00 Introduction 00:47 What is a Convex Hull? 02:36 The Gift Wrapping Algorithm 03:50 Animated Example of the Algorithm 04:58 Time Complexity of this Algorithm 05:30 Code! Drawing Random Points 05:42 Find the Leftmost Point 07:05 Set up Variables for the Animation 09:03 Make a Guess about the Next Point 10:58 Find out which Vector is “to the Left” 15:00 Add Spacing around the Points 15:33 Add an Exit Condition 15:54 Add the Next Vertex to the Hull 16:26 Draw the Hull 17:12 Continue the Algorithm with the Vertices 18:33 Check when the Algorithm is Done 19:08 Mutating the Array is not necessary 19:50 Watching the Algorithm with More Points 20:13 Inefficiencies about this Algorithm 20:29 Closing the Shape 20:54 (Gift) Wrapping up this Coding Challenge 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://thecodingtrain.com/discord 💖 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 #algorithm #computationalgeometry #convexhull #p5js #javascript

detail
{'title': 'Coding Challenge #148: Gift Wrapping Algorithm (Convex Hull)', 'heatmap': [{'end': 337.677, 'start': 322.068, 'weight': 0.717}, {'end': 418.075, 'start': 377.422, 'weight': 0.821}, {'end': 676.957, 'start': 660.502, 'weight': 0.736}, {'end': 877.943, 'start': 863.754, 'weight': 0.756}, {'end': 1129.757, 'start': 1103.298, 'weight': 1}], 'summary': "Explores the concepts of convex hull and gift wrapping algorithm, delving into computational geometry topics, discussing the jarvis march algorithm's time complexity, and demonstrating the implementation of sorting points algorithm in javascript with visual animations.", 'chapters': [{'end': 151.902, 'segs': [{'end': 81.942, 'src': 'embed', 'start': 42.154, 'weight': 1, 'content': [{'end': 46.776, 'text': "The gift wrapping algorithm is probably the least efficient, but it's a good starter one.", 'start': 42.154, 'duration': 4.622}, {'end': 54.2, 'text': "So let me talk about what a convex hull is first, and then look at what the algorithm is, and then we'll go and write the code for it.", 'start': 47.096, 'duration': 7.104}, {'end': 59.964, 'text': 'And this, I should say, is an algorithm part of the field of research called computational geometry.', 'start': 54.58, 'duration': 5.384}, {'end': 66.29, 'text': 'And I would really like to do a variety of coding challenges around different computational geometry topics.', 'start': 60.044, 'duration': 6.246}, {'end': 69.132, 'text': 'So if you have an idea for one, write it in the comments.', 'start': 66.33, 'duration': 2.802}, {'end': 75.257, 'text': 'So the idea of a convex hull is, first, we need just a random collection of points.', 'start': 69.492, 'duration': 5.765}, {'end': 81.942, 'text': 'So if we have a two-dimensional space, and these algorithms typically generalize to higher dimensions, but you know me.', 'start': 75.617, 'duration': 6.325}], 'summary': 'Introduction to the inefficient gift wrapping algorithm and the concept of convex hull in computational geometry.', 'duration': 39.788, 'max_score': 42.154, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI42154.jpg'}, {'end': 129.801, 'src': 'embed', 'start': 104.4, 'weight': 0, 'content': [{'end': 110.564, 'text': "So a convex shape, I always get this confused, but now that I know the term convex hull, I won't forget it again.", 'start': 104.4, 'duration': 6.164}, {'end': 118.171, 'text': 'If I wanted to turn this into a convex shape, I would eliminate this point and connect these two points.', 'start': 111.505, 'duration': 6.666}, {'end': 121.875, 'text': 'And now I have a convex shape.', 'start': 118.592, 'duration': 3.283}, {'end': 129.801, 'text': 'And a convex hull is a polygon that you construct that is convex and contains all of the points.', 'start': 121.975, 'duration': 7.826}], 'summary': 'A convex hull is a polygon that is convex and contains all points.', 'duration': 25.401, 'max_score': 104.4, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI104400.jpg'}], 'start': 0.729, 'title': 'Gift wrapping algorithm', 'summary': 'Introduces the concept of convex hull, explains the gift wrapping algorithm, and discusses other algorithms for computing a convex hull, with a focus on computational geometry topics.', 'chapters': [{'end': 151.902, 'start': 0.729, 'title': 'Coding challenge: gift wrapping algorithm', 'summary': 'Introduces the concept of a convex hull, explains the gift wrapping algorithm, and discusses other algorithms for computing a convex hull, with a focus on computational geometry topics.', 'duration': 151.173, 'highlights': ['The concept of a convex hull is introduced, distinguishing between convex and concave shapes, and explaining how a convex hull is a polygon that is convex and contains all of the points. The chapter explains the concept of a convex hull, distinguishing between convex and concave shapes, and clarifying that a convex hull is a polygon that is convex and contains all of the points.', 'The chapter discusses the gift wrapping algorithm and its efficiency compared to other algorithms for computing a convex hull, emphasizing its status as a good starter algorithm in computational geometry. The chapter discusses the gift wrapping algorithm, highlighting its status as a good starter algorithm in computational geometry and its relatively lower efficiency compared to other algorithms for computing a convex hull.', "The author expresses interest in exploring various coding challenges related to computational geometry topics and encourages audience participation by inviting suggestions for future challenges. The chapter emphasizes the author's interest in exploring coding challenges related to computational geometry topics and encourages audience participation by inviting suggestions for future challenges."]}], 'duration': 151.173, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI729.jpg', 'highlights': ['The chapter introduces the concept of a convex hull and explains the distinction between convex and concave shapes.', 'The gift wrapping algorithm is discussed as a good starter algorithm in computational geometry.', 'The author expresses interest in exploring coding challenges related to computational geometry topics and encourages audience participation.']}, {'end': 324.73, 'segs': [{'end': 250.534, 'src': 'embed', 'start': 209.725, 'weight': 0, 'content': [{'end': 219.329, 'text': "We can see if I draw a line out to all of the points, if I sort them all along a radial path, the one that's all the way to the left will be this one.", 'start': 209.725, 'duration': 9.604}, {'end': 223.011, 'text': 'And then I just do that over and over and over again until eventually I get over here.', 'start': 219.409, 'duration': 3.602}, {'end': 226.072, 'text': 'And I find that the one furthest to the left is the one that I started with.', 'start': 223.311, 'duration': 2.761}, {'end': 229.394, 'text': "And that's going to be my convex hull.", 'start': 226.492, 'duration': 2.902}, {'end': 235.861, 'text': 'Coming back over to the computer on the Wikipedia page, we can see a nice animation of this playing out.', 'start': 230.094, 'duration': 5.767}, {'end': 244.17, 'text': 'And this, by the way, is one of the reasons why I like to write the code for these algorithms without a library.', 'start': 236.201, 'duration': 7.969}, {'end': 245.851, 'text': 'if what.', 'start': 245.531, 'duration': 0.32}, {'end': 250.534, 'text': "I'm working on a larger project and I need to compute a convex hull for some reason.", 'start': 245.851, 'duration': 4.683}], 'summary': 'An algorithm to find convex hull using radial sort method.', 'duration': 40.809, 'max_score': 209.725, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI209725.jpg'}, {'end': 328.623, 'src': 'embed', 'start': 304.359, 'weight': 1, 'content': [{'end': 312.323, 'text': 'Jarvis And the time complexity is O-N-H, N being the number of points and H being the number of points around the convex hull.', 'start': 304.359, 'duration': 7.964}, {'end': 318.727, 'text': "And the reason it's that is because for every point around the convex hull, I have to check all the other points.", 'start': 312.603, 'duration': 6.124}, {'end': 322.048, 'text': "So that's the number of points around the hull times all of the points.", 'start': 318.947, 'duration': 3.101}, {'end': 324.73, 'text': "It's a little bit better than O-N squared, but not by much.", 'start': 322.068, 'duration': 2.662}, {'end': 328.623, 'text': 'And again, there are plenty of other more efficient algorithms for doing it.', 'start': 325.391, 'duration': 3.232}], 'summary': 'Time complexity is o(n*h), n: number of points, h: number of points around convex hull. there are more efficient algorithms available.', 'duration': 24.264, 'max_score': 304.359, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI304359.jpg'}], 'start': 152.903, 'title': 'Convex hull algorithm', 'summary': 'Discusses the jarvis march algorithm for computing the convex hull, including the process of selecting exterior points and determining the time complexity, with emphasis on its efficiency in computational geometry.', 'chapters': [{'end': 324.73, 'start': 152.903, 'title': 'Convex hull algorithm', 'summary': 'Discusses the jarvis march algorithm for computing the convex hull, including the process of selecting exterior points and determining the time complexity, with emphasis on its efficiency in computational geometry.', 'duration': 171.827, 'highlights': ['The Jarvis march algorithm for computing the convex hull involves selecting the leftmost point as the starting vertex and iteratively determining the next point based on its position relative to the current point, resulting in a radial path arrangement of points (relevance: 5)', 'The Jarvis march, also known as the 2D case of the convex hull algorithm, invented by R.A. Jarvis, has a time complexity of O(N*H), where N is the number of points and H is the number of points around the convex hull, offering a more efficient solution than O(N squared) for computational geometry (relevance: 4)', 'Writing algorithms without a library for computing the convex hull can be beneficial for creating interactive explanations or animations for educational or artistic purposes, as most libraries compute all points at once and may not support such visualizations (relevance: 3)']}], 'duration': 171.827, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI152903.jpg', 'highlights': ['The Jarvis march algorithm for computing the convex hull involves selecting the leftmost point as the starting vertex and iteratively determining the next point based on its position relative to the current point, resulting in a radial path arrangement of points (relevance: 5)', 'The Jarvis march, also known as the 2D case of the convex hull algorithm, invented by R.A. Jarvis, has a time complexity of O(N*H), where N is the number of points and H is the number of points around the convex hull, offering a more efficient solution than O(N squared) for computational geometry (relevance: 4)', 'Writing algorithms without a library for computing the convex hull can be beneficial for creating interactive explanations or animations for educational or artistic purposes, as most libraries compute all points at once and may not support such visualizations (relevance: 3)']}, {'end': 669.49, 'segs': [{'end': 356.95, 'src': 'embed', 'start': 325.391, 'weight': 0, 'content': [{'end': 328.623, 'text': 'And again, there are plenty of other more efficient algorithms for doing it.', 'start': 325.391, 'duration': 3.232}, {'end': 330.049, 'text': "This is just the one that I'm starting with.", 'start': 328.824, 'duration': 1.225}, {'end': 331.934, 'text': "All right, let's write some code.", 'start': 330.913, 'duration': 1.021}, {'end': 333.795, 'text': "So I'm just starting with some boilerplate code.", 'start': 332.154, 'duration': 1.641}, {'end': 335.236, 'text': "I've got an empty array.", 'start': 334.215, 'duration': 1.021}, {'end': 337.677, 'text': "I'm putting p5 vectors in it.", 'start': 335.536, 'duration': 2.141}, {'end': 339.959, 'text': "I'm using a p5 vector object to store a point.", 'start': 337.777, 'duration': 2.182}, {'end': 342.841, 'text': "And then I'm just drawing all the points on the canvas itself.", 'start': 340.599, 'duration': 2.242}, {'end': 348.584, 'text': "So the first step that I want to do is find, you can see I can run this over, and I'm going to get a random collection of 10 points.", 'start': 343.181, 'duration': 5.403}, {'end': 351.886, 'text': "And eventually I'll do this with a much higher number of points, but let's start with just 10.", 'start': 348.845, 'duration': 3.041}, {'end': 354.348, 'text': 'So the first thing I want to do is find the leftmost point.', 'start': 351.886, 'duration': 2.462}, {'end': 356.95, 'text': 'And an easy way for me to do that would just be to sort the points.', 'start': 354.708, 'duration': 2.242}], 'summary': 'Starting with code to sort and draw 10 p5 vectors.', 'duration': 31.559, 'max_score': 325.391, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI325391.jpg'}, {'end': 442.44, 'src': 'heatmap', 'start': 377.422, 'weight': 3, 'content': [{'end': 379.403, 'text': "I'll say a.x minus b.x.", 'start': 377.422, 'duration': 1.981}, {'end': 389.39, 'text': "So what this is doing is it's returning a positive number any time a is to the right of b and a negative number any time a is to the left of b.", 'start': 379.823, 'duration': 9.567}, {'end': 394.333, 'text': 'And that should make it such that I can create a global variable.', 'start': 389.39, 'duration': 4.943}, {'end': 397.035, 'text': "I'll call it left for the leftmost point.", 'start': 394.614, 'duration': 2.421}, {'end': 399.177, 'text': 'Left equals points.', 'start': 397.916, 'duration': 1.261}, {'end': 416.515, 'text': 'index 0, and now, if I were to say stroke 0, 255, 0, and say point p.x, p.y, I should see that the left.x and left.y.', 'start': 400.805, 'duration': 15.71}, {'end': 418.075, 'text': 'I should see that the left point is green.', 'start': 416.515, 'duration': 1.56}, {'end': 419.076, 'text': 'So there you can see that.', 'start': 418.316, 'duration': 0.76}, {'end': 423.379, 'text': 'And every time I run it, whichever point is most to the left is going to be green.', 'start': 419.096, 'duration': 4.283}, {'end': 429.784, 'text': 'Great Now I need to find the next point on the convex hull.', 'start': 423.619, 'duration': 6.165}, {'end': 431.227, 'text': 'And remember, I want to animate this.', 'start': 429.944, 'duration': 1.283}, {'end': 438.959, 'text': 'So really, if I were to just go back to the Wikipedia page and look at the pseudocode,', 'start': 432.048, 'duration': 6.911}, {'end': 442.44, 'text': "you're going to see everything happens in just a set of nested loops.", 'start': 438.959, 'duration': 3.481}], 'summary': "Algorithm determines points to the left using global variable 'left'; next point on convex hull found using pseudocode from wikipedia.", 'duration': 65.018, 'max_score': 377.422, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI377422.jpg'}, {'end': 507.313, 'src': 'embed', 'start': 478.534, 'weight': 2, 'content': [{'end': 486.598, 'text': "So vertex I'm going to use that term when it's specifically a vertex along the hull and point is the current point that I'm checking to see if it's the next vertex.", 'start': 478.534, 'duration': 8.064}, {'end': 489.239, 'text': 'So maybe I also need next vertex.', 'start': 487.058, 'duration': 2.181}, {'end': 493.403, 'text': 'I think these are what I need.', 'start': 492.102, 'duration': 1.301}, {'end': 498.066, 'text': 'And so leftmost is just going to be this, sorry, is this.', 'start': 493.483, 'duration': 4.583}, {'end': 507.313, 'text': "And that's also the current vertex is going to start as the leftmost.", 'start': 498.967, 'duration': 8.346}], 'summary': "Using 'vertex' and 'point' to check for next vertex, starting from leftmost.", 'duration': 28.779, 'max_score': 478.534, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI478534.jpg'}], 'start': 325.391, 'title': 'Sorting and convex hull algorithms', 'summary': 'Covers the initial implementation of sorting points algorithm in javascript using p5 vectors to find the leftmost point from a collection of 10 points and explains the process of finding the next point on the convex hull using nested loops and visual animations.', 'chapters': [{'end': 379.403, 'start': 325.391, 'title': 'Sorting points algorithm', 'summary': 'Demonstrates the initial implementation of sorting points algorithm in javascript using p5 vectors to find the leftmost point from a collection of 10 points.', 'duration': 54.012, 'highlights': ['The chapter provides an introductory explanation of implementing sorting points algorithm in JavaScript using p5 vectors.', 'It outlines the process of finding the leftmost point from a collection of 10 points by using the JavaScript sort function with a comparison function.']}, {'end': 669.49, 'start': 379.823, 'title': 'Convex hull algorithm', 'summary': 'Explains the process of finding the next point on the convex hull using nested loops and visual animations, including comparisons between points and vertices, to determine the leftmost point.', 'duration': 289.667, 'highlights': ['The process involves finding the next point on the convex hull using visual animations and comparisons between points and vertices to determine the leftmost point. Process of finding next point, visual animations, comparisons between points and vertices, determination of leftmost point.', 'The algorithm uses nested loops to iterate through the points and determine the leftmost point and the next vertex on the convex hull. Usage of nested loops, iteration through points, determination of leftmost point and next vertex.', 'Visual animations are employed to show the comparisons between points and vertices to determine the leftmost point and the next vertex on the convex hull. Use of visual animations, comparisons between points and vertices, determination of leftmost point and next vertex.']}], 'duration': 344.099, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI325391.jpg', 'highlights': ['The chapter provides an introductory explanation of implementing sorting points algorithm in JavaScript using p5 vectors.', 'It outlines the process of finding the leftmost point from a collection of 10 points by using the JavaScript sort function with a comparison function.', 'The algorithm uses nested loops to iterate through the points and determine the leftmost point and the next vertex on the convex hull.', 'Visual animations are employed to show the comparisons between points and vertices to determine the leftmost point and the next vertex on the convex hull.']}, {'end': 906.734, 'segs': [{'end': 712.064, 'src': 'embed', 'start': 669.83, 'weight': 0, 'content': [{'end': 672.913, 'text': "And guess what? There's a really nice way that I can do that.", 'start': 669.83, 'duration': 3.083}, {'end': 676.957, 'text': 'And the way that I can do that is with the cross product.', 'start': 673.273, 'duration': 3.684}, {'end': 686.144, 'text': 'The cross product is a particular vector operation that you can apply on a 2D vector, two vectors that are in the same plane,', 'start': 677.597, 'duration': 8.547}, {'end': 691.869, 'text': 'and it will return to you a vector pointing perpendicularly in the third dimension away.', 'start': 686.144, 'duration': 5.725}, {'end': 699.415, 'text': "And so what's interesting about this is let me show you what I mean, and I can never remember which is which, but it doesn't really matter,", 'start': 692.269, 'duration': 7.146}, {'end': 701.017, 'text': "because we just need to know that it's one or the other.", 'start': 699.415, 'duration': 1.602}, {'end': 712.064, 'text': 'If this is vector a and this is vector b, the cross product of these two vectors will give me a vector pointing out this way.', 'start': 702.842, 'duration': 9.222}], 'summary': 'The cross product yields a perpendicular vector in 3d space.', 'duration': 42.234, 'max_score': 669.83, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI669830.jpg'}, {'end': 761.846, 'src': 'embed', 'start': 734.171, 'weight': 2, 'content': [{'end': 741.175, 'text': 'So I just need to test is z the z value of a cross product b?', 'start': 734.171, 'duration': 7.004}, {'end': 744.037, 'text': 'is it greater than 0 or less than 0??', 'start': 741.175, 'duration': 2.862}, {'end': 750.24, 'text': "If, by the way, they were collinear or along the same path, you'll get 0..", 'start': 744.037, 'duration': 6.203}, {'end': 753.682, 'text': "And we're just going to assume for this case that I'm picking random points.", 'start': 750.24, 'duration': 3.442}, {'end': 754.943, 'text': 'None of them are going to be collinear.', 'start': 753.822, 'duration': 1.121}, {'end': 756.464, 'text': "It'll probably sort of work out anyway.", 'start': 754.963, 'duration': 1.501}, {'end': 761.846, 'text': 'b is to the left of a if z is less than 0.', 'start': 758.525, 'duration': 3.321}], 'summary': 'Testing if z value of cross product a x b is greater or less than 0', 'duration': 27.675, 'max_score': 734.171, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI734171.jpg'}, {'end': 818.911, 'src': 'embed', 'start': 784.568, 'weight': 4, 'content': [{'end': 786.949, 'text': 'what is currently the next vertex to the current vertex.', 'start': 784.568, 'duration': 2.381}, {'end': 789.031, 'text': "That'll be vector A.", 'start': 787.189, 'duration': 1.842}, {'end': 799.336, 'text': "And then B will be pointing from what I'm checking to the current vertex.", 'start': 789.031, 'duration': 10.305}, {'end': 805.921, 'text': 'And then on the cross product, is a.crossb.', 'start': 799.456, 'duration': 6.465}, {'end': 811.025, 'text': "So I can implement the math for the cross product, but it's actually just there in the p5 library for me.", 'start': 806.141, 'duration': 4.884}, {'end': 818.911, 'text': 'And then I just want to say, if cross is greater than 0, then probably something like next vertex.', 'start': 811.425, 'duration': 7.486}], 'summary': 'Implementing cross product math for finding the next vertex.', 'duration': 34.343, 'max_score': 784.568, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI784568.jpg'}, {'end': 877.943, 'src': 'heatmap', 'start': 841.584, 'weight': 5, 'content': [{'end': 844.485, 'text': 'So is that right? Current one is green.', 'start': 841.584, 'duration': 2.901}, {'end': 848.867, 'text': "So if it's less than 0, then that's to the left.", 'start': 844.905, 'duration': 3.962}, {'end': 862.433, 'text': "So if cross.z is less than 0, then next vertex should actually be the one that I'm checking.", 'start': 849.747, 'duration': 12.686}, {'end': 869.718, 'text': 'And then I just want to say index equals index plus 1.', 'start': 863.754, 'duration': 5.964}, {'end': 870.398, 'text': 'There we go.', 'start': 869.718, 'duration': 0.68}, {'end': 875.582, 'text': "So you can see that as it goes through, it's always going to find the correct one.", 'start': 870.438, 'duration': 5.144}, {'end': 876.762, 'text': "It's checking them all.", 'start': 875.642, 'duration': 1.12}, {'end': 877.943, 'text': "Let's make a lot of points.", 'start': 876.822, 'duration': 1.121}], 'summary': 'Algorithm iterates through vertices to find correct ones.', 'duration': 36.359, 'max_score': 841.584, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI841584.jpg'}], 'start': 669.83, 'title': 'Cross product in 2d vectors and its applications', 'summary': 'Introduces the cross product as a vector operation in 2d vectors, discussing its use for determining vector direction and implementing it to find the next vertex, resulting in visually easier to follow iterations.', 'chapters': [{'end': 733.911, 'start': 669.83, 'title': 'Cross product in 2d vectors', 'summary': 'Introduces the concept of the cross product as a vector operation on 2d vectors, yielding a perpendicular vector in the third dimension, with the direction determined by the order of the input vectors.', 'duration': 64.081, 'highlights': ['The cross product is a vector operation on 2D vectors, resulting in a vector perpendicular to the input vectors in the third dimension.', 'The direction of the resulting vector is determined by the order of the input vectors, with a different order yielding a vector pointing in the opposite direction.']}, {'end': 783.391, 'start': 734.171, 'title': 'Cross product test for vector direction', 'summary': 'Discusses the use of the cross product to determine the direction of vectors by testing the z value, with the result being greater than 0 or less than 0 depending on the relative positions of the vectors.', 'duration': 49.22, 'highlights': ['The cross product z value determines the relative position of vectors, with a value greater than 0 indicating one direction and less than 0 indicating the other.', 'The method assumes non-collinear points and addresses the potential issue of collinearity resulting in a value of 0 for the cross product z value.', 'The direction determination is relevant in computer graphics systems and is adjusted accordingly, with the code being developed to implement this functionality.']}, {'end': 906.734, 'start': 784.568, 'title': 'Implementing cross product for finding next vertex', 'summary': 'Discusses implementing the cross product to determine the next vertex in a shape, iterating through vertices and checking the cross product to find the correct one while incrementing the index, resulting in visually easier to follow iterations.', 'duration': 122.166, 'highlights': ['Implementing the cross product to determine the next vertex in a shape, iterating through vertices and checking the cross product to find the correct one while incrementing the index.', "Using the condition 'if cross.z is less than 0' to determine the next vertex, resulting in visually easier to follow iterations.", 'Using the p5 library for the cross product math implementation.']}], 'duration': 236.904, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI669830.jpg', 'highlights': ['The cross product is a vector operation on 2D vectors, resulting in a vector perpendicular to the input vectors in the third dimension.', 'The direction of the resulting vector is determined by the order of the input vectors, with a different order yielding a vector pointing in the opposite direction.', 'The cross product z value determines the relative position of vectors, with a value greater than 0 indicating one direction and less than 0 indicating the other.', 'The method assumes non-collinear points and addresses the potential issue of collinearity resulting in a value of 0 for the cross product z value.', 'Implementing the cross product to determine the next vertex in a shape, iterating through vertices and checking the cross product to find the correct one while incrementing the index.', "Using the condition 'if cross.z is less than 0' to determine the next vertex, resulting in visually easier to follow iterations."]}, {'end': 1336.642, 'segs': [{'end': 940.614, 'src': 'embed', 'start': 906.754, 'weight': 1, 'content': [{'end': 923.037, 'text': "And I'm going to say pick a point between buffer and width minus buffer and the height also between buffer and height minus buffer.", 'start': 906.754, 'duration': 16.283}, {'end': 928.258, 'text': "And let's make that buffer even bigger.", 'start': 926.838, 'duration': 1.42}, {'end': 933.17, 'text': "So now the points won't get picked super close to the edge.", 'start': 930.148, 'duration': 3.022}, {'end': 935.591, 'text': 'So clearly I need an exit condition.', 'start': 933.95, 'duration': 1.641}, {'end': 940.614, 'text': "So I'm going to say if index equals points.length, that means I've gotten to the end of the array.", 'start': 935.771, 'duration': 4.843}], 'summary': 'Algorithm adjusted to prevent points near edges.', 'duration': 33.86, 'max_score': 906.754, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI906754.jpg'}, {'end': 1043.732, 'src': 'embed', 'start': 1014.567, 'weight': 3, 'content': [{'end': 1018.79, 'text': "And I'm not going to say close, but I am going to give it a really light fill.", 'start': 1014.567, 'duration': 4.223}, {'end': 1020.331, 'text': "So I'm going to say fill.", 'start': 1019.19, 'duration': 1.141}, {'end': 1023.433, 'text': "I'll also have it be blue, but with a lot of alpha.", 'start': 1020.851, 'duration': 2.582}, {'end': 1025.733, 'text': 'Then I need to add vertex.', 'start': 1024.032, 'duration': 1.701}, {'end': 1032.239, 'text': "And I don't think I'm going to see the hull yet, because I've only drawn two points so far, and I've stopped the loop from looping.", 'start': 1026.275, 'duration': 5.964}, {'end': 1033.719, 'text': "So let's see what happens.", 'start': 1032.699, 'duration': 1.02}, {'end': 1039.943, 'text': 'What if I just reset index back to zero? and turn off no loop.', 'start': 1033.759, 'duration': 6.184}, {'end': 1043.732, 'text': 'OK It got stuck.', 'start': 1042.008, 'duration': 1.724}], 'summary': 'Experimenting with drawing using a light blue fill with alpha, adding vertices, and encountering issues with loop and index reset.', 'duration': 29.165, 'max_score': 1014.567, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI1014567.jpg'}, {'end': 1129.757, 'src': 'heatmap', 'start': 1103.298, 'weight': 1, 'content': [{'end': 1109.001, 'text': "So what I should do is just reset next vertex to something else, like I'll just put it back to be that leftmost one.", 'start': 1103.298, 'duration': 5.703}, {'end': 1111.09, 'text': 'There we go.', 'start': 1110.41, 'duration': 0.68}, {'end': 1112.751, 'text': "So now you can see it's working.", 'start': 1111.37, 'duration': 1.381}, {'end': 1116.232, 'text': "Now, it's stuck when it gets to the end.", 'start': 1114.592, 'duration': 1.64}, {'end': 1129.757, 'text': "But guess what? The reason why is I know when I'm done, right? I am done if it actually picks next vertex as the same as the leftmost.", 'start': 1116.552, 'duration': 13.205}], 'summary': 'Resetting vertex resolved issue; reached end but picked same vertex as leftmost.', 'duration': 26.459, 'max_score': 1103.298, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI1103298.jpg'}, {'end': 1221.626, 'src': 'embed', 'start': 1166.938, 'weight': 0, 'content': [{'end': 1171.579, 'text': "But actually, it turns out, and I've just discovered this through some debugging, that I don't even need to delete it.", 'start': 1166.938, 'duration': 4.641}, {'end': 1178.062, 'text': 'The problem was really the fact that next vertex was not reset back to the leftmost.', 'start': 1171.8, 'duration': 6.262}, {'end': 1184.684, 'text': "So it's actually going to work just fine every single time, without splicing that out,", 'start': 1178.262, 'duration': 6.422}, {'end': 1189.906, 'text': 'as long as I reset the next vertex back to leftmost so that it sort of skips getting stuck.', 'start': 1184.684, 'duration': 5.222}, {'end': 1196.255, 'text': "So let's just make sure this, let's watch this happen now with like 200 points, and I will speed this up for you.", 'start': 1191.027, 'duration': 5.228}, {'end': 1210.22, 'text': "OK, we can see that it's done and it looks correct.", 'start': 1207.518, 'duration': 2.702}, {'end': 1213.041, 'text': "I'm pretty sure I did this correctly because it seems to be working.", 'start': 1210.52, 'duration': 2.521}, {'end': 1221.626, 'text': "Of course, this is less efficient because I'm checking extra points that I don't need to check because they're already part of the convex whole array.", 'start': 1213.301, 'duration': 8.325}], 'summary': 'Resetting next vertex to leftmost resolves the issue, making it work fine every time with 200 points.', 'duration': 54.688, 'max_score': 1166.938, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI1166938.jpg'}], 'start': 906.754, 'title': 'Drawing and optimizing convex hull algorithm', 'summary': 'Covers drawing hull points in processing with buffer implementation and convex hull optimization utilizing splicing, resetting vertex positions, and identifying computational efficiency for potential future developments in computational geometry coding challenges.', 'chapters': [{'end': 1033.719, 'start': 906.754, 'title': 'Drawing hull points in processing', 'summary': 'Explains how to draw hull points in processing by using a buffer to avoid points near the edge, implementing an exit condition, and drawing the hull with a blue stroke and light fill.', 'duration': 126.965, 'highlights': ['The author discusses using a buffer to prevent points from being picked too close to the edge, enhancing the visualization of the hull points.', "An exit condition is implemented to stop the animation when the end of the array is reached, improving the program's efficiency.", 'Drawing the hull with a blue stroke and light fill is demonstrated, adding visual representation to the hull points.']}, {'end': 1336.642, 'start': 1033.759, 'title': 'Optimizing convex hull algorithm', 'summary': 'Demonstrates the process of optimizing the convex hull algorithm, utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency, leading to potential future developments in computational geometry coding challenges.', 'duration': 302.883, 'highlights': ['The chapter demonstrates the process of optimizing the convex hull algorithm The speaker discusses the process of optimizing the convex hull algorithm by utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency.', 'Utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency The speaker explains the utilization of concepts such as splicing to remove vertices, resetting vertex positions, and identifying computational efficiency for improving the algorithm.', 'Potential future developments in computational geometry coding challenges The chapter concludes by discussing potential future developments in computational geometry, including the creation of a triangulation around all the points and exploring the possibilities of tying the algorithm to sound or other interactive elements.']}], 'duration': 429.888, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YNyULRrydVI/pics/YNyULRrydVI906754.jpg', 'highlights': ['The chapter demonstrates the process of optimizing the convex hull algorithm by utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency.', "An exit condition is implemented to stop the animation when the end of the array is reached, improving the program's efficiency.", 'Utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency for improving the algorithm.', 'Drawing the hull with a blue stroke and light fill is demonstrated, adding visual representation to the hull points.']}], 'highlights': ['The Jarvis march algorithm for computing the convex hull involves selecting the leftmost point as the starting vertex and iteratively determining the next point based on its position relative to the current point, resulting in a radial path arrangement of points (relevance: 5)', 'The Jarvis march, also known as the 2D case of the convex hull algorithm, invented by R.A. Jarvis, has a time complexity of O(N*H), where N is the number of points and H is the number of points around the convex hull, offering a more efficient solution than O(N squared) for computational geometry (relevance: 4)', 'The chapter introduces the concept of a convex hull and explains the distinction between convex and concave shapes.', 'The gift wrapping algorithm is discussed as a good starter algorithm in computational geometry.', 'The chapter provides an introductory explanation of implementing sorting points algorithm in JavaScript using p5 vectors.', 'The cross product is a vector operation on 2D vectors, resulting in a vector perpendicular to the input vectors in the third dimension.', 'The chapter demonstrates the process of optimizing the convex hull algorithm by utilizing concepts such as splicing, resetting vertex positions, and identifying computational efficiency.']}