Skip to main content
Version: 0.13.0

Convex hull

The convex_hull aggregation returns the smallest convex region containing everything a bucket matched.

Where geo_bounds gives you a rectangle — which for a diagonal flight path or a coastline is mostly empty ocean — a hull follows the shape of the data. It answers "where is this fleet operating", "what ground does this survey cover", "which area does this customer's activity actually occupy".

It works on geo_point, point, geo_shape and shape fields.

Example​

GET /fleet/_search
{
  "size": 0,
  "aggs": {
    "coverage": {
      "convex_hull": { "field": "location" }
    }
  }
}

The result is a GeoJSON Feature wrapping a Polygon, which a map client can render directly:

"coverage": {
  "type": "Feature",
  "geometry": {
    "type": "Polygon",
    "coordinates": [[[-97.9, 30.1], [-97.6, 30.2], [-97.7, 30.5], [-97.9, 30.1]]]
  },
  "properties": {
    "count": 1482032,
    "exact": true,
    "vertices": 3
  }
}

Put it under a terms aggregation for one hull per vehicle, per customer, or per site.

Buckets whose values do not bound a region are rendered as what they are: a Point for a single distinct location, a LineString for values that are entirely collinear, and a null geometry for an empty bucket. None is forced into a zero-area polygon, which most GeoJSON readers reject.

Parameters​

ParameterDefaultDescription
field—The geo_point, point, geo_shape or shape field.
size1024Maximum number of vertices. Maximum 10000.

It is exact, and stays exact when distributed​

A convex hull is a monoid: the hull of two hulls is the hull of everything they contain. So a shard computes its own hull, sends only the vertices, and the coordinating node feeds them into the same algorithm. Nothing is lost in distribution — a hull over a thousand shards is identical to one computed over a single shard holding the same documents.

That is unusual enough to be worth stating. Most aggregations that summarize a shape over unbounded input trade exactness for a bounded sketch. Here exactness is what makes it bounded: a point inside the hull of what has been seen so far is inside the hull of everything, so it can be discarded the moment it arrives and never reconsidered.

properties.exact is false in exactly two cases, both below.

On a sphere, not on a lat/lon plane​

For geographic fields the hull is computed on the sphere, and it is worth being clear why, because the alternative looks like it works.

Treating longitude and latitude as x and y produces a polygon wrong in two ways. A cluster spanning the antimeridian comes back stretched almost all the way around the world in the wrong direction, because two points a few kilometres apart are 360 degrees apart in that plane. And near the poles the edges are not the paths between the points — the shortest route from Anchorage to Oslo passes north of both, and no straight line in longitude and latitude does — so the polygon excludes territory it should contain.

Points are instead projected gnomonically onto a plane touching the sphere. That projection maps every great circle to a straight line, so the planar hull of the projected points is the spherical hull of the originals, not an approximation of it. The antimeridian stops being special because the projection has no seam; the poles stop being special because the geometry is no longer in degrees.

info

Gnomonic projection covers a hemisphere. The tangent point tracks the data automatically, so this binds only if the matched points genuinely span more than half the planet — in which case the request is rejected with an explanation rather than answered. A convex hull over more than a hemisphere is not well defined: several regions have equal claim to being "the inside". Use geo_bounds for a global extent.

Shapes give an outer bound​

For geo_shape and shape, the hull is built from bounding rectangles rather than outlines, because Lucene's public API over shape doc values exposes the bounding box, centroid, dimension and a relate operation — not an enumeration of the triangles. Getting outlines another way would mean fetching and re-parsing _source for every matched document, which an aggregation over millions of shapes cannot do. The limit is the API surface, not the stored data.

So the hull is built from the corners of each shape's bounding rectangle. The result is guaranteed to contain every matched shape, may be larger than the hull of their outlines, and is flagged exact: false.

That direction is the useful one. "Everything I matched is inside this region" is what a hull over shapes is asked for, and it answers safely; a tight fit that might exclude part of a matched shape would not.

The vertex budget​

size almost never binds. A million points scattered over a region give a hull of a few dozen vertices, because hull size grows like the logarithm or cube root of the input rather than with it.

It exists for the shapes where that is not true. Points lying on a circle put every point on the hull — which is what a ring road, a patrol route or a circular fence line produces — and without a bound one such bucket returns a polygon with as many vertices as it has documents.

When the budget binds, vertices are dropped cheapest-first by the area lost in cutting the corner, and the result is flagged exact: false. The reduced polygon is contained in the true hull, so it may exclude a matched point. Raise size if that matters.

Cost​

Per point: one binary search over the hull's vertices, O(log h), and nothing else for the great majority of points, which are interior. Insertions are rare, and each is O(log h) plus the vertices it removes, which amortizes to nothing since a vertex can only be removed once.

Measured, in nanoseconds per point:

Data10,000 points1,000,000 points
Scattered in a disc4669
On a circle246257
On a grid5439

Flat across a hundredfold increase, which is the property that matters. The circle costs about five times a disc because none of its points can be discarded — that is the shape's own difficulty, and the figure holding steady is what says the implementation is not adding to it.

Memory per bucket is O(h) — the hull's own vertices, plus a rebuild buffer bounded by size.

Things worth knowing​

  • Sub-aggregations are not accepted. A hull is a leaf metric.
  • Concurrent segment search is supported, and cannot change the answer: slices reduce through the same exact merge that shards do.
  • Multi-valued fields contribute every value.
  • A straight edge may come back with a few more vertices than it needs. Exactly collinear points are dropped, but coordinates arrive quantized — a geo_point to about a centimetre — so points along a straight boundary are not exactly collinear once projected, and one may be kept that stands off the edge by less than the index can represent. Thinning by tolerance was tried and does not work safely: on a near-vertical edge the sweep sorts points by rounding rather than position, so a tolerance can drop a genuine corner. A hull missing a corner is a wrong answer that still looks like a plausible polygon.