Understanding Convex Hull

When working with geographic data, one interesting problem is figuring out how much multiple routes overlap.

At first this sounds simple. You have GPS coordinates, so you might think:

• compare every point,
• calculate distances,
• maybe group nearby coordinates together.

But once routes become larger, this quickly gets messy.

A route is not just a line. It’s really a shape spread across an area.

That’s where convex hull becomes useful.

What Is a Convex Hull?

A convex hull is the smallest convex shape that can contain a set of points.

The easiest way to picture it is this:

Imagine placing nails on a board and stretching a rubber band around them.

The rubber band naturally wraps around the outermost points.

The outer boundary is the convex hull.

       •
   •       •

 •           •

    •     •

       •

Convex hull ignores inner points and keeps only the points needed to describe the outer boundary.

Why This Is Useful

A list of GPS coordinates is difficult to compare directly.

But once you convert those coordinates into polygons, you can start asking useful questions:

• Do these routes overlap?
• How much area do they share?
• Which routes are isolated?
• Which ones cover nearly the same region?

Instead of comparing hundreds of individual coordinates, you compare shapes.

That simplifies the problem a lot.

Building the Hull

Most convex hull implementations follow the same general idea:

1. Sort points
2. Walk through them in order
3. Keep only points that maintain the outer boundary
4. Remove points that create inward turns

One important piece here is the cross product.

The algorithm uses it to determine whether three points form:

• a left turn,
• a right turn,
• or a straight line.

function cross(o, a, b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

If the result is positive, the path turns left. If it’s negative, it turns right.

That small calculation is what helps the algorithm maintain the hull shape.

Example

Imagine these points represent stops from a route:

A •           • B

      •
   •     •

D •           • C

The convex hull would keep:

A → B → C → D

The inner points are ignored because they don’t affect the outer boundary.

Implementation in TypeScript

Here’s a simple implementation using the Monotonic Chain algorithm.

type GeoPoint = {
  lat: number;
  lng: number;
};

function cross(o: GeoPoint, a: GeoPoint, b: GeoPoint): number {
  return (a.lng - o.lng) * (b.lat - o.lat) - (a.lat - o.lat) * (b.lng - o.lng);
}

export function getConvexHull(points: GeoPoint[]): GeoPoint[] {
  if (points.length <= 2) {
    return [...points];
  }

  // Sort points from left to right
  const sorted = [...points].sort((a, b) => {
    if (a.lng !== b.lng) {
      return a.lng - b.lng;
    }

    return a.lat - b.lat;
  });

  const lower: GeoPoint[] = [];

  for (const point of sorted) {
    while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], point) <= 0) {
      lower.pop();
    }

    lower.push(point);
  }

  const upper: GeoPoint[] = [];

  for (let i = sorted.length - 1; i >= 0; i--) {
    const point = sorted[i];

    while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], point) <= 0) {
      upper.pop();
    }

    upper.push(point);
  }

  // Remove duplicate endpoints
  lower.pop();
  upper.pop();

  return [...lower, ...upper];
}

How the Algorithm Works

The implementation builds the hull in two parts:

• lower hull,
• upper hull.

For every new point:

1. The algorithm checks the last two points already in the hull.
2. It calculates the turn direction using the cross product.
3. If the turn goes inward, the middle point is removed.
4. This continues until the boundary stays convex.

The final hull is the combination of both halves.

Measuring Route Overlap

Once each route becomes a polygon, overlap becomes much easier to calculate.

The process usually looks like this:

Route Points
    ↓
Convex Hull
    ↓
Polygon Shape
    ↓
Intersection Area
    ↓
Overlap Percentage

Two routes with heavily intersecting hulls likely operate in similar geographic areas.

Routes with little or no intersection are geographically separated.

Tradeoffs

Convex hull works well when you want a fast and simple representation of a route.

But it also has limitations.

Because the hull is convex, it can sometimes include empty areas that the route never actually touches.

For highly irregular paths, more advanced spatial algorithms may produce better results.

Still, convex hull is often a great balance between:

• simplicity,
• performance,
• and usefulness.