Voronoi cells around points
The region nearest each point (its Voronoi cell), planar on a local map within a box around the points, or on the whole sphere for a global set.
Each of the 5 points has a cell on the planar surface.
- Surface
Provenance
- Computed by
- geometry.mesh.voronoi 1.0.0, core 0.1.0
- Model
- From the Delaunay triangulation. Planar: each cell is the box around the points (padded by a tenth of their spread) cut by the perpendicular bisector with each Delaunay neighbor, on an azimuthal equidistant plane. Spherical: the circumcenters of the triangles around the point, in order
- Accuracy
- Exact on the chosen surface; planar cells at the edge of the set end at the box
- Notes
- None
- Cites
- de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M., Springer, Computational Geometry: Algorithms and Applications
Something look off?
How we got thisFormula, worked example, sources, and proof
Model: From the Delaunay triangulation. Planar: each cell is the box around the points (padded by a tenth of their spread) cut by the perpendicular bisector with each Delaunay neighbor, on an azimuthal equidistant plane. Spherical: the circumcenters of the triangles around the point, in order
Show your work
Delaunay triangles
the convex hull on the chosen surface5 points= 4Cells
one per point, from its Delaunay neighbors5 points on the planar surface= 5
The same steps an agent gets from the MCP server with explain: true.
Accuracy: Exact on the chosen surface; planar cells at the edge of the set end at the box
When to use this: Use this to divide ground between points: the catchment of each depot, station, transmitter or sensor, the area each is nearest to, the territory a set of sites carves up between them. Every place inside a cell is closer to that cell's point than to any other, which is what makes it the right answer when the question is which one serves a given place. It is the Delaunay triangulation seen the other way round, so the two come from the same construction.
Limitations: The outer cells are unbounded — nothing stops the territory of an edge point running to the horizon — so on the planar surface they are cut at a box around the points, padded by a tenth of their spread. That box is a presentation choice and not geometry: the outer cells' shapes and areas depend on it, and only the interior cells are determined by the points alone. On the spherical surface no box is needed, since every cell closes. Cells are computed on the chosen surface and a point exactly equidistant from three or more generators sits on a shared corner, so a cell boundary belongs to no single cell.
Worked example: Five survey points. Source: The Delaunay dual; checked against Qhull via SciPy, and against GEOS 3.11.4's voronoi_polygons over fifteen point sets in the same clip box, agreeing on every cell's corner count and on its area to 4.4e-7 relative.
You enter
- Points
- 40, -105 40.01, -104.99 40, -104.98 39.99, -104.992 40.004, -104.995
You get
- Cells
- 5
- Surface
- planar
Review: Not yet independently reviewed by a GIS professional.
Last verified: 2026-09-22, when a maintainer last confirmed this tool's sources at the issuer. See the sources ledger.
Status: version 1.0.0, core 0.1.0. See this tool in the verification report.
Checked against: 20 golden test vectors (download the test vectors, each with its source and tolerance). See how results are checked and every source.
Sources
- Computational Geometry: Algorithms and Applications, de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M., Springer, 3rd edition. Chapter 9 (Delaunay triangulations) and 11.5 (the lifting map and convex hulls).