Coding Challenge #148: Gift Wrapping Algorithm (Convex Hull)
3,557In 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