[EN] The Jarvis March
I am working on a small project that involves a bunch of geometry algorithms. Since it's something I'm doing for fun, I'm rolling my own implementations of every algorithm I use, in modern C++. Right now, I needed a convex hull algorithm that was going to be used for a small amount of vertices (think up to 30 or so). A convex hull is the smallest convex polygon that contains every point in a set. You can think of it as the shape drawn by sticking a bunch of nails to a piece of wood and then releasing a rubber band around them. I don't have a picture of that but, in a more abstact setting, it looks like this: There are a few different algorithms with different performance characteristics that will compute the convex hull for us. The two major ones are The Jarvis March (a very simple O(N^2)), the Graham Scan (more complicated, O(NlogN)). Since my use case involves very few vertices, I went with the Jarvis March. The Jarvis March This is the algorith