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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5struct Point {
6 int x, y;
7};
8
9int compare(const void *vp1, const void *vp2) {
10 struct Point *p1 = (struct Point *)vp1;
11 struct Point *p2 = (struct Point *)vp2;
12 return (p1->x != p2->x) ? (p1->x - p2->x) : (p1->y - p2->y);
13}
14
15int cross(struct Point O, struct Point A, struct Point B) {
16 return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
17}
18
19void convexHull(struct Point *points, int n, struct Point *hull, int *hullSize) {
20 qsort(points, n, sizeof(struct Point), compare);
21
22 int k = 0;
23 for (int i = 0; i < n; ++i) {
24 while (k >= 2 && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
25 hull[k++] = points[i];
26 }
27
28 for (int i = n - 2, t = k + 1; i >= 0; i--) {
29 while (k >= t && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
30 hull[k++] = points[i];
31 }
32 *hullSize = k - 1;
33}
34
35int main() {
36 struct Point trees[] = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
37 int numTrees = sizeof(trees) / sizeof(trees[0]);
38
39 struct Point hull[8];
40 int hullSize = 0;
41
42 convexHull(trees, numTrees, hull, &hullSize);
43
44 printf("Convex Hull:\n");
45 for (int i = 0; i < hullSize; i++) {
46 printf("(%d, %d)\n", hull[i].x, hull[i].y);
47 }
48
49 return 0;
50}This C code implements the Monotone Chain Algorithm for finding the convex hull. First, it sorts the points, then constructs the lower and upper hulls. Sorting ensures all points are processed in order, while stack logic applies to maintaining valid hull points by checking the turn direction using cross product.
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.
1using System.Collections.Generic;
class Point {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Program {
static int Orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
return (val == 0) ? 0 : (val > 0 ? 1 : 2);
}
static List<Point> ConvexHull(Point[] points) {
if (points.Length < 3) return new List<Point>();
List<Point> hull = new List<Point>();
int leftmost = 0;
for (int i = 1; i < points.Length; i++)
if (points[i].x < points[leftmost].x)
leftmost = i;
int p = leftmost, q;
do {
hull.Add(points[p]);
q = (p + 1) % points.Length;
for (int i = 0; i < points.Length; i++)
if (Orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p != leftmost);
return hull;
}
static void Main(string[] args) {
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) };
List<Point> result = ConvexHull(trees);
Console.WriteLine("Convex Hull:");
foreach (var p in result)
Console.WriteLine($"({p.x}, {p.y})");
}
}This C# solution employs the Gift Wrapping strategy by iterating points to fill the hull. It uses a direction check relative to the previous hull point to ensure counterclockwise traversal for subsequent points.