Top Cut of Convex Hull

C++. I developed an algorithm based on “three penny algorithm” to find the top cut of a convex hull for dense circle shaped data. It takes the most left point as an entry point like Jarvis’s march. However, it is different from Graham scan and Jarvis’s march because it does its calculation by directly sweeping x plane from left to right.

It works with data as sorted and no far extreme points. For extreme points, orientation calculation would change according the position. And also, this algorithm would work for bottom cut too when orientation direction is changed. Moreover, data includes start and end points on x plane for a better demonstration. You will see the circumference points as red on x-y coordinates (see the figure below).

* int data type was chosen for a better readability.


[1] Convex hulls

[2] Convex hull Jarvis’s Algorithm