Branch	macOS/Linux/Windows
master
dev

jc_voronoi

A fast C header only implementation for creating 2D Voronoi diagrams from a point set

• Uses Fortune's sweep algorithm.
• Disclaimer: This software is supplied "AS IS" without any warranties and support
• LICENSE (The MIT license)
• Showcases
• Documentation

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

Install

macOS with Homebrew

Install the C headers and CMake package metadata from the project tap:

brew install JCash/tap/jc-voronoi

A CMake project can then consume the installed header-only target:

find_package(jc_voronoi CONFIG REQUIRED)
target_link_libraries(your_app PRIVATE jc_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-voronoi

import { loadVoronoi } from "jc-voronoi";

const voronoi = await loadVoronoi();

See README_JS.md 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:

#define JC_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_app PRIVATE jc_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 build

The 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.svg

Linux

Build and run the example (assumes clang is installed):

./scripts/compile.sh
./build/main -n 100 -r 3 -w 1024 -h 768 -o example.svg

Windows

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.svg

The 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 GitHub Releases page. 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 interactive WebAssembly demo, which is rebuilt from the dev branch.

import { loadVoronoi } from "./voronoi.js";

const voronoi = await loadVoronoi();
const edges = voronoi.edges(
  [{ x: 10, y: 20 }, { x: 80, y: 30 }, { x: 40, y: 90 }],
  100,
  100,
);
// Float32Array: x0, y0, x1, y1 for each edge

For 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:

const diagram = voronoi.generate(
  [{ x: 10, y: 20 }, { x: 80, y: 30 }, { x: 40, y: 90 }],
  { bounds: [0, 0, 100, 100] },
);

const cell = diagram.cell(0); // null if the input site was pruned
if (cell) {
  console.log(cell.site.index, cell.site.p.x, cell.site.p.y);
  for (const { x, y } of cell.polygon) console.log(x, y);
  for (const edge of cell.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";

const voronoi = await loadVoronoiWorker();
const diagram = await voronoi.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 site

Open 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 benchmark

See Benchmarks.md 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 JCash/homebrew-tap repository. That repository updates and stores the Homebrew formula.

#define JCV_REAL_TYPE double
#define JCV_REAL_TYPE_EPSILON DBL_EPSILON
#define JCV_ATAN2 atan2
#define JCV_SQRT sqrt
#define JCV_FLT_MAX DBL_MAX
#define JCV_PI 3.14159265358979323846264338327950288
#define JC_VORONOI_IMPLEMENTATION
#include "jc_voronoi.h"

Usage

• Migration guide

Api

The main api contains these functions

void jcv_diagram_generate( int num_points, const jcv_point* points, const jcv_rect* rect, const jcv_clipper* clipper, jcv_diagram* diagram );
void jcv_delaunay_generate( int num_points, const jcv_point* points, const jcv_rect* rect, const jcv_clipper* clipper, jcv_diagram* diagram );
void jcv_diagram_generate_useralloc( int num_points, const jcv_point* points, const jcv_rect* rect, const jcv_clipper* clipper, void* userallocctx, FJCVAllocFn allocfn, FJCVFreeFn freefn, jcv_diagram* diagram );
void jcv_diagram_free( jcv_diagram* diagram );

const jcv_site* jcv_diagram_get_sites( const jcv_diagram* diagram );
int jcv_get_num_vertices( const jcv_diagram* diagram );
void jcv_diagram_get_vertices( const jcv_diagram* diagram, jcv_point* vertices );
int jcv_diagram_get_edge_count( const jcv_diagram* diagram );
int jcv_delaunay_get_edge_count( const jcv_diagram* diagram );
void jcv_diagram_get_edges( const jcv_diagram* diagram, jcv_edge_iter* iter );
void jcv_site_get_edges( const jcv_diagram* diagram, const jcv_site* site, jcv_edge_iter* iter );
int jcv_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_point points[] = {
    { 0, 0 },
    { 100, 0 },
    { 50, 100 }
};

jcv_diagram diagram = {0};
jcv_diagram_generate(3, points, NULL, NULL, &diagram);

const jcv_site* sites = jcv_diagram_get_sites(&diagram);
for( int i = 0; i < diagram.numsites; ++i )
{
    const jcv_site* site = &sites[i];

    jcv_edge_iter iter;
    jcv_edge edge;
    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

const jcv_site* sites = jcv_diagram_get_sites(&diagram);
const jcv_site** sites_by_input = calloc(
    (size_t)num_points, sizeof(*sites_by_input));

for( int i = 0; i < diagram.numsites; ++i )
    sites_by_input[sites[i].index] = &sites[i];

const jcv_site* site = sites_by_input[input_index];

jcv_diagram diagram = {0};
jcv_delaunay_generate(num_points, points, NULL, NULL, &diagram);
int edge_count = jcv_delaunay_get_edge_count(&diagram);

jcv_delaunay_iter iter;
jcv_delaunay_begin( &diagram, &iter );
jcv_delaunay_edge delaunay_edge;
while (jcv_delaunay_next( &iter, &delaunay_edge ))
{
    ...
}

jcv_diagram_free(&diagram);

jcv_point* vertices = malloc((size_t)jcv_get_num_vertices(&diagram) * sizeof(*vertices));
jcv_diagram_get_vertices(&diagram, vertices);

jcv_edge_iter iter;
jcv_edge edge;
jcv_diagram_get_edges(&diagram, &iter);
while (jcv_edge_next(&iter, &edge))
{
    add_indexed_edge(edge.vertices[0], edge.vertices[1]);
}

int num_vertices = jcv_get_num_vertices(&diagram);
allocate_vertex_site_storage(num_vertices);

const jcv_site* sites = jcv_diagram_get_sites(&diagram);
for( int i = 0; i < diagram.numsites; ++i )
{
    const jcv_site* site = &sites[i];
    jcv_edge_iter iter;
    jcv_edge edge;

    jcv_site_get_edges(&diagram, site, &iter);
    while( jcv_edge_next(&iter, &edge) )
        link_vertex_site(edge.vertices[0], site);
}

void relax_points(const jcv_diagram* diagram, jcv_point* points)
{
    const jcv_site* sites = jcv_diagram_get_sites(diagram);
    for( int i = 0; i < diagram->numsites; ++i )
    {
        const jcv_site* site = &sites[i];
        jcv_point sum = site->p;
        int count = 1;

        jcv_edge_iter iter;
        jcv_edge edge;
        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;
    }
}

    #define JC_VORONOI_CLIP_IMPLEMENTATION
    #include "jc_voronoi_clip.h"

    jcv_clipping_polygon polygon;
    // Triangle
    polygon.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_clipper polygonclipper;
    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_diagram diagram;
    memset(&diagram, 0, sizeof(jcv_diagram));
    jcv_diagram_generate(count, (const jcv_point*)points, 0, clipper, &diagram);

#define JC_VORONOI_IMPLEMENTATION
#include "jc_voronoi.h"

void draw_edges(const jcv_diagram* diagram);
void draw_cells(const jcv_diagram* diagram);
void draw_delaunay(const jcv_diagram* diagram);

void generate_and_draw(int numpoints, const jcv_point* points, int imagewidth, int imageheight)
{
    jcv_diagram diagram;
    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);
}

void draw_edges(const jcv_diagram* diagram)
{
    // If all you need are the edges
    jcv_edge_iter iter;
    jcv_edge edge;
    jcv_diagram_get_edges(diagram, &iter);
    while( jcv_edge_next(&iter, &edge) )
    {
        draw_line(edge.pos[0], edge.pos[1]);
    }
}

void draw_cells(const jcv_diagram* diagram)
{
    // If you want to draw triangles, or relax the diagram,
    // you can iterate over the sites and get all edges easily
    const jcv_site* sites = jcv_diagram_get_sites(diagram);
    for( int i = 0; i < diagram->numsites; ++i )
    {
        const jcv_site* site = &sites[i];

        jcv_edge_iter iter;
        jcv_edge edge;
        jcv_site_get_edges(diagram, site, &iter);
        while( jcv_edge_next(&iter, &edge) )
        {
            draw_triangle(site->p, edge.pos[0], edge.pos[1]);
        }
    }
}

void draw_delaunay(const jcv_diagram* diagram)
{
    jcv_delaunay_iter delaunay;
    jcv_delaunay_begin(diagram, &delaunay);
    jcv_delaunay_edge delaunay_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 _

Same stats, as tables

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.

Voronoi++

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!