Coding Challenge

[@TheCodingTrain]

Find the code and share your version! thecodingtrain.com/CodingChallenges/148-gift-wrapping.html

[@devilnight6610]

Thanks for the gift codes!

[@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

[@ivanpedrero9773]

This is mine: editor.p5js.org/IvanPedrero/full/rID2WvsCB You can create your points by clicking on the screen and then see the algorithm work... Thanks for the video! Really good explanation!

[@FlyingButterHorse]

Just a small correction; You said that the cross product is an operation between two vectors that are on the same plane, which is correct, but redundant. Given any two vectors, there exists a plan that contains them. In fact, they define that plane uniquely, as long as they are not linearly dependant (multiples of one another). Just saying.

[@goranjosic]

With your knowledge of JavaScript, how is it possible that the new site did not keep the old links?! Currently, none of the old links work anymore? :)

[@hashbrown8314]

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

[@leandrodipietro5611]

How about a tutorial on 3D scanning with a pc webcam in p5... point cloud generation... Delaunay triangulation... STL representation?? You are the best. Keep up the good work!

[@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

[@aditya95sriram]

Someone please make a compilation of all of Dan's adorable fumbles including but not limited to "Graham's Scam" 😂

[@donwilson]

I recommended this way back in early 2018 on the topics GitHub, glad to see it done 😊

[@matthewharrilal7626]

This guy gives me motivation to be calm during problems

[@russellg3775]

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.

[@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.

[@andrejilic8106]

Dude, your videos are too great for youtube.

[@kishorenagarajan344]

Explanation is sooo engaging....

[@chaheeDo0]

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

[@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!

[@TheCodingTrain]

awesome, glad to hear!

[@shadowyxpgames5506]

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!

[@afrodisco2655]

I tried to improved slightly the visual and the ease of use of the your code. You can find this there: editor.p5js.org/AfroDisco/sketches/-st9ZFxBS I also tried to use divide and conquer to reduce the complexity: editor.p5js.org/AfroDisco/sketches/nSWqjnOJU The approach is to compute the convex hull of subset of points (split along the X axis) and then computing the convex hull of all points inside these convex hulls. I also added some outputs to show the computational differences between both.

[@TheCodingTrain]

This is so great! Would you mind submitting a link to the coding train website? github.com/CodingTrain/website/wiki/Community-Contributions-Guide

[@riccardoorlando2262]

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.

[@gunnarbernstein2867]

This is a nice explanation of the Gift-Wrapping-Algorithm, but it has one big flaw. By sorting the points first a O(n log(n)) time complexity is added, which makes this algorithm very slow. While it seems this algorithm is slower than the graham scan, in many cases it is acutally a lot faster, because sorting takes a lot of time. The sort should be replaced by a simple for loop to identify the leftmost point. In my tests the Gift-Wrapping-Algorithm was always faster than the Graham Scan at least to about 2500 points, then depending on the number of convex hull points found. One of the reasons may be, that sorting actually requires memory access, while just reading the points can take advantage of processor cache.

[@TheCodingTrain]

Thanks for this very important feedback!

[@godthinkun]

Omg you are the best coding teacher in my life!!

[@awaisahmed7033]

Bro love and respect for you

[@carolinabatista3226]

Would love to see a sketch with the conrec algorithm!

[@TheAknok]

Quite late, but somewhat related to this. Coding Challenge: Divide an arbitrary 2D polygon into triangles. + Polygon can be overlapping. + Inside is defined as uneven number of "linehops" from outside.

[@ezstudio3d]

have you done a Delaunay Triangulation challenge, I'd like to see it?

[@kothawadegs]

It will be great if you can post a tutorial on the Alpha-shape method as well.

[@williamabousharaf9122]

Amazing energy!!!

[@roamingcelt]

You asked for it. I'd like to see you do a Delaunay triangulation video.

[@parthpawar7837]

Coding Challenge Suggestion: Delaunay's Triangulation

[@chrissekely]

Would it be possible to connect all the dots with a non-self-intersecting spiral? Obviously I would not be a true spiral and would likely be quite misshapen but I think you get the idea.

[@konstantinrebrov675]

Dear sir, can you please make some videos about 3D geometric algorithms? Those would be really fun.

[@bertobertoberto242]

But in the first example of the Gram Scan, there is one point outside the convex hull....

[@OdinZockt]

Isnt the definition of convex just, hat you can connect evry 2 points with a straight line and the line will be in your shape completely? and concave being just non-convex

[@miha53cevic]

You could do Triangulations next

[@TheCodingTrain]

Yes, I hope to!

[@anuraghazra4772]

Oh no. did i just missed the live stream of this Coding Challenge?

[@TheCodingTrain]

It was this one! kzbin.info/www/bejne/qJ-tmJVjor6De6s

[@anuraghazra4772]

@@TheCodingTrain oh, thanks!

[@mctuble]

I really hope to see a video on polygon triangulation.

[@DedicatedManagers]

I’d like to see how software like jsplumb creates lines between objects and even smart routes them. Another website that does this is something like draw.io where you connect to boxes together with a line.

[@franksimon8375]

90s wireframe mesh but on fractal location data

[@irispallis]

excellent vid! but why so fast?

[@okoiful]

Please do delaunay triangulation! :)

[@DeathKiller307]

Would you be able to create a convex hull using this algorithm kzbin.info/www/bejne/g2eXeYh_f6uHkK8

[@emanuelmilani7976]

Geometry idea: offset of a polyline

[@PaulGoux]

A continuation from a previous project where I've implemented something similar to this idea when trying to figure out how to make procedural racetracks . You're video happened to remind me of trying to figure this out. Note this is done to a quantized grid as opposed to a random set of points. I shall try to revise my program to handle random points. www.openprocessing.org/sketch/731320 Hit start, wait for load, then hit cluster. it will trace the outline of all the clusters. I used a different algorithm. It assigns maze generators which have different ids, these will map out random shapes, until they have visited all points. if a point has a neighbor with a different id it therefore lies on the outside, otherwise it lies on the inside. Then i use a algorithm which picks a random outer point in a cluster, and checks whether the next point shares one of its neighbors, if it does, then its switches to said point

[@MrSmellyPotato]

Let's find the longest path in a graph

[@TechnicalManhoon]

I thought there is someone else when it came to timeline 8:39 hahahahahahahahahaa

[@aries7395]

it's similar to the Graham Scan

[@lonnybulldozer8426]

Did you study mathematics as an undergraduate? Also, I have a textbook on computational geometry, so I'll get back to you with some suggestions.

[@TheCodingTrain]

I did!

[@lonnybulldozer8426]

@@TheCodingTrain Wow! It shows.

[@Wurstfinger-rl1zi]

Took me 3 Hours to do get the most left point with C++

[@AntonioNoack]

For all interested in a nicely animated version of the probably most efficient of the algorithms, Chan's Algorithm: github.com/AntonioNoack/ChansAlgorithm (written for a seminar at university by me)

[@TheCodingTrain]

Nice work! You can submit a link to the coding train website if you like! github.com/CodingTrain/website/wiki/Community-Contributions-Guide

[@gaborszentirmai407]

Amazing video, but what do you mean by higher dimensions at 1:19 ? Is it 3D or something else?

[@ineedken5400]

prob the 10th dimension lol

[@TheCodingTrain]

Yes, you can have a "convex hull" in 3D which would be the convex surface that holds a collection of points in 3D space. . and so on and so forth!

[@BusyAsBee1738]

so we bout to use a convex hull to ambush area 51?

[@ashishsaud6688]

hey could you make a game using minimax algorithm

[@강관훈]

Maybe this implementation's time complexity is bad because you search every point when you choose new border point..

[@pragueexpat5106]

well he did mention that this algorithm is probably the least efficient

[@Greasyw00t]

You can remember convex vs. concave by thinking conCAVE = CAVE

[@Greasyw00t]

Or maybe more clear, a CAVE is conCAVE

[@Mr8lacklp]

A good mnemonic is: If the girl has sex her belly gets convex

[@juandcg0331]

Pleaseee Spanish Subtitles!!!! 🙏🙏🙏🙏🙏

[@Joshhies]

Graham Scam... :D

[@zackhartmann]

new coding challenge? let me stop whatever i was doing

[@Bunny99s]

That single "sort" call would already have a complexity of O(n log n) (assuming quick sort). Just finding the left most point would only require O(n). There's actually a nice divide and conquer method. First find the extremes in both axis (left most, right most, top most, bottom most). This can be done in O(n) in a single loop through all points. Now we can connect the 4 points to form a quadrilateral. A nice features of those 4 lines is, that all points that are outside that line are only relevant for this line segment. So we can actually filter all points into 5 groups. One for each line segment (all points on the outside of that segment) as well as the points enclosed in that quadrilateral. Those enclosed points don't need to be checked ever again. We splitted the outer points into 4 seperate groups. Next we just iterate through the points for one segment and find the outer most point simply by calculating the dot product between the segments normal vector and the connecting vector from one of the end points to each point in that group. We know that the outer most point is also part of the convex hull. So we can split the original segment into two segments with the new point being the connecting point. Now just repeat for those sub segments. Once there are no points outside all segments, that's the convex hull. The number of points will cut down rapidly this way. Unlike the gift wrapping solution in this video, this approach extends quite nicely into 3d. The min / max points in 3d form an octahedron. So we have 8 triangle faces which form seperation planes. Since it's possible that in the worst case you get 2 initial hull points from the min / max (it's possible that the top and left most point is the same point. Same for the bottom right point), it's usually simpler to assume just a single edge for the start. Same for the 3d case. However we can calculate the point that is furthest from the initial line to form the first cutting plane / triangle in 3d.

[@TheCodingTrain]

Thanks for this explanation!

[@l2ubio]

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

[@alexcook5521]

Any chance you can do a video on a Concave Hull algorithm? I'm a surveyor, and the ability to define the concave hull of a spatial dataset would be an awesome tool for our processing.

[@gelearthur]

This is exactly what I need for my project thank you

[@TheRainHarvester]

Do one of these life simulations next: kzbin.info/www/bejne/f2fFeaOAZ6yJZrs

[@eladaharon9051]

Great video 👍 how about vertex cover coding challenge?

[@eladaharon9051]

I watched the live version 😂

[@aaditya4998]

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

[@HelloMediaArt]

Thank you for always giving a good lecture on a new topic.

[@nikhilgangwar5141]

I think you should do video on minimum spanning tree alg visualisation someday

[@TheCodingTrain]

I did a while back! kzbin.info/www/bejne/eKnEk6GBp7SdipI

[@vincentcleaver1925]

I thought he was trolling, but maybe not. This happens in other channels with hundreds of episodes... 8-)

[@cheshire_cat_311]

0:15 but both demonstrations show some points outside of the convex hull. Is it not a complete implementation or does it have some bugs?

[@TheCodingTrain]

I think it has some bugs I didn't notice! I will have to revisit that code (which is different than the code I wrote in this challenge.)

[@Confuseddave]

I'd love to see you take a crack at some 2d boolean algorithms, like the Vatti clipping algorithm

[@RedHair651]

People: "What does ADHD feel like?" Me: "I realised halfway through the video that he speaks English with the same accent as Kermit the frog, and now I can't listen to his words anymore."

[@kaizen9451]

Fantastic topic! Never knew this existed.

[@ytb.addict]

Sir, First of all, I am a big big big fan of your challenge videos. As asked by you, I would love to see you program "Vornoi Diagram and Decaulay Triangulation Problem".

[@michaeldaly4088]

Coding Challenge Idea: Implementing the shortest splitline algorithm for an arbitrary shape, population, and number of districts. Completed my own coding challenge and had to settle for solving a constrained case (fixed population, fixed # of districts, arbitrary shape) mbdaly.com/projects/gerrymandering/

[@coopercowley4883]

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

[@RuiLopesFR]

11:38: "a cross product is the product of vectors which are on the same plane" Two non-colinear vectors always define a plane, two colinear vectors always define a line, which is always contained in a plane; so two vectors are always on the same plane ;-) Sorry, that's only my math disorder syndrom at play...

[@engboy69]

One of my lecturers mentioned using the convex hull to enclose cancerous tissue inside bone. Thanks for helping me visualise it!

[@TheCodingTrain]

If you create something using the algorithm please share!

[@nraynaud]

I have a question for you: what's the average number of points in the convex hull of a random point cloud of size n?

[@jetexeryt1127]

Couldnt you just put a string around all the points and tighten it? Idk how the logic would work but i think the outcome would be the same

[@renecura]

Hi, really late observation but I think you are calculating the cross product of the vector from the origin to the points, not the actual ones you are drawing. It's surprising that it actually works.

[@solepanic6583]

a los 4 que le dieron dislike, todo bien en casa? for the four that dont like the video, everything is good at home ?

[@sergeyblackoff8695]

No left point! ONLY CENTER IMAGE START NOW!!!

[@XX-vu5jo]

Why is he claiming that he came with the "Gift Wrapping" algorithm? LOL!

[@kizunoV]

I love these animations. Would also like to see the divide and conquer convex hull animation as it would probably be cool in teaching people divide and conquer.

[@BlueYoshiProductions]

For more computational geometry you could try animating a Voronoi Diagram. Eg: en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Voronoi_growth_euclidean.gif

[@newirismechanism6230]

Hallo und danke für das interessante Video! Ich habe eine aktuelle Aufgabenstellung: Wie kann man innerhalb einer beliebig geformten Fläche (beispielsweise eine Schnittkontur in einem CAD Programm) mit einem Algorithmus eine Optimierung durchführen, wie innerhalb der vorgegebenen Kontur ein Rechteck mit dem maximalen Flächeninhalt angeordnet werden kann? Gegeben: Fläche, in die das Rechteck passen muss. Freie Parameter: Länge, Breite und Drehwinkel des Rechtecks. Bin gespannt, ob es dafür eine clevere und gut programmierbare Lösung gibt, die man in ein Makro für CAD integrieren kann! Vielen Dank und beste Grüße an Euch! :-)

[@amandixit3555]

14:09 how is the cross product negative ? it should be positive as we are moving in counter clockwise direction from vector a to vector b

[@JuanGarcia-lo2el]

when will more computational algorithms come back?

[@zuku05]

Could you use this to make Travelling Salesman in future video?

[@Rallion1]

The shape created by adding "CLOSE" to endShape hints at a possible optimisation; if you can figure out what points are within that shape, you don't need to check them.

[@1000AbstractMachines]

hehe that what I thought too. but how can you figure out what points are in that shape without "checking them" first ? ;)

[@tshivhulatshilidzi9209]

You can use Chan Algorithm it will perform way better

[@father_mihai]

Mulțumim!

[@nevahid1]

I wrote a processing program about Kinetic K-Center Problem, which is a computational geometry topic, it is done based on Black-Box model, although there are some big differences, what do you think? can we try to tackle it and maybe (surely!) improve my algorithm?

[@TheCodingTrain]

Please suggest here! github.com/CodingTrain/Rainbow-Topics/issues

[@JohannesSchmitz]

So the three well known algorithms seem to be Jarvis march (gift wrapping), Graham's scan and Chan's algorithm which kind of combines the former two. Is there anything else more efficient that I have overlooked?

[@JohannesSchmitz]

Just found that this wikipedia article answers my question: en.m.wikipedia.org/wiki/Convex_hull_algorithms

[@sweetie_py]

omg... i wish i could be smart like you your vids are gold.

[@siddhantjain2402]

Hi! Can you also please add some real-world use cases of the algorithms you cover in coding challenges? I really like to see you code but it would be great to know where it can be applied.

[@TheCodingTrain]

Great suggestion!

[@bca6943]

I don't think the "nextIndex" variable is necessary.

[@mehdisaffar]

I have a feeling that this could have been coded much cleaner had you used generator functions. The algorithm when written inside the generator algorithm would be pretty similar to the gift wrapping algorithm pseudo code you would find online, instead of being "scattered around" in setup and draw. any time a draw happens, you ask for the next value from the generator. The generator could return the new state of the points each time. Neat video though :)

[@TheCodingTrain]

I keep getting people recommending generator functions to me! I've actually never used one, something I definitely need to learn. Thank you for the tip!

[@KouzelniceKelly]

👍👍👍

In the last version looks like You can exclude all the points which are already inside boundary.... that would be great optimisation.

[@connecticutaggie]

Is there an algorithm that determines for any closed path of points (concave or convex) whether another specified point is inside or outside of that path?

[@APaleDot]

Yes. The easiest one to understand is the even-odd test. Make a line from a point "really far away" to the test point. Check to see if this line intersects with any of the lines in the closed path. If the number of collisions is even, the point is outside the path, if it is odd, the point is inside the path. This works because every time the line enters or exits the shape, it intersects with the path leading to a pattern of outside-inside-outside-inside-...etc. The test line can't extend into or out of the shape without intersecting a line, and it likewise can't intersect a line in the path without extending into or out of the shape.

[@tzq33tdq]

8:38 what happened with your voice? Are you okay?

[@TheCodingTrain]

I had a cold when I recorded this challenge!

[@Jova]

can you cover a concave hull algorithm as well?

[@vincentcleaver1925]

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

[@Vanessaleeyl]

please do Delaunay triangulation it'll be interesting