Convex hull of points
For the points (0, 0), (4, 0), (4, 3), (0, 3) and (2, 1), the convex hull is the rectangle formed by the first four, and (2, 1) stays inside. It is the outline a rubber band would make stretched around your points. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
A convex hull is the smallest convex polygon that contains every point in a finite set—the rubber-band outline if you stretched a band around nails on a board. Surveyors, GIS analysts, game developers, and computational-geometry students all need that outline from unordered samples: GPS tracks, building footprints, sprite vertices, or classroom clouds of (x, y) pairs. This convex hull of points tool runs Andrew’s monotone chain scan: it sorts the points by horizontal then vertical coordinate, builds the lower and upper chains in linear passes, and returns the extreme vertices in counter-clockwise order. Interior points and collinear mid-edge samples drop out automatically. You may send planar x/y pairs or geographic lat/lon points; geo mode still performs a planar hull in the longitude–latitude plane, which is the usual local approximation for city-scale and site-scale envelopes.
What a convex hull is and how the monotone chain works
Given a finite set of points in the plane, the convex hull is the unique smallest convex set that contains them all. Its boundary is a convex polygon whose vertices are a subset of the input: every extreme point that “sticks out” appears on the hull, and every point that can be written as a convex combination of others lies strictly inside or on an edge. Andrew’s monotone chain (also called the monotone chain scan) computes that boundary in O(n log n) time dominated by sorting.
After sorting points by increasing x-coordinate (and by y when x ties), the algorithm walks left to right to build the lower hull, always keeping a strict left turn at the last three vertices of the stack; then it walks right to left to build the upper hull with the same left-turn test. Using a non-strict turn test (cross product less than or equal to zero) removes collinear intermediate points so each edge is maximal.
Degenerate sets are handled cleanly: one unique point returns a one-vertex hull; two distinct points return a two-vertex segment; three or more collinear points return only the two extremes. That behaviour matches classroom definitions of the extreme-point hull and keeps downstream polygon tools free of zero-area “dents” caused by mid-edge samples.
Where a convex outline comes in handy
Mapping and logistics teams compute the convex envelope of delivery stops, asset pings, or survey markers to draw a simple outer boundary without manual digitizing. Game and CAD pipelines shrink collision proxies or UI selection boxes to the hull of mesh or sprite vertices so overlap tests stay cheap. Data-science notebooks use the hull as a robust outer contour for scatter plots and anomaly review when a bounding box is too loose and a concave alpha shape is too heavy.
Classroom and contest platforms need a deterministic oracle for “list the extreme points in order” exercises; a pure parse capability returns byte-stable coordinates at a fixed precision so graders never flake on floating noise. Failed validation does not consume balance. Keep clouds under the ten-thousand-point cap, pin hull vertices in tests, and you get reproducible envelopes for GIS ETL, edge workers, and homework without standing up a full geometry library of your own.
What you can do with it
GIS envelope of GPS samples
Send unordered lat/lon pings from a field survey or vehicle track and obtain the counter-clockwise convex outline for map overlays and simple service-area sketches.
Game and CAD collision proxies
Reduce a cloud of mesh or sprite vertices to a strict convex hull for fast broad-phase collision and selection bounds without shipping a full CG library.
Classroom computational geometry checks
Let students submit point sets and verify ordered extreme vertices against monotone-chain theory, including collinear and duplicate edge cases.
FAQ
Does geographic mode use a spherical geodesic hull?
No. Geo mode validates lat/lon ranges and runs a planar monotone chain in the longitude–latitude plane. That local approximation is standard for city- and site-scale envelopes; global geodesic hulls are out of scope.
Are collinear points kept on the hull?
Intermediate collinear points on an edge are removed.
What is the minimum number of points?
At least one. One unique point returns a one-vertex hull; two points return a segment; three or more non-collinear points return a polygonal hull.
In what order are the hull vertices returned?
Counter-clockwise, starting from the left-most point, or the lowest of those if several share the same left edge. The ring is left open, so the first vertex is not repeated at the end.
How many points can I enter at once?
Up to 10000 points per calculation. Exact duplicates are merged before the outline is built, so a corner entered twice never appears twice on the hull or inflates the vertex count.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/geo/polygon-convex-hull \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}'const res = await fetch("https://api.kit.forhosting.com/geo/polygon-convex-hull", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"points": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
},
{
"x": 2,
"y": 1
}
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/geo/polygon-convex-hull",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"points": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
},
{
"x": 2,
"y": 1
}
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/geo/polygon-convex-hull", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"points":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3},{"x":2,"y":1}]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/geo/polygon-convex-hull", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"points": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
},
{
"x": 2,
"y": 1
}
]
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "geo.polygon_convex_hull",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
What a convex hull is and how the monotone chain works
Concatenating the two chains without duplicating the shared left-most and right-most endpoints yields the full hull in counter-clockwise order starting at the left-most (then bottom-most) extreme. Exact duplicate coordinates are collapsed before the scans so a repeated corner never inflates hull_count.
Input contract, coordinate modes, and response fields
Each record may be {x, y} for planar work, {lat, lon} for geographic samples, or a two-number array. In auto mode, lat/lon keys select geographic labelling; x/y keys select planar labelling. Geo mode validates latitude in [−90, 90] and longitude in [−180, 180] and still runs the hull in the lon–lat plane (x = longitude, y = latitude). Optional precision (0–15, default 10) sets decimal places on returned coordinates. The hull ring is open: the first vertex is not repeated at the end. POST a JSON body with required points: an array of at least one coordinate record. Aliases vertices, coordinates, and coords are accepted for the array. Optional coord_mode is auto (default), planar, or geo. On success the body includes hull (ordered extreme vertices), hull_count, point_count (input length), unique_count (after dropping exact duplicates), interior_count (unique points not on the hull), method equal to monotone_chain, coord_mode resolved to planar or geo, and orientation equal to ccw. Missing points, an empty array, non-finite numbers, out-of-range latitudes or longitudes in geo mode, or more than ten thousand points fail with invalid_input and are not billed. Pair this endpoint with area or perimeter calculators only after you have an ordered ring; the hull output is already ordered and ready for those tools when you need the envelope metrics of a point cloud rather than of a hand-digitized polygon.
Technical questions
How do I compute the convex hull of a set of points?
POST points as an array of {x,y} or {lat,lon} records (at least one). The API sorts them and runs Andrew’s monotone chain, returning hull vertices in counter-clockwise order with method monotone_chain.
What does the convex hull of points calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.