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

References:

Videos:

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

#algorithm #computationalgeometry #convexhull #p5js #javascript

[hashbrown]

The vibe itself pulled me towards your video. And the teaching, as always, next level.

[andrejilic]

Dude, your videos are too great for youtube.

[aaditya]

The way you interact, the way u express ur intrest in coding, your logical thinking inspires me

[singhashutoshk]

Man you are amazing and the way you teach coding makes you wonder is it actually this simple and fun...I learnt a lot from you especially learning p5js was a big tool under my belt ...really thanks...keep doing the good work

[matthewharrilal]

This guy gives me motivation to be calm during problems

[jimbarchuk]

I'm glad you mentioned inefficiency. But brute force is fine for first pass demo. I once wrote a dialup BBS router the task of which was to pass messages through several steps of 'free/local' calls, to connect systems that were normally 'long distance.' Imagine the array of dots, a message can enter the system at any edge point, and traverse the array of dots to any other point. The intent was to do that with the fewest number of calls. There was an array of fixed data, that needed human maintenance, that said which phone numbers were local to which others. Tons of fun to write.

[russellg]

I have an idea for a computational geometry challenge: a 2D concave hull algorithm - surely this is more useful day-to-day anyway? You want to pass through all the boundary points and generate a shape with the minimum area.

[coopercowley]

Always love seeing a new coding train video in my inbox!! Great video, found it really interesting!

[Amakratacjan]

I began watching the vid and when I realised what it's about, I did it myself in python and went along with watching you solve it. It's awesome how differently we achieved the same result. Big fan of your channel

[chaheeDo]

the enthusiasm tho wow I want to be this excited about coding too

[matebiro]

Just had a class on geometric algorithms last semester, but needless to say, your presentation is way more exciting and clear.

[vincentcleaver]

I have a suggestion; sort the points around a central point by lowest to highest angle, build a starburst polygon, then check each vertex for the angle between the adjacent points, removing vertices with angles greater than pi/180 degrees. Loop through the vertices until there are no concavities

[Mr.Adhesive]

Haha this is pretty halarious! I am doing research and we need to extract contours of important areas in an image, and I have been looking for something like this! Literally just started looking yesterday! How serendipitous!

[williamhewlett]

Cross product rule for (a x b):
1. Put your right hand perpendicular to the plane of the board.
2. Let vector a "go through" the palm of your hand and your thumb stick out perpendicular to the plane of the board
3. Visually inspect to see if the angle between vector a and vector b is less than 180 degrees
3a. If it is, curl your fingers over to vector b, proceed to step 4
3b. If is is not, rotate your forearm 180 degrees about its long axis, then return to step 3a
4. Your thumb is the direction of the resultant vector

[shadowyxpgames]

Ironic, I was assigned to write jarvis' march in my algorithm's class, and i am looking up information algorithm and you just released a video! Thank you so much for doing it, I had a great understanding after i watched the video, and I had the confidence to write it up for my class afterwards. Cheers!

[lubio]

looking forward to the computational geometry series...i stumbled across delauney triangulation on gamedev once

[kaizen]

Fantastic topic! Never knew this existed.

[zackhartmann]

new coding challenge? let me stop whatever i was doing

[RocketSpecialist]

Bro this video is highly underrated! Thank you!!

[riccardoorlando]

Well, the coolest thing about the DeLaunay triangulation is not the circle thing, it's that it is optimal in avoiding thin long triangles which look ugly. In this sense, it is mathematically the most beautiful triangulation of a given set of points.