Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
graham_scan_functions.hpp
1/******************************************************************************
2 * @file
3 * @brief Implementation of the [Convex
4 * Hull](https://en.wikipedia.org/wiki/Convex_hull) implementation using [Graham
5 * Scan](https://en.wikipedia.org/wiki/Graham_scan)
6 * @details
7 * In geometry, the convex hull or convex envelope or convex closure of a shape
8 * is the smallest convex set that contains it. The convex hull may be defined
9 * either as the intersection of all convex sets containing a given subset of a
10 * Euclidean space, or equivalently as the set of all convex combinations of
11 * points in the subset. For a bounded subset of the plane, the convex hull may
12 * be visualized as the shape enclosed by a rubber band stretched around the
13 * subset.
14 *
15 * The worst case time complexity of Jarvis’s Algorithm is O(n^2). Using
16 * Graham’s scan algorithm, we can find Convex Hull in O(nLogn) time.
17 *
18 * ### Implementation
19 *
20 * Sort points
21 * We first find the bottom-most point. The idea is to pre-process
22 * points be sorting them with respect to the bottom-most point. Once the points
23 * are sorted, they form a simple closed path.
24 * The sorting criteria is to use the orientation to compare angles without
25 * actually computing them (See the compare() function below) because
26 * computation of actual angles would be inefficient since trigonometric
27 * functions are not simple to evaluate.
28 *
29 * Accept or Reject Points
30 * Once we have the closed path, the next step is to traverse the path and
31 * remove concave points on this path using orientation. The first two points in
32 * sorted array are always part of Convex Hull. For remaining points, we keep
33 * track of recent three points, and find the angle formed by them. Let the
34 * three points be prev(p), curr(c) and next(n). If orientation of these points
35 * (considering them in same order) is not counterclockwise, we discard c,
36 * otherwise we keep it.
37 *
38 * @author [Lajat Manekar](https://github.com/Lazeeez)
39 *
40 *******************************************************************************/
41#include <algorithm> /// for std::swap
42#include <cstdlib> /// for mathematics and datatype conversion
43#include <iostream> /// for IO operations
44#include <stack> /// for std::stack
45#include <vector> /// for std::vector
46
47/******************************************************************************
48 * @namespace geometry
49 * @brief geometric algorithms
50 *******************************************************************************/
51namespace geometry {
52
53/******************************************************************************
54 * @namespace graham scan
55 * @brief convex hull algorithm
56 *******************************************************************************/
57namespace grahamscan {
58
59/******************************************************************************
60 * @struct Point
61 * @brief for X and Y co-ordinates of the co-ordinate.
62 *******************************************************************************/
63struct Point {
64 int x, y;
65};
66
67// A global point needed for sorting points with reference
68// to the first point Used in compare function of qsort()
69
70Point p0;
71
72/******************************************************************************
73 * @brief A utility function to find next to top in a stack.
74 * @param S Stack to be used for the process.
75 * @returns @param Point Co-ordinates of the Point <int, int>
76 *******************************************************************************/
77Point nextToTop(std::stack<Point> *S) {
78 Point p = S->top();
79 S->pop();
80 Point res = S->top();
81 S->push(p);
82 return res;
83}
84
85/******************************************************************************
86 * @brief A utility function to return square of distance between p1 and p2.
87 * @param p1 Co-ordinates of Point 1 <int, int>.
88 * @param p2 Co-ordinates of Point 2 <int, int>.
89 * @returns @param int distance between p1 and p2.
90 *******************************************************************************/
91int distSq(Point p1, Point p2) {
92 return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
93}
94
95/******************************************************************************
96 * @brief To find orientation of ordered triplet (p, q, r).
97 * @param p Co-ordinates of Point p <int, int>.
98 * @param q Co-ordinates of Point q <int, int>.
99 * @param r Co-ordinates of Point r <int, int>.
100 * @returns @param int 0 --> p, q and r are collinear, 1 --> Clockwise,
101 * 2 --> Counterclockwise
102 *******************************************************************************/
103int orientation(Point p, Point q, Point r) {
104 int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
105
106 if (val == 0) {
107 return 0; // collinear
108 }
109 return (val > 0) ? 1 : 2; // clock or counter-clock wise
110}
111
112/******************************************************************************
113 * @brief A function used by library function qsort() to sort an array of
114 * points with respect to the first point
115 * @param vp1 Co-ordinates of Point 1 <int, int>.
116 * @param vp2 Co-ordinates of Point 2 <int, int>.
117 * @returns @param int distance between p1 and p2.
118 *******************************************************************************/
119int compare(const void *vp1, const void *vp2) {
120 auto *p1 = static_cast<const Point *>(vp1);
121 auto *p2 = static_cast<const Point *>(vp2);
122
123 // Find orientation
124 int o = orientation(p0, *p1, *p2);
125 if (o == 0) {
126 return (distSq(p0, *p2) >= distSq(p0, *p1)) ? -1 : 1;
127 }
128
129 return (o == 2) ? -1 : 1;
130}
131
132/******************************************************************************
133 * @brief Prints convex hull of a set of n points.
134 * @param points vector of Point<int, int> with co-ordinates.
135 * @param size Size of the vector.
136 * @returns @param vector vector of Conver Hull.
137 *******************************************************************************/
138std::vector<Point> convexHull(std::vector<Point> points, uint64_t size) {
139 // Find the bottom-most point
140 int ymin = points[0].y, min = 0;
141 for (int i = 1; i < size; i++) {
142 int y = points[i].y;
143
144 // Pick the bottom-most or chose the left-most point in case of tie
145 if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
146 ymin = points[i].y, min = i;
147 }
148 }
149
150 // Place the bottom-most point at first position
151 std::swap(points[0], points[min]);
152
153 // Sort n-1 points with respect to the first point. A point p1 comes
154 // before p2 in sorted output if p2 has larger polar angle
155 // (in counterclockwise direction) than p1.
156 p0 = points[0];
157 qsort(&points[1], size - 1, sizeof(Point), compare);
158
159 // If two or more points make same angle with p0, Remove all but the one
160 // that is farthest from p0 Remember that, in above sorting, our criteria
161 // was to keep the farthest point at the end when more than one points have
162 // same angle.
163 int m = 1; // Initialize size of modified array
164 for (int i = 1; i < size; i++) {
165 // Keep removing i while angle of i and i+1 is same with respect to p0
166 while (i < size - 1 && orientation(p0, points[i], points[i + 1]) == 0) {
167 i++;
168 }
169
170 points[m] = points[i];
171 m++; // Update size of modified array
172 }
173
174 // If modified array of points has less than 3 points, convex hull is not
175 // possible
176 if (m < 3) {
177 return {};
178 };
179
180 // Create an empty stack and push first three points to it.
182 St.push(points[0]);
183 St.push(points[1]);
184 St.push(points[2]);
185
186 // Process remaining n-3 points
187 for (int i = 3; i < m; i++) {
188 // Keep removing top while the angle formed by
189 // points next-to-top, top, and points[i] makes
190 // a non-left turn
191 while (St.size() > 1 &&
192 orientation(nextToTop(&St), St.top(), points[i]) != 2) {
193 St.pop();
194 }
195 St.push(points[i]);
196 }
197
199 // Now stack has the output points, push them into the resultant vector
200 while (!St.empty()) {
201 Point p = St.top();
202 result.push_back(p);
203 St.pop();
204 }
205
206 return result; // return resultant vector with Convex Hull co-ordinates.
207}
208} // namespace grahamscan
209} // namespace geometry
T empty(T... args)
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
T min(T... args)
for std::vector
Definition graham_scan_functions.hpp:51
T pop(T... args)
T push(T... args)
T qsort(T... args)
T size(T... args)
Definition line_segment_intersection.cpp:12
int y
Point respect to x coordinate.
Definition line_segment_intersection.cpp:14
Definition huffman.cpp:28
Definition graham_scan_functions.hpp:63
T swap(T... args)
T top(T... args)