Sponsored
Sponsored
The Monotone Chain Algorithm is an efficient algorithm for finding the convex hull of a set of 2D points. It constructs the hull in O(n log n) time. The idea is to sort the points, then construct the lower and upper hulls in O(n) time each. Points are rejected if they don't form a 'left turn', which can be determined using cross product.
Time complexity is O(n log n) due to sorting. Space complexity is O(n) for storing the hull points.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct Point {
7 int x, y;
8 bool operator<(const Point &p) const {
9 return x == p.x ? y < p.y : x < p.x;
10 }
11};
12
13int cross(const Point &O, const Point &A, const Point &B) {
14 return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
15}
16
17vector<Point> convexHull(vector<Point> &points) {
18 sort(points.begin(), points.end());
19 int n = points.size(), k = 0;
20 vector<Point> hull(2 * n);
21
22 for (int i = 0; i < n; i++) {
23 while (k >= 2 && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
24 hull[k++] = points[i];
25 }
26
27 for (int i = n - 2, t = k + 1; i >= 0; i--) {
28 while (k >= t && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
29 hull[k++] = points[i];
30 }
31
32 hull.resize(k - 1);
33 return hull;
34}
35
36int main() {
37 vector<Point> trees = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
38 vector<Point> result = convexHull(trees);
39
40 cout << "Convex Hull:" << endl;
41 for (auto &p : result)
42 cout << "(" << p.x << ", " << p.y << ")" << endl;
43
44 return 0;
45}This C++ code finds the convex hull using the Monotone Chain Algorithm. It uses a vector to store the hull points and sorts the points initially. The upper and lower hulls are constructed by maintaining constraints on cross product values.
The Gift Wrapping Algorithm, also known as Jarvis March, is another method to find the convex hull. It builds the hull one vertex at a time, looking for the line tangent to the current edge and a point in the set of all remaining points. It's less efficient than Monotone Chain, operating in O(nh) time complexity, where h is the number of hull vertices.
Time complexity is O(nh) where n is the number of points and h is the number of points on the hull. Space complexity is O(h) for the hull array.
1
This Java implementation showcases the use of an ArrayList to gather hull points by searching for the next tangential line using the counterclockwise test. The cycle continues until returning to the start vertex.