GitHub - JCash/voronoi: A C implementation for creating 2D Voronoi/Delauney diagrams
BranchmacOS/Linux/Windowsmaster
dev
jc_voronoi
A fast C header only implementation for creating 2D Voronoi diagrams from a point set
Uses
Disclaimer: This software is supplied "AS IS" without any warranties and support
(
)
Brief
I was realizing that the previous 2D voronoi generator I was using, was taking up too much time in my app, and worse, sometimes it also produced errors.
So I started looking for other implementations.
Given the alternatives out there, they usually lack one aspect or the other. So this project set out to achieve a combination of the good things the other libs provide.
Easy to use
Robustness
Speed
Small memory footprint
Single/Double floating point implementation
Readable code
Small code (single source file)
No external dependencies
Cells have a list of edges (for easier/faster relaxation)
Edges should be clipped
A clear license
But mostly, I did it for fun :)
Feature comparisons
Feature vs Implvoronoi++boostfastjetd3-delaunayjcvLanguageC++C++CJavaScriptCEdge clip****Generate Edges*****Generate Cells****Cell Edges Not Flipped**Cell Edges CCW**Easy Relaxation**Custom Allocator*Delaunay generation**Install
macOS with Homebrew
Install the C headers and CMake package metadata from the project tap:
brew install JCash/tap/jc-voronoiA CMake project can then consume the installed header-only target:
find_package(jc_voronoiCONFIGREQUIRED) target_link_libraries(your_appPRIVATEjc_voronoi::jc_voronoi)If CMake does not find the Homebrew prefix automatically, configure with -DCMAKE_PREFIX_PATH="$(brew --prefix jc-voronoi)".
JavaScript and WebAssembly with npm
Install the ES module, WebAssembly runtime, worker, and TypeScript declarations:
npm install jc-voronoiimport{loadVoronoi}from"jc-voronoi";constvoronoi=awaitloadVoronoi();See
for the JavaScript API and examples.
Build
jc_voronoi is a header-only library, so you do not need to build the library itself. The repository also includes src/main.c, an example app that generates a Voronoi diagram and writes it to a PNG or SVG file. Run the commands below from the repository root to build and run that app.
Supported C dialects
The source supports C99 and later: C99, C11, C17, and C23. On compilers that use the pre-standard name for C23, select c2x. The header can also be included from C++.
Using the library
Add src/jc_voronoi.h to your project and emit its implementation from exactly one C or C++ translation unit:
#defineJC_VORONOI_IMPLEMENTATION#include"jc_voronoi.h"Other translation units should include jc_voronoi.h without defining JC_VORONOI_IMPLEMENTATION.
CMake
When this repository is added with add_subdirectory or FetchContent, link the header-only target to your application:
target_link_libraries(your_appPRIVATEjc_voronoi::jc_voronoi)The default CMake build does not produce a library file because jc_voronoi is header-only. To build the bundled example programs and tests, configure with:
cmake -S . -B build -DJC_VORONOI_BUILD_EXAMPLES=ON -DJC_VORONOI_BUILD_TESTS=ON cmake --build build ctest --test-dir buildThe project can also be installed. An installed copy can be consumed with find_package(jc_voronoi CONFIG REQUIRED) and the same namespaced target. Packagers can set JC_VORONOI_VERSION while configuring to add version metadata to the installed CMake package; ordinary source builds do not need a version.
macOS
Build and run the example (assumes clang is installed):
./scripts/compile.sh ./build/main -n 100 -r 3 -w 1024 -h 768 -o example.svgLinux
Build and run the example (assumes clang is installed):
./scripts/compile.sh ./build/main -n 100 -r 3 -w 1024 -h 768 -o example.svgWindows
Install Visual Studio or the Visual Studio Build Tools with the Desktop development with C++ workload. From an x64 Native Tools Command Prompt for VS, run:
scripts\compile_cl.bat build\main.exe -n 100 -r 3 -w 1024 -h 768 -o example.svgThe example above generates 100 random sites, applies three relaxation passes, and writes a 1024 x 768 example.svg in the current directory. Run build/main --help on macOS/Linux or build\main.exe --help on Windows to see all options, including image size, relaxation, input files, and SVG output.
WebAssembly
Version tags automatically publish a browser-ready WebAssembly package on the
. The package contains jc_voronoi.wasm, Emscripten's ES-module loader, the JavaScript API, and its optional one-shot worker. You can also try the
, which is rebuilt from the dev branch.
import{loadVoronoi}from"./voronoi.js";constvoronoi=awaitloadVoronoi();constedges=voronoi.edges([{x: 10,y: 20},{x: 80,y: 30},{x: 40,y: 90}],100,100,);// Float32Array: x0, y0, x1, y1 for each edgeFor site, cell, and edge information, generate an ergonomic diagram. The result is copied once into a compact JavaScript-owned ArrayBuffer, and subsequent object access reads that buffer without calling into WebAssembly:
constdiagram=voronoi.generate([{x: 10,y: 20},{x: 80,y: 30},{x: 40,y: 90}],{bounds: [0,0,100,100]},);constcell=diagram.cell(0);// null if the input site was prunedif(cell){console.log(cell.site.index,cell.site.p.x,cell.site.p.y);for(const{ x, y }ofcell.polygon)console.log(x,y);for(constedgeofcell.edges){console.log(edge.pos[0],edge.pos[1],edge.sites[1]);}}diagram.sites contains the retained sites, diagram.edges contains all Voronoi edges, and diagram.neighbors(inputIndex) returns neighboring Site objects. Cell edges are counter-clockwise. Points support both .x / .y access and [x, y] destructuring. Accessing a diagram object after dispose() throws an error. Disposal is optional because the result buffer is owned and garbage-collected by JavaScript; use it only to release memory eagerly.
Large one-off diagrams can be generated in a disposable worker so the WebAssembly heap does not remain alongside the result:
import{loadVoronoiWorker}from"./voronoi.js";constvoronoi=awaitloadVoronoiWorker();constdiagram=awaitvoronoi.generate(points,{bounds: [0,0,100,100]});The worker transfers the packed result and terminates before generate() resolves. The returned diagram uses the same JavaScript API.
To build the package locally, install the Emscripten SDK and run ./scripts/build_wasm.sh. The output is written to build/wasm by default.
To run the interactive example locally:
./scripts/build_wasm.sh site/vendor npm ci --prefix benchmark npm run build --prefix benchmark python3 -m http.server 8000 --directory siteOpen http://localhost:8000/ for the example.
To regenerate the offline performance report and its wasm-*.svg charts:
./scripts/build_wasm.sh npm ci --prefix benchmark npm run benchmark --prefix benchmarkSee
for the generated tables, methodology, and charts. The benchmark compares diagram generation, generation plus site access, generation plus Voronoi-edge access, and generation plus Delaunay-edge access for the 10k, 100k, and 100k pathological (issue48) inputs. It also generates module-size, Brotli, and source-LOC comparisons. To update only those code-size results, run npm run code-size --prefix benchmark.
Releasing
Create and push a version tag such as v0.11.0. The release workflow uses the tag as the npm package version; the tagged source commit is not modified.
Pushing the tag creates the GitHub release, publishes the jc-voronoi npm package, and uploads the WebAssembly assets. Once those artifacts are available, it dispatches the release to the
repository. That repository updates and stores the Homebrew formula.
Configuration definesDefine configuration macros before including jc_voronoi.h. Use the same configuration in every translation unit that includes the header.
DefinePurposeDefaultJC_VORONOI_IMPLEMENTATIONEmits the implementation; define it in exactly one translation unitNot definedJCV_REAL_TYPEScalar type used for coordinates and calculationsfloatJCV_REAL_TYPE_EPSILONEpsilon used when comparing scalar valuesFLT_EPSILONJCV_ATAN2Two-argument arctangent function matching JCV_REAL_TYPEatan2fJCV_SQRTSquare-root function matching JCV_REAL_TYPEsqrtfJCV_PIPi constant matching JCV_REAL_TYPESingle-precision piJCV_FLT_MAXLargest supported coordinate magnitudeFLT_MAX equivalentJC_VORONOI_CLIP_IMPLEMENTATIONEmits the optional jc_voronoi_clip.h implementationNot definedDouble floating point precision
For double-precision coordinates and calculations, override the scalar type, math functions, limits, and constants before including the header:
#defineJCV_REAL_TYPE double #defineJCV_REAL_TYPE_EPSILON DBL_EPSILON #defineJCV_ATAN2 atan2 #defineJCV_SQRT sqrt #defineJCV_FLT_MAX DBL_MAX #defineJCV_PI 3.14159265358979323846264338327950288 #defineJC_VORONOI_IMPLEMENTATION#include"jc_voronoi.h"Usage
Api
The main api contains these functions
voidjcv_diagram_generate( intnum_points, constjcv_point*points, constjcv_rect*rect, constjcv_clipper*clipper, jcv_diagram*diagram ); voidjcv_delaunay_generate( intnum_points, constjcv_point*points, constjcv_rect*rect, constjcv_clipper*clipper, jcv_diagram*diagram ); voidjcv_diagram_generate_useralloc( intnum_points, constjcv_point*points, constjcv_rect*rect, constjcv_clipper*clipper, void*userallocctx, FJCVAllocFnallocfn, FJCVFreeFnfreefn, jcv_diagram*diagram ); voidjcv_diagram_free( jcv_diagram*diagram ); constjcv_site*jcv_diagram_get_sites( constjcv_diagram*diagram ); intjcv_get_num_vertices( constjcv_diagram*diagram ); voidjcv_diagram_get_vertices( constjcv_diagram*diagram, jcv_point*vertices ); intjcv_diagram_get_edge_count( constjcv_diagram*diagram ); intjcv_delaunay_get_edge_count( constjcv_diagram*diagram ); voidjcv_diagram_get_edges( constjcv_diagram*diagram, jcv_edge_iter*iter ); voidjcv_site_get_edges( constjcv_diagram*diagram, constjcv_site*site, jcv_edge_iter*iter ); intjcv_edge_next( jcv_edge_iter*iter, jcv_edge*edge );Generate a diagram
Create a zero-initialized diagram, generate it from an array of points, iterate through its sites and their edges, then free it when you are done:
jcv_pointpoints[] = { { 0, 0 }, { 100, 0 }, { 50, 100 } }; jcv_diagramdiagram= {0}; jcv_diagram_generate(3, points, NULL, NULL, &diagram); constjcv_site*sites=jcv_diagram_get_sites(&diagram); for( inti=0; i<diagram.numsites; ++i ) { constjcv_site*site=&sites[i]; jcv_edge_iteriter; jcv_edgeedge; jcv_site_get_edges(&diagram, site, &iter); while( jcv_edge_next(&iter, &edge) ) { // Use site and edge here. } } jcv_diagram_free(&diagram);Passing NULL for the bounding rectangle calculates one automatically. Passing NULL for the clipper uses the default box clipper.
The input points are pruned if
There are duplicates points
The input points are outside of the bounding box
The input points are rejected by the clipper's test function
The input bounding box is optional
The input clipper is optional, a default box clipper is used by default
Accessing sites in input orderThe sites returned by jcv_diagram_get_sites are sorted for Fortune's sweep algorithm and are not in the same order as the input points. Each site's index is the index of its original input point. To access sites by that index, create a reverse lookup after generating the diagram:
constjcv_site*sites=jcv_diagram_get_sites(&diagram); constjcv_site**sites_by_input=calloc( (size_t)num_points, sizeof(*sites_by_input)); for( inti=0; i<diagram.numsites; ++i ) sites_by_input[sites[i].index] =&sites[i]; constjcv_site*site=sites_by_input[input_index];Allocate the lookup for the original number of input points, rather than diagram.numsites. An entry can be NULL when the corresponding input point was pruned because it was a duplicate, outside the bounding box, or rejected by the clipper. The site pointers remain valid until jcv_diagram_free is called. Free sites_by_input when it is no longer needed.
Both edge functions initialize a jcv_edge_iter; jcv_edge_next then fills a caller-owned jcv_edge and performs no allocation. Diagram iteration returns each edge once. Site iteration returns the site's edges in counter-clockwise order, with edge.sites[0] set to that site and the endpoints oriented around the cell.
Delaunay triangulationIf only Delaunay adjacency is needed, generate it without clipping or building Voronoi cell topology: (See
for a practical example)
jcv_diagramdiagram= {0}; jcv_delaunay_generate(num_points, points, NULL, NULL, &diagram); intedge_count=jcv_delaunay_get_edge_count(&diagram); jcv_delaunay_iteriter; jcv_delaunay_begin( &diagram, &iter ); jcv_delaunay_edgedelaunay_edge; while (jcv_delaunay_next( &iter, &delaunay_edge )) { ... } jcv_diagram_free(&diagram);Sites and the Delaunay iterator are available on a Delaunay-only diagram. Only the sites and pos members of each jcv_delaunay_edge are valid. Voronoi edge geometry, per-site edges, and unique vertices are intentionally unavailable.
Unique verticesEach edge endpoint has a contiguous integer vertex index. The diagram itself does not allocate a separate vertex array; clients can create one only when it is needed, without comparing floating-point coordinates:
jcv_point*vertices=malloc((size_t)jcv_get_num_vertices(&diagram) *sizeof(*vertices)); jcv_diagram_get_vertices(&diagram, vertices); jcv_edge_iteriter; jcv_edgeedge; jcv_diagram_get_edges(&diagram, &iter); while (jcv_edge_next(&iter, &edge)) { add_indexed_edge(edge.vertices[0], edge.vertices[1]); }To build a mapping from each vertex to its connected sites, iterate over each site's edges and link the first endpoint. Since the edges form an ordered, closed loop, this visits each vertex of the site exactly once:
intnum_vertices=jcv_get_num_vertices(&diagram); allocate_vertex_site_storage(num_vertices); constjcv_site*sites=jcv_diagram_get_sites(&diagram); for( inti=0; i<diagram.numsites; ++i ) { constjcv_site*site=&sites[i]; jcv_edge_iteriter; jcv_edgeedge; jcv_site_get_edges(&diagram, site, &iter); while( jcv_edge_next(&iter, &edge) ) link_vertex_site(edge.vertices[0], site); }Here, allocate_vertex_site_storage and link_vertex_site are client-defined.
Relaxing the pointsHere is an example of how to do the relaxations of the cells.
voidrelax_points(constjcv_diagram*diagram, jcv_point*points) { constjcv_site*sites=jcv_diagram_get_sites(diagram); for( inti=0; i<diagram->numsites; ++i ) { constjcv_site*site=&sites[i]; jcv_pointsum=site->p; intcount=1; jcv_edge_iteriter; jcv_edgeedge; jcv_site_get_edges(diagram, site, &iter); while( jcv_edge_next(&iter, &edge) ) { sum.x+=edge.pos[0].x; sum.y+=edge.pos[0].y; ++count; } points[site->index].x=sum.x / count; points[site->index].y=sum.y / count; } }Custom clippingThe library also comes with a second header, that contains code for custom clipping of edges against a convex polygon.
The polygon is defined by a set of
Again, see
for a practical example
#defineJC_VORONOI_CLIP_IMPLEMENTATION#include"jc_voronoi_clip.h"jcv_clipping_polygonpolygon; // Trianglepolygon.num_points=3; polygon.points= (jcv_point*)malloc(sizeof(jcv_point)*(size_t)polygon.num_points); polygon.points[0].x=width/2; polygon.points[1].x=width-width/5; polygon.points[2].x=width/5; polygon.points[0].y=height/5; polygon.points[1].y=height-height/5; polygon.points[2].y=height-height/5; jcv_clipperpolygonclipper; polygonclipper.test_fn=jcv_clip_polygon_test_point; polygonclipper.clip_fn=jcv_clip_polygon_clip_edge; polygonclipper.fill_fn=jcv_clip_polygon_fill_gaps; polygonclipper.ctx=&polygon; jcv_diagramdiagram; memset(&diagram, 0, sizeof(jcv_diagram)); jcv_diagram_generate(count, (constjcv_point*)points, 0, clipper, &diagram);ExampleExample implementation (see
for actual code):
#defineJC_VORONOI_IMPLEMENTATION#include"jc_voronoi.h"voiddraw_edges(constjcv_diagram*diagram); voiddraw_cells(constjcv_diagram*diagram); voiddraw_delaunay(constjcv_diagram*diagram); voidgenerate_and_draw(intnumpoints, constjcv_point*points, intimagewidth, intimageheight) { jcv_diagramdiagram; memset(&diagram, 0, sizeof(jcv_diagram)); jcv_diagram_generate(numpoints, points, 0, 0, &diagram); draw_edges(&diagram); draw_cells(&diagram); draw_delaunay(&diagram); jcv_diagram_free(&diagram); } voiddraw_edges(constjcv_diagram*diagram) { // If all you need are the edgesjcv_edge_iteriter; jcv_edgeedge; jcv_diagram_get_edges(diagram, &iter); while( jcv_edge_next(&iter, &edge) ) { draw_line(edge.pos[0], edge.pos[1]); } } voiddraw_cells(constjcv_diagram*diagram) { // If you want to draw triangles, or relax the diagram,// you can iterate over the sites and get all edges easilyconstjcv_site*sites=jcv_diagram_get_sites(diagram); for( inti=0; i<diagram->numsites; ++i ) { constjcv_site*site=&sites[i]; jcv_edge_iteriter; jcv_edgeedge; jcv_site_get_edges(diagram, site, &iter); while( jcv_edge_next(&iter, &edge) ) { draw_triangle(site->p, edge.pos[0], edge.pos[1]); } } } voiddraw_delaunay(constjcv_diagram*diagram) { jcv_delaunay_iterdelaunay; jcv_delaunay_begin(diagram, &delaunay); jcv_delaunay_edgedelaunay_edge; while( jcv_delaunay_next(&delaunay, &delaunay_edge) ) { draw_line(delaunay_edge.pos[0], delaunay_edge.pos[1]); } }Some Numbers
Tests run on a Intel(R) Core(TM) i7-7567U CPU @ 3.50GHz MBP with 16 GB 2133 MHz LPDDR3 ram. Each test ran 20 times, and the minimum time is presented below
I removed the voronoi++ from the results, since it was consistently 10x-15x slower than the rest and consumed way more memory _
General thoughts
Fastjet
The Fastjet version is built upon Steven Fortune's original C version, which Shane O'Sullivan improved upon. Given the robustness and speed improvements of the implementation done by Fastjet, that should be the base line to compare other implementations with.
Unfortunately, the code is not very readable, and the license is unclear (GPL?)
Also, if you want access to the actual cells, you have to recreate that yourself using the edges.
Boost
Using boost might be convenient for some, but the sheer amount of code is too great in many cases. I had to install 5 modules of boost to compile (config, core, mpl, preprocessor and polygon). If you install full boost, that's 650mb of source.
It is ~2x as slow as the fastest algorithms, and takes ~2.5x as much memory.
The boost implementation also puts the burden of clipping the final edges on the client.
The code consists of only templated headers, and it increases compile time a lot. For simply generating a 2D voronoi diagram using points as input, it is clearly overkill.
The performance of it is very slow (~20x slower than fastjet) and And it uses ~2.5x-3x more memory than the fastest algorithms.
Using the same data sets as the other algorithms, it breaks under some conditions.
O'Sullivan
A C++ version of the original C version from Steven Fortune.
Although fast, it's not completely robust and will produce errors.
Gallery
I'd love to see what you're using this software for! If possible, please send me images and some brief explanation of your usage of this library!