Gift Wrapping Algorithm Convex Hull

There are many different convex hull algorithms. I looked at several, including Jarvis March,

Graham Scan and QuickHull. Simplest is Jarvis March (also known as the gift wrapping algorithm).

The algorithm may be summarized as follows:

• Initialization:

• Start with a known point on the convex hull (e.g., the right point).

• Set i = 0 to keep track of the number of steps.

• Main Steps:

• Find the next point pi+1 such that all other points lie to the left of the line formed by pi and pi+1.

• Increment i and repeat until you reach the starting point again (i.e., ph = p0).

• Result:

• The sequence of points obtained during this process forms the convex hull.

In simpler terms, imagine wrapping a string around the set of points, ensuring that no points are on the left side of the string.

Its time complexity is O(nh), where n is the number of points and h is the number of points on the convex hull.

The gift wrapping algorithm, also known as the Jarvis march, is a straightforward method for constructing a convex hull from a set of 2D points. Let’s create a JavaScript implementation of this algorithm:

function orientation(p, q, r) {
    const val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    if (val === 0) return 0; // Collinear
    return val > 0 ? 1 : 2; // Clockwise or counterclockwise
}

function convexHull(points) {
    const n = points.length;
    if (n < 3) return points; // Convex hull not possible

    // Find the point with the lowest y-coordinate (and leftmost if tied)
    let leftmost = 0;
    for (let i = 1; i < n; i++) {
        if (points[i][1] < points[leftmost][1] || (points[i][1] === points[leftmost][1] && points[i][0] < points[leftmost][0])) {
            leftmost = i;
        }
    }

    const hull = [];
    let p = leftmost;
    do {
        hull.push(points[p]);
        let q = (p + 1) % n;
        for (let r = 0; r < n; r++) {
            if (orientation(points[p], points[q], points[r]) === 2) {
                q = r;
            }
        }
        p = q;
    } while (p !== leftmost);

    return hull;
}

// Example usage:
const points = [
    [0, 3],
    [1, 1],
    [2, 2],
    [4, 4],
    [0, 0],
    [1, 2],
    [3, 1],
    [3, 3]
];

const convexHullPoints = convexHull(points);
console.log("Convex Hull Points:", convexHullPoints);

The orientation() function is a crucial part of the gift wrapping algorithm (Jarvis march) for constructing a convex hull from a set of 2D points. Let’s break down how it works:

Purpose:

The orientation(p, q, r) function determines the orientation of three points: p, q, and r.

It helps identify whether these points are collinear, form a clockwise (right turn), or counterclockwise (left turn) arrangement.

Mathematical Insight:

Given three points p(x1, y1), q(x2, y2), and r(x3, y3):

If the cross product of vectors pq and qr is positive, the points are in counterclockwise order (left turn).

If the cross product is negative, the points are in clockwise order (right turn).

If the cross product is zero, the points are collinear.

Implementation:

The function calculates the determinant of the following matrix:

| x1 y1 1 |

| x2 y2 1 |

| x3 y3 1 |

The determinant value (val) is then used to determine the orientation.

Return Values:

If val is zero, the points are collinear (return 0).

If val is positive, the points form a counterclockwise arrangement (return 1).

If val is negative, the points form a clockwise arrangement (return 2).

Example:

Suppose we have three points: p(1, 2), q(3, 5), and r(4, 7).

Calculate the determinant:

val = (5 - 2) (4 - 3) - (3 - 1) (7 - 5)

= 3 1 - 2 2

= -1

Since val is negative, the points p, q, and r form a clockwise arrangement.