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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <iostream> #include <vector> struct Point { int x, y; Point(int _x, int _y) : x(_x), y(_y) {} }; int main() { //dense circle shape sorted data at x-y coordinates //it does not include extreme points affecting the circle area density Point dataSet[] = { { -6,0 },{ -5,3 },{ -4,-2 },{ -4,2 },{ -3,-4 },{ -3,1 },{ -3,4 },{ -2,-3 }, { -2,-1 },{ -1,-5 },{ -1,0 },{ -1,2 },{ -1,4 },{ 1,-4 },{ 1,2 },{ 1,5 },{ 2,-2 },{ 2,1 }, { 2,3 },{ 3,-1 },{ 3,0 },{ 4,-4 },{ 4,2 },{ 4,4 },{ 5,-2 },{ 5,1 },{ 6,2 },{ 7,0 } }; int const n = sizeof(dataSet) / sizeof(dataSet[0]); //size of sorted data std::vector<int>UPx; //upper half point x data std::vector<int>UPy; //upper half point y data for (int i = 0; i < n; ++i) { if (dataSet[i].y >= dataSet[0].y) //separating upper half data { UPx.push_back(dataSet[i].x); UPy.push_back(dataSet[i].y); } } //UPPER HALF SIDE std::vector<int>upx; //new up side x data std::vector<int>upy; //new up side y data upx.push_back(UPx[0]); upy.push_back(UPy[0]); upx.push_back(UPx[1]); upy.push_back(UPy[1]); int value = 0; int topSectionSize = UPx.size(); for (int i = 2; i < topSectionSize; ++i) { int upSize = upx.size(); //checking the vector size //calculating orientation of consecutive three points //if value is positive, direction is clockwise (accept) //if value is negative, direction is counterclockwise (reject) value = (upy[upSize - 1] - upy[upSize - 2]) * (UPx[i] - upx[upSize - 1]) - (upx[upSize - 1] - upx[upSize - 2]) * (UPy[i] - upy[upSize - 1]); if (value >= 0) //accept the last point { upx.push_back(UPx[i]); upy.push_back(UPy[i]); } //special case when there is no start and end points at x = 0 if (value < 0 && UPx[i] == UPx.back()) { upx.push_back(UPx[i]); upy.push_back(UPy[i]); value = 0; } //rejecting to add the last point and tracing back where value > 0 while (value < 0) { upx.pop_back(); //deleting the middle point at the triple upy.pop_back(); upSize = upx.size(); //refreshing new vector size value = (upy[upSize - 1] - upy[upSize - 2]) * (UPx[i] - upx[upSize - 1]) - (upx[upSize - 1] - upx[upSize - 2]) * (UPy[i] - upy[upSize - 1]); if (value >= 0 || upSize == 1) { upx.push_back(UPx[i]); upy.push_back(UPy[i]); value = 0; } } } //RESULT topSectionSize = upx.size(); for (int i = 0; i < topSectionSize; ++i) { std::cout << "(" << upx[i] << "," << upy[i] << ")" << std::endl; } return 0; } |
References:
[1] Convex hulls [2] Convex hull Jarvis’s Algorithm