d3-geo-voronoi
A JavaScript library for computing Voronoi diagrams and Delaunay triangulations on the surface of a sphere.
What is d3-geo-voronoi?
d3-geo-voronoi is a JavaScript library that adapts planar Delaunay triangulation and Voronoi diagram algorithms to work with spherical data, enabling geographic and spatial computations on a globe. It provides tools for generating spherical Voronoi tessellations, Delaunay triangulations, convex hulls, Urquhart graphs, and contour lines from spherical coordinates. The library solves the problem of performing accurate spatial analysis and visualization on spherical surfaces, such as Earth or celestial bodies, where planar projections can distort results.
This library is designed for data visualization developers and geospatial analysts working with geographic data on spherical surfaces, particularly those using the D3.js ecosystem for mapping and spatial computations. It is also suitable for researchers or engineers needing mesh generation, point location queries, or contouring for non-gridded spherical data.
Developers choose d3-geo-voronoi because it offers accurate spherical geometry computations while maintaining compatibility with D3.js, providing familiar APIs that extend planar concepts to the globe. Its dual API design allows for both high-level GeoJSON outputs for easy visualization and low-level index-based access for efficient topological computations, balancing performance and usability.
Overview
Voronoi / Delaunay tessellations on the sphere
Use Cases
Best For
- Generating Voronoi diagrams or Delaunay triangulations directly on a sphere for geographic data visualization.
- Performing spatial analysis tasks like point location queries to find the closest data point or containing Voronoi cell on a spherical surface.
- Creating contour lines and isobands for non-gridded data distributed over a sphere, similar to d3-contour but for spherical coordinates.
- Computing spherical convex hulls or Urquhart graphs from datasets with geographic coordinates.
- Building interactive maps or globes that require mesh generation, tessellation, or proximity-based graphs for spatial data.
- Integrating spherical spatial computations into D3.js-based projects with APIs that mirror planar counterparts like d3-voronoi and d3-delaunay.
Not Ideal For
- Projects dealing exclusively with planar 2D data where standard d3-delaunay is sufficient and more performant.
- Applications requiring convex hull computations for datasets spanning more than a hemisphere, as the library returns null in such cases.
- Teams seeking a drop-in replacement for d3-voronoi without code adjustments, due to output differences (GeoJSON features vs. planar arrays) and missing methods like .extent().
Pros & Cons
Pros
Computes Voronoi diagrams and Delaunay triangulations directly on the sphere using stereographic projection, avoiding distortions from planar approximations, as detailed in the adaptation from d3-delaunay.
Offers both a high-level GeoJSON API (d3.geoVoronoi) for easy map visualization and a lightweight index-based API (d3.geoDelaunay) for efficient topology computations, balancing usability and performance per the README.
Includes spherical convex hull, Urquhart graph, point location queries, and contouring for non-gridded data, extending beyond basic Voronoi/Delaunay to a full suite for geographic analysis.
Maintains compatibility with D3.js by mirroring APIs of d3-voronoi and d3-delaunay, easing adoption for developers already familiar with planar D3 spatial libraries.
Cons
Does not implement .extent() and .size() methods available in d3-voronoi, limiting control over diagram bounds in visualizations, as the README acknowledges this is 'quite tricky' for spherical data.
Convex hull computation fails (returns null) for datasets covering more than a hemisphere, restricting use in global-scale analyses with widely distributed points, a noted constraint in the API reference.
Spherical adaptations introduce computational complexity compared to planar algorithms, potentially impacting performance with very large datasets, and the library requires careful handling of GeoJSON outputs versus planar arrays.
Frequently Asked Questions
Related Projects
Leaflet🍃 JavaScript library for mobile-friendly interactive maps 🇺🇦
Cesium.jsAn open-source JavaScript library for world-class 3D globes and maps :earth_americas:
Deck.GLWebGL2 powered visualization framework
OpenLayersOpenLayers
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.