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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Point implements Comparable<Point> {
6 int x, y;
7 Point(int x, int y) {
8 this.x = x;
9 this.y = y;
10 }
11 public int compareTo(Point p) {
12 return this.x == p.x ? this.y - p.y : this.x - p.x;
13 }
14}
15
16public class Main {
17 public static int cross(Point O, Point A, Point B) {
18 return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
19 }
20
21 public static List<Point> convexHull(Point[] points) {
22 Arrays.sort(points);
23 List<Point> hull = new ArrayList<>();
24
25 for (int i = 0; i < points.length; i++) {
26 while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
27 hull.remove(hull.size() - 1);
28 hull.add(points[i]);
29 }
30
31 for (int i = points.length - 2, t = hull.size() + 1; i >= 0; i--) {
32 while (hull.size() >= t && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
33 hull.remove(hull.size() - 1);
34 hull.add(points[i]);
35 }
36
37 return hull.subList(0, hull.size() - 1);
38 }
39
40 public static void main(String[] args) {
41 Point[] trees = {new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2)};
42 List<Point> result = convexHull(trees);
43 System.out.println("Convex Hull:");
44 for (Point p : result)
45 System.out.println("(" + p.x + ", " + p.y + ")");
46 }
47}This Java code sorts the points and iteratively constructs the hull using the Monotone Chain method by checking the direction of turning based on the cross product, removing last point if improper direction is found.
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 JavaScript code implements the Gift Wrapping algorithm; it uses loops to find and stitch together hull vertices by scrutinizing directions between subsequent point pairs until all points in the hull have been determined.