GIS Tools - Convex / Concave Hull

What Is a Convex Hull in GIS?

A convex hull is the smallest convex polygon that encloses a set of points, lines, or polygons. Imagine stretching a rubber band around a cluster of nails on a board: when you let go, the rubber band traces the convex hull. Every point in the input lies inside the hull, and the hull has no interior concavities. Convex hull GIS workflows are a staple of spatial analysis, used whenever you need to turn a scatter of locations into an enclosing polygon representing their aggregate footprint.

The Convex / Concave Hull tool on gis.tools lets you compute a convex hull from points (or lines or polygons) directly in your browser. Drop a GeoJSON, Shapefile, KML, or CSV with lat/lon columns, click Generate, and download the enclosing polygon. The tool also supports concave hulls (alpha shapes) which hug the points more tightly and can reveal non-convex cluster shapes that a plain convex hull would miss.

Convex hulls are sometimes called minimum bounding polygons or minimum convex polygons, especially in wildlife biology where they are used to estimate home ranges. In computational geometry they are formal objects with well-known algorithms (Graham scan, Jarvis march, QuickHull, and the Chan algorithm) that run in O(n log n) time.

How Convex Hull Generation Works

Most GIS libraries use a variant of the Graham scan or QuickHull algorithm:

Find an extreme point (e.g., the bottom-most, then left-most)
Sort the remaining points by polar angle around that anchor
Walk through the sorted points, pushing each onto a stack and popping any that would create a right turn
The final stack contains the hull vertices in counter-clockwise order

The algorithm runs in O(n log n) time, dominated by the sort step. Output is a single polygon with no holes or concavities.

Concave Hull (Alpha Shape) Variants

When a convex hull over-represents the footprint of a cluster — for example, wrapping around a U-shaped distribution of points and including empty space in the middle — a concave hull provides a tighter envelope. Common algorithms include alpha shapes, k-nearest neighbors concave hull, and character shapes. A key parameter is the concavity threshold (often called alpha): smaller values produce tighter, more detailed hulls; larger values approach the convex hull.

Input Geometry Types

Convex hull can be computed over:

Points (the most common case)
Lines (vertices are treated as points)
Polygons (vertices are treated as points)
Mixed geometries

Key Parameters and Options

Hull Type

Choose between convex and concave. Default to convex unless you know you need a tighter shape.

Concavity (Alpha)

Applies only to concave hulls. Lower values produce tighter hulls that can introduce holes; higher values approach the convex hull.

Group By

Optionally compute separate hulls for groups of input features by attribute. For example, you can produce one convex hull per species from a layer of wildlife observations.

Practical Applications

Home Range Estimation

Ecologists and wildlife biologists use the Minimum Convex Polygon (MCP) method to estimate animal home ranges from GPS collar data. Each animal's relocation points are wrapped in a convex hull to produce an area estimate that feeds conservation planning and population assessments.

Delineating Study Areas

Fieldwork teams compute convex hulls around sampling points to define the extent of their study area for reporting and mapping purposes.

Market Territory Mapping

Retailers and telecoms draw convex hulls around customer clusters to estimate market territories for resource allocation.

Flight Path Envelopes

Aviation analysts compute convex hulls around historical flight tracks to visualize operational envelopes and airspace usage.

Archaeological Site Footprints

Archaeologists wrap artifact findspots in a convex hull to approximate site extent before excavation.

Fleet Coverage Analysis

Delivery and transportation companies use convex hulls of stop locations to visualize service coverage over time.

Clustering and Density Visualization

Convex hulls of density-based clusters (DBSCAN, HDBSCAN) give a clean polygon representation for each identified group.

Step-by-Step Workflow in gis.tools

Open the Convex / Concave Hull tool
Drag in a vector layer (GeoJSON, Shapefile ZIP, KML, or CSV with lat/lon)
Preview the input points on the map
Choose convex or concave hull mode
Optionally select a grouping attribute to generate one hull per group
Click "Generate Hull" to compute the polygon(s)
Inspect the result and its area
Export as GeoJSON, KML, or Shapefile

Worked Example

A wildlife biologist has 1,200 GPS relocation points from a single elk collar covering one year of monitoring. She loads the GeoJSON into the Convex / Concave Hull tool, selects Convex as the hull type, and clicks Generate. The output is a single polygon encompassing all 1,200 points, with an area of 187 square kilometers. She notes the area as the 100% MCP home range estimate for her publication. For the 95% MCP estimate (which excludes extreme outliers), she would first filter out the 5% of points farthest from the centroid, then re-run the hull.

Common Pitfalls and Gotchas

Convex hulls over-estimate area for clustered or U-shaped distributions. Use a concave hull or a kernel density estimate instead.
Single-point or collinear inputs produce degenerate hulls (a point or a line, not a polygon). Handle these cases explicitly.
Outliers dramatically inflate hull area. A single errant GPS fix can double the calculated home range. Filter outliers first.
Projection matters for area: compute the hull, then reproject to an equal-area CRS before measuring area with the Area Calculator.
Concave hull concavity parameter is fiddly; you may need several tries to find the right tightness.
Duplicate points don't cause issues but inflate processing time; deduplicate with De-duplication Tool first.
Very large point sets (millions of points) are fine because the hull has at most O(h) vertices where h is the number of extreme points.

Tips for Best Results

Reproject to an equal-area CRS before computing area with the Area Calculator
Remove outliers first — an error-laden GPS fix can dominate the hull
Try both convex and concave hulls to see which better represents your distribution
Use group-by to produce per-category hulls in a single pass
Compare hull area to alternative home range estimators (kernel density, bivariate normal) for robustness

Comparison with Other GIS Approaches

QGIS offers Convex Hull under Vector > Geoprocessing Tools, and a Minimum Bounding Geometry tool with the CONVEX_HULL option. ArcGIS Pro exposes it as part of the Minimum Bounding Geometry tool in Data Management. PostGIS has ST_ConvexHull and ST_ConcaveHull. GRASS has v.hull. Turf.js has turf.convex and turf.concave. All produce topologically equivalent output for the same input. The browser-based Convex / Concave Hull tool on gis.tools is ideal for quick interactive analysis without an install.

Performance Considerations

Convex hull is O(n log n) in practice and handles millions of points easily. The bottleneck is usually reading the file, not the hull computation. Concave hull algorithms are more expensive, typically O(n log n) to O(n²) depending on the method.

Data Privacy and Browser-Based Processing

Sensitive location data (wildlife telemetry, medical patient home addresses, covert monitoring points) can be processed privately. Nothing is uploaded; the hull and the original points stay on your device.

Related GIS Concepts

Minimum Bounding Rectangle (MBR) is the simplest envelope: an axis-aligned bounding box. Oriented Bounding Box (OBB) is the tightest rectangle at any orientation. Convex hull is the tightest convex polygon. Concave hull (alpha shape) is a tighter non-convex envelope. Kernel density estimate contours provide a probability-weighted home range alternative. Minimum Enclosing Circle is the smallest circle containing all points.

Frequently Asked Questions

How do I compute a convex hull from points?

Drop the point layer into the tool, select Convex, and click Generate. That's the entire workflow.

What's the difference between convex and concave hull?

A convex hull has no indentations; a concave hull can follow the shape of the cluster more tightly, including concavities.

Can I compute hulls per group?

Yes — use the group-by option to produce one hull per unique attribute value.

What's the minimum number of points needed?

Three non-collinear points produce a triangle. Two points produce a line (not a polygon), and one point is itself.

Convex / Concave Hull

About Hulls