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

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


32 thoughts on “Coding Challenge #148: Gift Wrapping Algorithm (Convex Hull)”

  1. For a new challenge: How about getting your position by triangulation of signals from cell towers or satellites as a simulation?

  2. 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

  3. Dwight Keller-Williams

    so… a way to make it a little more efficient would be to not check the points inside the shape… I wonder how you would do that…

  4. 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

  5. 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?

  6. 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!

  7. Jānis Grīnvalds

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

  8. 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.

  9. 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.

  10. I am finally working on triangulating a point set. I am picking points in my canvas and making triangles using the cross product to find points outside existing triangles (or inside; that'll be fun…)

  11. 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.

  12. Whenever I want to animate an algorithm, I use a generator function. I would ask you to just look up what that is *, but I like to think of it as:

    Instead of doing the algorithm in the animation loop (the hard part), having a separate algorithm loop, and then synchronizing both loops together.

    * Or you can just learn it here! https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*

  13. 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 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *